Thuật toán đối sánh

Question

Tôi có danh sách bút chì và danh sách các loại tẩy. Mục đích của nó là để kiểm tra xem có phải tất cả các tẩy có thể được đặt trên bút chì hay không. Một cục tẩy có thể vừa với nhiều bút chì khác nhau. Bút chì có thể có tối đa 1 cục tẩy.

Nếu tôi chỉ vòng qua tất cả các tẩy và đặt chúng vào bút chì, tôi kết thúc với tẩy mà không phù hợp với bút chì trống, mặc dù có một giải pháp có tất cả các tẩy trên bút chì.

Tôi có thể sử dụng thuật toán nào để tìm ra một kết hợp phù hợp với tất cả các tẩy xóa trên bút chì?

public class Eraser(){ 
    public boolean matches(Pencil p){ 
    //unimportant 
    } 
} 

public class Pencil(){ 
} 

nỗ lực của tôi

public boolean doMatch(List<Eraser> erasers, List<Pencil> pencils){ 
for (Eraser e : erasers) { 
     boolean found = false; 
     Iterator it = pencils.iterator(); 
     while (it.hasNext()) { 
      Pencil p = (Pencil) it.next(); 
      if (e.matches(p)) { 
       found = true; 
       it.remove(); 
       break; 
      } 
     } 
     if (!found) { 
      return false; 
     } 
} 
return true; 
} 

Answer 1

Đây là một giải pháp đơn giản. Tôi nghi ngờ nó quy mô tốt. Nó có thể có thể được thực hiện hiệu quả hơn bằng cách bắt đầu với các erasers phù hợp với bút chì ít nhất.

Tôi chưa hề bận tâm với lớp học Eraser. Ở đây có một Eraser cho mỗi chỉ mục trong danh sách matches.

private static final class Pencil { 
    private final int id; 
    private Pencil(int id) { this.id = id; } 
    @Override 
    public String toString() { return "p" + id; } 
} 

public static void main(String[] args) { 
    Pencil p1 = new Pencil(1); 
    Pencil p2 = new Pencil(2); 
    Pencil p3 = new Pencil(3); 
    Pencil p4 = new Pencil(4); 
    Pencil p5 = new Pencil(5); 
    List<Set<Pencil>> matches = new ArrayList<>(); 
    matches.add(new HashSet<>(Arrays.asList(p1, p2, p5)));  // First eraser only fits these 3 pencils. 
    matches.add(new HashSet<>(Arrays.asList(p3, p4)));   // Second eraser only fits these 2 pencils. 
    matches.add(new HashSet<>(Arrays.asList(p3, p5)));   // etc 
    matches.add(new HashSet<>(Arrays.asList(p1, p2, p4))); 
    matches.add(new HashSet<>(Arrays.asList(p1, p5))); 
    System.out.println(allocate(matches));      // prints [p2, p4, p3, p1, p5] 
} 

// Returns null if no solution can be found. 
private static List<Pencil> allocate(List<Set<Pencil>> matches) { 
    return allocate(matches, new ArrayList<>()); 
} 

private static List<Pencil> allocate(List<Set<Pencil>> matches, List<Pencil> solution) { 
    int size = solution.size(); 
    if (matches.size() == size) 
     return solution; 
    for (Pencil pencil : matches.get(size)) { 
     if (solution.contains(pencil)) 
      continue; 
     List<Pencil> copy = new ArrayList<>(solution); 
     copy.add(pencil); 
     List<Pencil> result = allocate(matches, copy); 
     if (result != null) 
      return result; 
    } 
    return null; 
} 

Answer 2

Bạn có thể xây dựng các vấn đề như Constraint satisfaction problem

Các biến sẽ là ví dụ

X_i=eraser put on pencil i 

các lĩnh vực

D_i=erasers fitting on pencil i 

và các khó khăn là

X_i != X_j for i!=j 

Vấn đề sau đó có thể được giải quyết với một thuật toán quay lui cho các CSP. Có rất nhiều cách để cải thiện tìm kiếm backtracking với heuristics, ví dụ như "tối thiểu giá trị còn lại" heuristic. Một cuốn sách hay là ví dụ Russell, Norvig: Trí tuệ nhân tạo