我一直在尝试实现匈牙利算法的0（n^3）版本。我偶然发现了munkres图书馆，他们声称运行时间为0（n^3）通过查看它们的代码，我不确定它们如何度量0（n^3），因为它看起来像0（n^4）。
def __step4(self):
"""
Find a noncovered zero and prime it. If there is no starred zero
in the row containing this primed zero, Go to Step 5. Otherwise,
cover this row and uncover the column containing the starred
zero. Continue in this manner until there are no uncovered zeros
left. Save the smallest uncovered value and Go to Step 6.
"""
step = 0
done = False
row = 0
col = 0
star_col = -1
while not done:
(row, col) = self.__find_a_zero(row, col)
if row < 0:
done = True
step = 6
else:
self.marked[row][col] = 2
star_col = self.__find_star_in_row(row)
if star_col >= 0:
col = star_col
self.row_covered[row] = True
self.col_covered[col] = False
else:
done = True
self.Z0_r = row
self.Z0_c = col
step = 5
print("In Step 4")
return step
def __find_a_zero(self, i0=0, j0=0):
"""Find the first uncovered element with value 0"""
row = -1
col = -1
i = i0
n = self.n
done = False
while not done:
j = j0
while True:
if (self.C[i][j] == 0) and \
(not self.row_covered[i]) and \
(not self.col_covered[j]):
row = i
col = j
done = True
j = (j + 1) % n
if j == j0:
break
i = (i + 1) % n
if i == i0:
done = True
return (row, col)
def compute(self, cost_matrix):
"""
Compute the indexes for the lowest-cost pairings between rows and
columns in the database. Returns a list of (row, column) tuples
that can be used to traverse the matrix.
:Parameters:
cost_matrix : list of lists
The cost matrix. If this cost matrix is not square, it
will be padded with zeros, via a call to ``pad_matrix()``.
(This method does *not* modify the caller's matrix. It
operates on a copy of the matrix.)
**WARNING**: This code handles square and rectangular
matrices. It does *not* handle irregular matrices.
:rtype: list
:return: A list of ``(row, column)`` tuples that describe the lowest
cost path through the matrix
"""
self.C = self.pad_matrix(cost_matrix)
self.n = len(self.C)
self.original_length = len(cost_matrix)
self.original_width = len(cost_matrix[0])
self.row_covered = [False for i in range(self.n)]
self.col_covered = [False for i in range(self.n)]
self.Z0_r = 0
self.Z0_c = 0
self.path = self.__make_matrix(self.n * 2, 0)
self.marked = self.__make_matrix(self.n, 0)
done = False
step = 1
steps = { 1 : self.__step1,
2 : self.__step2,
3 : self.__step3,
4 : self.__step4,
5 : self.__step5,
6 : self.__step6 }
while not done:
try:
func = steps[step]
step = func()
except KeyError:
done = True
# Look for the starred columns
results = []
for i in range(self.original_length):
for j in range(self.original_width):
if self.marked[i][j] == 1:
results += [(i, j)]
return results
这些是我正在查看的函数，我认为为了寻找零函数，复杂性是0（n ^ 2），因为它在STEP4中的while循环中被调用，所以它使得复杂性0（n ^ 3）。步骤4在计算中的while循环中调用，使得复杂性0（n ^ 4）。我想知道他们是如何声称拥有0（n^3）的？
最佳答案
这个库在o（n^4）中实现它。他们没有声称自己的实现是o（n^3），但他们只是提到匈牙利算法是o（n^3）。