2

我一直在尝试实现 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)？

4

1 回答 1

0

这个库在 O(n^4) 中实现它。他们没有声称他们的实现是 O(n^3)，但他们只是提到匈牙利算法是 O(n^3)。

于 2018-03-19T17:39:28.233 回答