对两个队列项的最佳算法

Question

我必须找到最好的算法来定义两个列表中的项目之间的配对，如图中所示。只有当列表A中的节点数低于列表B中的节点数，并且链路之间没有交叉时，该对才有效。匹配算法的质量取决于链路的总数。

​

​

我首先尝试使用一个非常简单的算法:取列表A中的一个节点，然后查找列表B中高于前者的第一个节点。第二个图显示了一个测试用例，其中该算法不是最好的。

​

​

Answer 1

多亏了大卫的建议，我终于找到了算法。这是一种LCS方法，将'=‘替换为’= '>‘’.

递推法

递归方法非常简单。G和V是大小为n和m的两个向量(在两者的开头加0)。从结尾开始，如果最后一次从G大于最后一次从V开始，则返回1+不带最后一项的函数，否则返回函数从G中移除的最大值或最后从V中移除的函数。

int evaluateMaxRecursive(vector<int> V, vector<int> G, int n, int m) {
   if ((n == 0) || (m == 0)) {
     return 0;
   }
   else {
      if (V[n] < G[m]) {
         return 1 + evaluateMaxRecursive(V, G, n - 1, m - 1);
      } else {
         return max(evaluateMaxRecursive(V, G, n - 1, m), evaluateMaxRecursive(V, G, n, m - 1));
      }
   }
};

由于对循环期间发生的相同列表进行重新评估，递归方法对于少量项是有效的。

非递归方法

非递归方法是相反的，它使用了一个表，该表在复制到0、第一行和第一列之后被填充。最大值是表左下角的值。

int evaluateMax(vector<int> V, vector<int> G, int n, int m) {
    
    int** table = new int* [n + 1];
    for (int i = 0; i < n + 1; ++i)
        table[i] = new int[m + 1];
    
    for (int i = 0; i < n + 1; i++)
        for (int t = 0; t < m + 1; t++)
            table[i][t] = 0;
    
    for (int i = 1; i < m + 1; i++) 
        for (int t = 1; t < n + 1; t++) {
            if (G[i - 1] > V[t - 1]) {
                table[t] [i] = 1 + table[t - 1][i - 1];
            }
            else {
                table[t][i] = max(table[t][i - 1], table[t - 1][i]);
            }
        }
    
    return table[n][m];
}

您可以在这里找到更多详细信息，LCS - Wikipedia。

Answer 2

简单的回溯可以工作(这可能不是最优的，但肯定会起作用)。

对于每个合法配对的A[i], B[j]，有两种选择：

• 拿着它，尝试将任何A[x], B[y]与x>i和y<j配对是非法的。
• 不是拿着它，而是看看其他可能的配对

通过将法律对增量地添加到一组配对中，最终将耗尽所有合法配对。路径中有效配对的数量是您所寻求的最大化，此算法将查看所有可能的答案，并保证工作。

伪码：

function search(currentPairs):
    bestPairing = currentPairs
    for each currently legal pair:
        nextPairing = search(copyOf(currentPairs) + this pair)
        if length of nextPairing > length of bestPairing:
           bestPairing = nextPairing
    return bestPairing

最初，您将传递一个空的currentPairs。寻找法律对是一个棘手的问题。您可以使用三个嵌套循环来查看所有的A[x]、B[y]，最后，如果是A[x] < B[y]，则查看所有currentPairs是否有交叉线(这大约是O(n^3)的成本)；或者您可以使用一个有效配对的布尔矩阵，您可以在每个级别更新它们(计算时间更短，直到O(n^2)，但在内存方面更昂贵)。

Answer 3

这里是一个Java实现。

为了方便起见，我首先构建一个映射，其中包含列表(数组)a到b的每个条目的有效选择。

然后循环遍历列表，对连接到b进行无选择和有效的选择。

由于您不能返回而不跨越现有的连接，所以我会跟踪b中分配的最大连接。

至少对这两个例子有效..。

public class ListMatcher {

    private int[] a ;
    private int[] b ;

    private Map<Integer,List<Integer>> choicesMap;

    public ListMatcher(int[] a, int[] b) {
        this.a = a;
        this.b = b;
        choicesMap = makeMap(a,b);
    }

    public Map<Integer,Integer> solve() {
        Map<Integer,Integer> solution = new HashMap<>();
        return solve(solution, 0, -1);
    }

    private Map<Integer,Integer> solve(Map<Integer,Integer> soFar, int current, int max) {

        // done
        if (current >= a.length) {
            return soFar;
        }


        // make no choice from this entry
        Map<Integer, Integer> solution =  solve(new HashMap<>(soFar),current+1, max);

        for (Integer choice : choicesMap.get(current)) {

            if (choice > max) // can't go back
            {
                Map<Integer,Integer> next = new HashMap<>(soFar);
                next.put(current, choice);
                next = solve(next, current+1, choice);
                if (next.size() > solution.size()) {
                    solution = next;
                }
            }
        }
        return solution;
    }


    // init possible choices
    private Map<Integer, List<Integer>> makeMap(int[] a, int[] b) {
        Map<Integer,List<Integer>> possibleMap = new HashMap<>();
        for(int i = 0; i < a.length; i++) {
            List<Integer> possible = new ArrayList<>();
            for(int j = 0; j < b.length; j++) {
                if (a[i] < b[j]) {
                    possible.add(j);
                }
            }
            possibleMap.put(i, possible);
        }
        return possibleMap;
    }

    public static void main(String[] args) {
        ListMatcher matcher = new ListMatcher(new int[]{3,7,2,1,5,9,2,2},new int[]{4,5,10,1,12,3,6,7});
        System.out.println(matcher.solve());
        matcher = new ListMatcher(new int[]{10,1,1,1,1,1,1,1},new int[]{2,2,2,2,2,2,2,101});
        System.out.println(matcher.solve());
    }
}

输出

(格式:零基index_in_a=index_in_b)

{2=0, 3=1, 4=2, 5=4, 6=5, 7=6}
{1=0, 2=1, 3=2, 4=3, 5=4, 6=5, 7=6}

您的解决方案没有被选中，因为没有选择的解决方案是首先选择的。您可以通过先处理循环来改变这一点..。