贪婪分配算法的复杂性

Question

The assignment problem 要求在给定的 n×n 矩阵的不同行和列中找到一组具有最大可能总和的 n 元素。可以在O(n^3)中用匈牙利算法最优求解。但是，让我们考虑以下次优贪心算法：

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

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

Answer 1

O(n²logn) 的复杂性可以使用如下方法实现。

您最初存储 n 行和列中每一个的排序版本。（此存储的行和列将使用的确切结构将在本答案的后面阐明）请注意，即使您将根据值对它们进行排序在单元格中，单元格的值应该与它们的初始索引一起存储。初始索引将有助于删除行和列。（算法的第 2 步）

经过上面提到的预处理，有一个迭代n次的循环。在这个循环中将是你的算法的步骤。在每次迭代中；

第 1 步：检查每个排序行和列中的最大元素，更新全局最大元素的值和地址。

步骤2.1：将元素添加到结果array/list/etc，并从相应行和列的已排序行和列结构中移除。

步骤 2.2:遍历每个排序的行结构。对于每一行，我们需要删除一列。由于我们有矩阵和最大元素的地址，我们还可以访问我们要为每一行删除的列的确切值和地址。利用这一点，在每个排序的行结构中，假设它已排序，进行二进制搜索以找到该元素并将其删除。

事情是这样的！如果将这个排序的行结构存储为一个简单的数组，删除这个元素将花费 O(n) 时间，因为你必须将数组的剩余部分向左移动 1。我能想到的解决方案是使用结构类似于 STL 的 set。它实际上可以像二进制搜索一样在 O(logn) 中查找，并提供 O(logn) 时间的插入和删除。

Step 2.3: 同Step 2.2，这次遍历每个列结构。当我们删除一行时，我们从每一列中删除一个元素。然而，由于找到了地址（即行和列）和全局最大元素的值，我们知道我们要删除哪一行以及我们从每一列中删除的元素的值和地址。因此，对于每个列结构，我们从存储该列的排序版本的 STL 类集合数据结构中找到并删除该元素。

性能

预处理： 现在我们知道什么样的数据结构存储排序的行和列，我们可以说它需要 O(n²logn) 因为这些结构有 2n 个，我们在 O(logn) 时间内向每个结构插入 n 个元素。

第1步：有2n个排序结构，这意味着在O(logn)时间内访问它们的最大元素将有一个组合O(nlogn)时间复杂度。

步骤2.1：虽然结果数据保存在数据结构中，但假设它是一个数组，添加一个元素需要O(1)时间它。然而，这一步的总体复杂度为 O(logn)，因为我们需要从它所属的已排序行和列结构中删除最大元素。

步骤 2.2： 有 n 个排序的行结构，我们对其进行查找和删除操作，导致 O(nlogn)负担。

步骤 2.3： 具有 O(nlogn) 成本，与步骤 2.2 相同。

考虑到步骤2.1、2.2、2.3做了n次，算法的整体复杂度为O(n²logn).

实施

您可以在下面找到我上面提到的算法的完整实现，它似乎可以工作。该算法的要点是相同的，由于实现而发生了微小的变化，例如定义负无穷大或使用额外的 bool 向量来存储行或列是否被完全删除。（即我们不会费心查看其排序结构在剩余矩阵中寻找最大元素时）

#include <set>
#include <vector>
#include <iostream>
#define NEGATIVE_INFINITY -1

using namespace std;

vector< set< pair<int, int> > > sortedRows;
vector< set< pair<int, int> > > sortedCols;
vector< int > result;
void solve(const vector< vector< int > > &matrix)
{
    int n = matrix.size();
    vector<bool> rowNotDeleted(n, true), colNotDeleted(n, true);

    // Preprocessing
    for(int i=0; i < n; ++i)
    {
        sortedRows.resize(n);
        sortedCols.resize(n);
        for(int j=0; j < n; ++j)
        {
            sortedRows[i].insert( make_pair(matrix[i][j], j) );
            sortedCols[j].insert( make_pair(matrix[i][j], i) );
        }
    }

    for(int k=0; k < n; ++k)
    {
        set< pair<int, int> >::reverse_iterator it;

        // STEP 1: Find max. element
        int maxVal = NEGATIVE_INFINITY, maxRow = -1, maxCol = -1;
        for(int i=0; i < n; ++i)
        {
            if(rowNotDeleted[i])
            {
                it = sortedRows[i].rbegin();
                if(it->first > maxVal)
                {
                    maxVal = it->first;
                    maxRow = i;
                    maxCol = it->second;
                }
            }
        }

        for(int i=0; i < n; ++i)
        {
            if(colNotDeleted[i])
            {
                it = sortedCols[i].rbegin();
                if(it->first > maxVal)
                {
                    maxVal = it->first;
                    maxRow = it->second;
                    maxCol = i;
                }
            }
        }

        // STEP 2.1: Add max. element to result.
        result.push_back(maxVal);
        /*
         * Due to my implementation, removing it from
         * relevant sorted data structures can be done
         * in steps 2.2 and 2.3.
         */
//        sortedRows[maxRow].erase( make_pair(maxVal, maxCol) );
//        sortedCols[maxCol].erase( make_pair(maxVal, maxRow) );
        rowNotDeleted[maxRow] = false;
        colNotDeleted[maxCol] = false;

        // STEP 2.2: Remove cells of deleted col from sorted row structures
        for(int i=0; i < n; ++i)
        {
            sortedRows[i].erase( make_pair(matrix[i][maxCol], maxCol) );
        }

        // STEP 2.3: Remove cells of deleted row from sorted col structures
        for(int i=0; i < n; ++i)
        {
            sortedCols[i].erase( make_pair(matrix[maxRow][i], maxRow) );
        }
    }
}

int main()
{
    int n;
    cin >> n;

    // Read matrix
    vector< vector< int > > matrix(n);
    for(int i=0; i < n; ++i)
    {
        matrix[i].resize(n);
        for(int j=0; j < n; ++j)
        {
            cin >> matrix[i][j];
        }
    }

    solve(matrix);

    // Output results
    cout << result[0];
    for(int i=1; i < n; ++i)
    {
        cout << " " << result[i];
    }
    cout << endl;

    return 0;
}

Answer 2

一旦元素被排序，你就可以扫描，使用两个数组来跟踪删除的行和列。在未经测试的 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

贪婪分配算法的复杂性

Complexity of a greedy assignment algorithm

algorithm

mathematical-optimization

time-complexity

性能

实施