マッチングアルゴリズム

Question

私は鉛筆のリストと消しゴムのリストを持っています。すべての消しゴムを鉛筆でかけることができるかどうかを確認することが目標です。消しゴムは、複数の異なる鉛筆に適合することがあります。鉛筆は最大で1つの消しゴムを持つことができます。

すべての消しゴムをループして鉛筆で塗りつぶしてしまうと、すべての消しゴムが鉛筆で覆われているという解決策があるにもかかわらず、私は空の鉛筆にはならない消しゴムで終わります。

鉛筆のすべての消しゴムに適合する組み合わせを見つけるのに、どのアルゴリズムを使用できますか？ Constraint satisfaction problem

変数は、例えばだろうとあなたが問題を定式化することができます

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

public class Pencil(){ 
} 

私の試み

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

ここには簡単な解決策があります。私はそれがまったくうまくスケールすることを疑う。それはおそらく、最も少ない鉛筆に合った消しゴムから始めれば、より効率的になる可能性があります。

私はEraserクラスで悩まされていません。ここにはmatchesリストの各インデックスに対して1つのEraserがあります。

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

X_i=eraser put on pencil i 

ドメイン

D_i=erasers fitting on pencil i 

と制約問題がその後のCSPのためのバックトラッキングアルゴリズムを用いて解くことができる

X_i != X_j for i!=j 

あります。ヒューリスティックを使用してバックトラック検索を改善するには、「最小残存値」ヒューリスティックなど、さまざまな方法があります。良い本は次のとおりです。 Russell、Norvig：人工知能