Algorytm dopasowania

Question

Mam listę ołówków i listę gumek. Celem jest sprawdzenie, czy wszystkie gumki można umieścić na ołówkach. Gumka może zmieścić się na wielu różnych ołówkach. Ołówki mogą mieć najwyżej 1 gumkę.

Jeśli po prostu przejdę przez wszystkie gumki i położy je na ołówkach, skończę z gumkami, które nie pasują do niezamocowanych ołówków, mimo że istnieje rozwiązanie, które ma wszystkie gumki na ołówkach.

Jakiego algorytmu użyć, aby obliczyć kombinację, która pasuje do wszystkich gumek do ołówków?

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

public class Pencil(){ 
} 

Moja próba

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

Oto proste rozwiązanie. Wątpię, żeby w ogóle dobrze się skaleczyła. Prawdopodobnie może być bardziej efektywny, zaczynając od gumek, które pasują do najmniejszych ołówków.

Nie zawracałem sobie głowy klasą Eraser. Oto jeden Eraser dla każdego indeksu na liście 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

Można sformułować problem jako Constraint satisfaction problem

Zmienne byłoby np

X_i=eraser put on pencil i 

domeny

D_i=erasers fitting on pencil i 

i ograniczenia są

X_i != X_j for i!=j 

Problem ten może być rozwiązany przez algorytm wycofywania dla CSP. Istnieje wiele sposobów na ulepszenie przeszukiwania wstecznego za pomocą heurystyki, na przykład heurystyki "Minimalne wartości pozostałe". Dobra książka to np. Russell, Norvig: Artificial Intelligence