贪婪分配算法的复杂性

Question

赋值问题要求在给定的n乘n矩阵的不同行和列中找到一组具有最大可能和的n元素。在O(n^3)中，匈牙利算法可以得到最优解。然而，让我们考虑以下次优贪婪算法：

1. 选择剩余矩阵中的最大元素
2. 将此元素添加到结果集，即将该元素的行与其列匹配，并从矩阵中删除这些行和列。
3. 从第1步重复。

实现这种算法的有效数据结构是什么？如果只要求O(n^2 log(n))对所有元素进行排序，那么它的时间复杂度可以是O(n^2)吗？

Answer 1

一旦对元素进行了排序，就可以使用两个数组来跟踪已删除的行和列。在未经测试的Python中：

def greedy_max_match(weight):
    n = len(weight)
    row_deleted = [False] * n
    col_deleted = [False] * n
    sorted_weights = sorted(((weight[i][j], i, j)
                             for i in range(n) for j in range(n)),
                            reverse=True)
    for w, i, j in sorted_weights:
        if not row_deleted[i] and not col_deleted[j]:
            yield (i, j)
            row_deleted[i] = True
            col_deleted[j] = True