java - 匹配算法

Question

我有一张铅笔 list 和一张橡皮 list 。目的是检查是否所有的橡皮都可以放在铅笔上。橡皮擦可能适合多支不同的铅笔。铅笔最多可以有 1 个橡皮擦。

如果我只是循环遍历所有橡皮并将它们放在铅笔上，我最终会得到适合所有未占用铅笔的橡皮，即使有一种解决方案可以将所有橡皮都放在铅笔上。

我可以使用什么算法来找出适合铅笔上所有橡皮的组合？

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

您可以将问题表述为 Constraint satisfaction problem

变量将是例如

X_i=eraser put on pencil i

领域

D_i=erasers fitting on pencil i

约束是

X_i != X_j for i!=j

然后可以使用 CSP 的回溯算法解决该问题。有许多方法可以通过启发式改进回溯搜索，例如“最小剩余值”启发式。一本好书是例如Russell, Norvig:人工智能