1

我正在 Python 3.4 中从头开始编写匈牙利算法，并且遇到了关于覆盖零的最佳行的问题。

我从其 Wikipedia 页面中获取了算法的定义，这是查找覆盖所有零的最小行的代码：

def minZeroLines(matrix):

    markMatrix = [] #first for marked rows, second for marked columns

    for row in range(len(matrix)):
        markMatrix.append([])
        for col in range(len(matrix)):
            markMatrix[row].append("")

    for row in range(len(matrix)):
        for col in range(len(matrix)):
            if matrix[row][col] == 0 and ("*" not in [i[col] for i in markMatrix] and "*" not in markMatrix[row]):
                markMatrix[row][col] = "*"

    print(markMatrix)

    rowColMark = [[],[]] #1st rows, 2nd cols

    for i in range(len(matrix)):
        rowColMark[0].append("")
        rowColMark[1].append("")

    for row in range(len(markMatrix)):
        if "*" not in markMatrix[row]:
            rowColMark[0][row] = "x"

    print(rowColMark)

    for row in range(len(markMatrix)):
        if rowColMark[0][row] == "x":
            for col in range(len(matrix)):
                if matrix[row][col] == 0:
                    rowColMark[1][col] = "x"
                    for row2 in range(len(markMatrix)):
                        if matrix[row2][col] == 0 and markMatrix[row2][col] == "*":
                            rowColMark[0][row2] = "x"

    print(rowColMark)

    lineList = []

    for col in range(len(rowColMark[1])):
        if rowColMark[1][col] == "x":
            lineList.append("c"+str(col))

    for row in range(len(rowColMark[0])):
        if rowColMark[0][row] != "x":
            lineList.append("r"+str(row))

    print(rowColMark)
    print(lineList)
    return lineList

问题是，当我通过它运行下面的矩阵时，在初始分配零作为找到覆盖它们的最少行的第一步时，选择了 matrix[1][1] 处的零。这会导致函数稍后标记所有行，这意味着它们不会被排列，即使行矩阵 [1] 显然应该是。

matrix = [[0, 0, 16, 16, 16, 16, 16],
      [0, 0, 0, 0, 0, 0, 0],
      [0, 0, 16, 16, 16, 16, 16],
      [0, 0, 16, 16, 16, 16, 16],
      [0, 0, 16, 16, 16, 16, 16],
      [0, 0, 16, 16, 16, 16, 16],
      [0, 0, 16, 16, 16, 16, 16]]

这是似乎导致问题的部分：

for row in range(len(matrix)):
    for col in range(len(matrix)):
        if matrix[row][col] == 0 and ("*" not in [i[col] for i in markMatrix] and "*" not in markMatrix[row]):
            markMatrix[row][col] = "*"

我认为必须有一些我错过的条件会阻止分配零，但这在我查看的描述和其他地方没有详细说明。有谁知道我做错了什么？

4

0 回答 0