非方阵下Hungarian Algorithm前两步实现崩溃问题求助

问题背景 #

正在完成大学算法课程作业，实现指派问题的匈牙利算法，已完成前两步编码：

• 对每一行，用该行每个元素减去行内最小值；
• 对每一列，用该列每个元素减去列内最小值。

程序可正常处理4x4方阵，但测试4x3这类非方阵时，初始输入数据显示错误（出现旋转后的表），随后程序崩溃，需要排查问题并修复以支持非方阵。

核心错误分析 #

1. 主函数行列定义与数据结构不匹配 #

主函数中定义Row=4、Column=3，但实际初始化的data是3行4列的矩阵（3个vector，每个包含4个元素），行列数完全搞反。同时输出初始数据时使用data[j][i]，将行列索引颠倒，导致越界访问和显示错误。

2. 构造函数参数传递错误 #

创建AssignmentProblem对象时，错误地将行列参数传反：AssignmentProblem AP(data, Column, Row);，应该传递实际的行数和列数。

3. 行最小值计算逻辑的索引错误 #

MinRowCosts函数中，错误地使用data[j][i] - row_minimums[j]，正确逻辑应为data[i][j] - row_minimums[i]（遍历第i行的每个元素，减去该行的最小值），原代码导致矩阵被转置。

4. 列最小值计算的越界与索引错误 #

• ColumnMinimums函数中，遍历列时使用min_row_costs[i][j]，其中i作为列索引循环到Column，但min_row_costs的行数是Row，当Row≠Column时会触发越界访问。
• MinColumnCosts函数中，错误地以列数作为循环次数创建行，且索引逻辑颠倒，导致矩阵结构混乱。

5. 矩阵输出的索引错误 #

calculateCostMatrix中输出Min Row Costs时，使用min_row_costs[j][i]，将行列索引颠倒，导致显示的矩阵是转置后的结果。

修复后的完整代码 #

#include <iostream>
#include <vector>
#include <climits> // 补充INT_MAX的头文件

class AssignmentProblem
{
private:
    int Row;
    int Column;
    std::vector<std::vector<int>> data;
public:
    AssignmentProblem(std::vector<std::vector<int>> NewData, int NewRow, int NewColumn)
    {
        Row = NewRow;
        Column = NewColumn;
        data = NewData;
    }

    // 计算每行的最小值
    std::vector<int> RowMinimums(std::vector<std::vector<int>> data)
    {
        std::vector<int> row_minimums;

        for (int i = 0; i < Row; i++)
        {
            int minimum = INT_MAX;
            for (int j = 0; j < Column; j++)
            {
                if (data[i][j] < minimum)
                {
                    minimum = data[i][j];
                }
            }
            row_minimums.push_back(minimum);
        }

        return row_minimums;
    }

    // 执行行减最小值操作
    std::vector<std::vector<int>> MinRowCosts(std::vector<std::vector<int>> data)
    {
        std::vector<int> row_minimums = RowMinimums(data);
        std::vector<std::vector<int>> min_row_costs;

        for (int i = 0; i < Row; i++)
        {
            std::vector<int> row;
            for (int j = 0; j < Column; j++)
            {
                // 修正索引：当前行元素减当前行最小值
                row.push_back(data[i][j] - row_minimums[i]);
            }
            min_row_costs.push_back(row);
        }

        return min_row_costs;
    }

    // 计算每列的最小值
    std::vector<int> ColumnMinimums(std::vector<std::vector<int>> min_row_costs)
    {
        std::vector<int> column_minimums;

        for (int j = 0; j < Column; j++)
        {
            int minimum = INT_MAX;
            for (int i = 0; i < Row; i++)
            {
                // 修正索引：遍历第j列的所有行元素
                if (min_row_costs[i][j] < minimum)
                {
                    minimum = min_row_costs[i][j];
                }
            }
            column_minimums.push_back(minimum);
        }

        return column_minimums;
    }

    // 执行列减最小值操作
    std::vector<std::vector<int>> MinColumnCosts(std::vector<std::vector<int>> min_row_costs)
    {
        std::vector<int> column_minimums = ColumnMinimums(min_row_costs);
        std::vector<std::vector<int>> min_column_costs;

        for (int i = 0; i < Row; i++)
        {
            std::vector<int> row;
            for (int j = 0; j < Column; j++)
            {
                // 修正索引：当前元素减对应列的最小值
                row.push_back(min_row_costs[i][j] - column_minimums[j]);
            }
            min_column_costs.push_back(row);
        }

        return min_column_costs;
    }

    // 计算并输出各阶段矩阵
    std::vector<std::vector<int>> calculateCostMatrix(std::vector<std::vector<int>> data)
    {
        std::vector<std::vector<int>> min_row_costs = MinRowCosts(data);

        std::cout << "Min Row Costs = " << std::endl;
        for (int i = 0; i < Row; i++)
        {
            std::cout << "< ";
            for (int j = 0; j < Column; j++)
            {
                // 修正输出索引
                std::cout << min_row_costs[i][j] << " ";
            }
            std::cout << " >" << std::endl;
        }
        std::cout << std::endl;

        std::vector<std::vector<int>> cost_matrix = MinColumnCosts(min_row_costs);

        std::cout << "Cost Matrix = " << std::endl;
        for (int i = 0; i < Row; i++)
        {
            std::cout << "< ";
            for (int j = 0; j < Column; j++)
            {
                std::cout << cost_matrix[i][j] << " ";
            }
            std::cout << " >" << std::endl;
        }
        return cost_matrix;
    }
};

int main()
{
    // 修正行列定义：data实际是3行4列
    int Row = 3;
    int Column = 4;

    std::vector<std::vector<int>> data = {{11,12,18,40},{14,15,13,22},{11,17,19,23}};

    std::cout << "Data = " << std::endl;
    for (int i = 0; i < Row; i++)
    {
        std::cout << "< ";
        for (int j = 0; j < Column; j++)
        {
            // 修正输出索引
            std::cout << data[i][j] << " ";
        }
        std::cout << " >" << std::endl;
    }
    std::cout << std::endl;

    // 修正构造函数参数：传递正确的行数和列数
    AssignmentProblem AP(data, Row, Column);

    std::vector<std::vector<int>> costs = AP.calculateCostMatrix(data);

    return 0;
}

修复说明 #

1. 修正了主函数中行列数与数据结构的匹配问题，确保Row和Column对应实际矩阵的行列数；
2. 统一了所有函数中的索引逻辑，确保data[i][j]代表第i行第j列的元素；
3. 修复了行列最小值计算和矩阵输出时的索引错误，避免越界访问；
4. 补充了INT_MAX所需的<climits>头文件，避免编译警告。

内容的提问来源于stack exchange，提问作者Austin