c++ - C++中矩阵的最小值

Question

我有一个 std::vector<std::vector<type T>> matrix ，我插入元素 type T到这个矩阵，我对这些元素逐行做一些说明。我还需要在每次迭代中以最低成本删除元素。

我创建了一个 std::priority_queue<Costelement, std::vector<Costelement>, Costelement::Comparekeys> Costvec;其中:

 struct Costelement
{
    int row;
    int column;
    std::vector<double> cost;

    struct CompareCosts
    {
        bool operator()(const Costelement &e1, const Costelement &e2)
        {
            return (e1.cost > e2.cost);
        }
    };
};

哪里row和 column是元素在 matrix 中的位置有相应的成本。但是，当我从 matrix 中删除具有最小键的元素时, 元素在相应 row 中的位置改变。我用了std::min_element在 matrix 的每次迭代中但这是非常昂贵的。我们如何才能有效地对这种情况进行建模？

Answer 1

A std::priority_queue默认情况下只是一个保持排序状态的 std::vector。从队列中插入和删除元素仍然很昂贵，正如您所注意到的，当您从 中插入或删除元素时，您可能需要更新队列中的所有 Costelements matrix 以反射(reflect)新的位置。但是，您也可以通过将优先级队列设为二维来提高效率，如下所示:

std::priority_queue<std::priority_queue<Costelement, ...>, ...> cost_matrix;

基本上，内部优先级队列对单个行的列的成本进行排序，然后外部优先级队列应该对整行的成本进行排序。让我们创建 ColumnCost 和 RowCost 结构:

struct ColumnCost {
    int column;
    double cost;

    friend bool operator<(const ColumnCost &a, const ColumnCost &b) {
        return a.cost > b.cost;
    }
};

struct RowCost {
    int row;
    std::priority_queue<ColumnCost> columns;

    friend bool operator<(const RowCost &a, const RowCost &b) {
        return a.columns.top() > b.columns.top();
    }
};

std::priority_queue<RowCost> cost_matrix;

现在您可以轻松地从costmatrix 中获取最低成本元素，它返回包含最低成本元素的RowCost，然后您获得ColumnCost 成本最低的那个:

const auto &lowest_row = cost_matrix.top();
const auto &lowest_column = lowest_row.columns.top();
int row = lowest_row.row;
int column = lowest_column.column;

当您现在从 matrix 中插入或删除元素时，您将以相同的方式从 cost_matrix 中插入或删除元素。您仍然需要更新 row 或 column 坐标，但现在工作量少了很多。唯一需要注意的是，如果您更新添加或删除元素到 RowCost 的优先级队列，您需要从 cost_matrix 中删除并重新插入整行code> 以确保外部优先级队列保持正确排序。

另一种可能的优化是使用 std::priority_queue 来保持行排序，但使用 std::min_element() 来跟踪每个行的最小值个人行。这大大减少了存储 cost_matrix 所需的内存量，并且您只需要调用 std::min_element() 来重新计算行的最小成本元素你改变那一行。