algorithm - 在二进制矩阵中查找 "generalized diagonal"

Question

NXN 矩阵中的“广义对角线”是 N 个单元格的选择，这样:

1. 从每一行和每一列中只选择一个单元格
2. 每个选定的单元格都包含一个非零值

我正在寻找一种算法来在 O(n^3) 中找到广义对角线。在我看来，以下动态规划算法“足够好”，但我不确定如何分析其复杂性。

Set<Set<Integer>> failedCache = new HashSet<Set<Integer>>();

List<Integer> find(int[][] matrix, Set<Integer> used, int row) {
    int N = matrix.length;
    if (failedCache.contains(used))
        return null;

    if (row == N) return new ArrayList<Integer>();

    for (int col = 0; col < N; ++col) {
        if (matrix[row][col] == 0)
            continue;

        if (used.contains(col))
            continue;

        Set<Integer> newUsed = new HashSet<Integer>(used);
        newUsed.add(col);
        List<Integer> answer = find(matrix, newUsed, row + 1);
        if (answer != null) {
            answer.add(col);
            return answer;
        }
    }

    failedCache.add(used);
    return null;
}

Answer 1

该算法在最坏情况指数时间内运行，因为在以下矩阵上

 11111
 11111
 11111
 11111
 00000

它将尝试大约 n!可能的组合。

对于多项式时间解，使用矩阵创建二分图，并找到 perfect matching .

例如用矩阵

 011
 101
 001

你创建图表

 A    X
 B    Y
 C    Z

边为 A->Y、A->Z、B->X、B->Z、C->Z。