algorithm - 确定两组之间最佳配对的Need算法(Need algorithm for determining optimal pairing between two sets)

Question

Say I have 2 sets.

(说我有2套。)

Set A has m elements and set B has n elements.

(集A有m个元素，集B有n个元素。)

Each element in set A can be paired with 0 to n elements in set B. Assume that I have a function that will indicate if a pairing between an element in set A and an element in set B is valid.

(集合A中的每个元素都可以与集合B中的0到n个元素配对。假设我有一个函数，它将指示集合A中的元素和集合B中的元素之间的配对是否有效。)

An ideal pairing solution exists when each element in set B is paired with one unique element from set A. Stated alternatively, not all elements of set A need to be paired with an element in set B, but all elements in set B need to be paired with a unique element in set A (two elements from set B cannot share the same pairing with a single element in set A).

(当集合B中的每个元素与集合A中的一个唯一元素配对时，存在一种理想的配对解决方案。换句话说，并不是集合A的所有元素都需要与集合B中的元素配对，而集合B中的所有元素都需要与集合A中的唯一元素配对（集合B中的两个元素不能与集合A中的单个元素共享相同的配对）。)

What is the algorithm that indicates if an ideal pairing exists?

(指示理想配对是否存在的算法是什么？)

The algorithm does not need to actually give the pairing, only answer if an ideal pairing exists or not.

(该算法不需要实际进行配对，仅在是否存在理想配对时才回答。)

Here is a recursive backtracking O(n^2) algorithm that is probably not the most efficient solution.

(这是一个递归的回溯O（n ^ 2）算法，它可能不是最有效的解决方案。)

    private boolean meetsRequirements(List<Requirement> requirementbuffer, List<Candidate> candidatebuffer) {
    if(requirementbuffer.isEmpty()) return true;
    if(candidatebuffer.isEmpty()) return false;
    for(int i = 0; i < requirementbuffer.size(); i++) {
        Requirement req = requirementbuffer.remove(i);
        for(int j = 0; j < candidatebuffer.size(); j++) {
            Candidate candidate = candidatebuffer.remove(j);
            if(req.isQualifiedCandidate(candidate)) {
                if(meetsRequirements(requirementbuffer, candidatebuffer)) {
                    return true;
                }
            }
            candidatebuffer.add(j, candidate);
        }
        requirementbuffer.add(i, req);
    }
    return false;
}

  ask by PentiumPro200 translate from so

Answer 1

等待大神答复