匹配算法

Question

我有一张铅笔清单和一张橡皮清单。目的是检查是否所有的橡皮都可以放在铅笔上。橡皮擦可能适合多支不同的铅笔。铅笔最多可以有 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 的回溯算法解决该问题。有很多方法可以通过启发式改进回溯搜索，例如 "Minimum remaining values" 启发式。一本好书是例如Russell, Norvig：人工智能

Answer 2

这是一个简单的解决方案。我怀疑它的扩展性是否很好。从适合最少铅笔的橡皮开始，它可能会变得更有效率。

我没有理会 Eraser class。 matches 列表中的每个索引都有一个 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;
}

匹配算法

Matching algorithm

java

algorithm

matching