Algoritmo di corrispondenza

Question

Ho una lista di matite e un elenco di gomme. L'obiettivo è quello di verificare se tutte le gomme possono essere messe sulle matite. Una gomma può adattarsi a più matite diverse. Le matite possono avere al massimo 1 cancellino.

Se metto in circolo tutte le gomme e le metto sulle matite, finisco con gomme che non si adattano a matite vuote, anche se c'è una soluzione che ha tutte le gomme sulle matite.

Quale algoritmo è possibile utilizzare per calcolare una combinazione che si adatta a tutti i gommini delle matite?

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

public class Pencil(){ 
} 

Il mio tentativo

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

Ecco una soluzione semplice. Dubito che tutto si riduca bene. Potrebbe essere probabilmente reso più efficiente iniziando con le gomme per cancellare che si adattano alle poche matite.

Non mi sono preoccupato di una classe Eraser. Qui c'è uno Eraser per ogni indice nell'elenco 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

È possibile formulare il problema come Constraint satisfaction problem

Le variabili sarebbero per esempio

X_i=eraser put on pencil i 

domini

D_i=erasers fitting on pencil i 

ei vincoli sono

X_i != X_j for i!=j 

Il problema può essere risolto con un algoritmo di backtracking per CSP. Esistono molti modi per migliorare la ricerca di backtracking con l'euristica, ad esempio l'euristica "Minimi valori rimanenti". Un buon libro è ad es. Russell, Norvig: Artificial Intelligence