匹配算法

Question

我有一份铅笔清单和一个橡皮清单。目标是检查所有的橡皮是否可以放在铅笔上。一个橡皮可能适合多支不同的铅笔。每支铅笔最多只能有一个橡皮。

如果我只是循环遍历所有的橡皮，并将它们放在铅笔上，最终会出现一些橡皮无法放在任何未被占用的铅笔上，而实际上有一种解决方案可以让所有橡皮都放在铅笔上。

我应该使用什么算法来找到一个组合，以便所有的橡皮都能放在铅笔上？

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

public class Pencil(){
}

My attempt

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;
}

- user3552325

---

匹配标准是什么？ - ChiefTwoPencils

那些铅笔和橡皮有什么特别之处吗？如果橡皮比铅笔少，那么你的答案是“是”，如果橡皮比铅笔多，那么你的答案是“否”。那么是否存在与此相矛盾的细节呢？ - RealSkeptic

@ChiefTwoPencils 它要么匹配，要么不匹配。没有标准。 - user3552325

如果有人能解决这个问题，那肯定是 @ChiefTwoPencils。 - Hovercraft Full Of Eels

@user3552325 我相信你正在寻找最大二分匹配算法。 - Nayuki

Answer 1

你可以将问题表述为 约束满足问题 变量可能包括：

X_i=eraser put on pencil i

领域名称

D_i=erasers fitting on pencil i

限制条件如下：

X_i != X_j for i!=j

问题可以使用用于CSP的回溯算法解决。有许多方法可以通过启发式算法来改进回溯搜索，例如“最少剩余值”启发式算法。一本好书是Russell，Norvig：Artificial Intelligence。

- felix

Answer 2

这里有一个简单的解决方案。我怀疑它的可扩展性不是很好。通过从适合最少铅笔的橡皮擦开始，可能可以使其更加高效。

我没有费心去创建一个Eraser类。在这里，每个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;
} 

- Paul Boddington