Eşleşen algoritma

Question

Kalemlerim ve silgi listemiz var. Amaç, tüm silgilerin kalemlere konup konmadığını kontrol etmektir. Bir silgi, çok farklı kalemlere sığabilir. Kalemler en fazla 1 silgide olabilir.

Tüm silgilerden geçip kurşun kalemlere yapıştıysam, tüm silgi kalemlerine sahip bir çözelti olsa da, kullanılmayan kalemlere uyan silgilerle sonuçlanırım.

Tüm silgi kalemlerine uyan bir kombinasyonu bulmak için hangi algoritmayı kullanabilirim?

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

public class Pencil(){ 
} 

Sen Constraint satisfaction problem

olarak sorunu formüle edebilirsiniz

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

İşte basit bir çözüm. Herhalde iyi ölçeklerim. En az kalemle eşleşen silgilerle başlayarak daha verimli hale getirilebilir.

Eraser sınıfından rahatsız olmadım. Burada matches listesindeki her dizin için bir Eraser var.

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

girişimim değişkenleri örneğin olurdu

X_i=eraser put on pencil i 

etki

D_i=erasers fitting on pencil i 

ve kısıtlamalar sorun daha sonra CSP için backtracking algoritması ile çözülebilir

X_i != X_j for i!=j 

bulunmaktadır. Geriye dönük araştırmayı buluşsal yöntemlerle geliştirmenin birçok yolu vardır, örneğin "Minimum kalan değerler" sezgiseldir. İyi bir kitap örn. Russell, Norvig: Yapay Zeka