我正在寻找匈牙利算法的变体（我认为），它将N人与自己配对，不包括自我配对和反向配对，其中N是偶数。
例如，给定N 0 - N 6和每对成本的矩阵C ，我如何获得 3 个最低成本对的集合？
C = [ [ - 5 6 1 9 4 ]
[ 5 - 4 8 6 2 ]
[ 6 4 - 3 7 6 ]
[ 1 8 3 - 8 9 ]
[ 9 6 7 8 - 5 ]
[ 4 2 6 9 5 - ] ]
在此示例中，生成的对将是：
N 0 , N 3
N 1 , N 4
N 2 , N 5
输入此内容后，我现在想知道是否可以仅增加矩阵“下半部分”中的成本值……甚至更好，将其删除。
是否有适用于非方阵的匈牙利语变体？
或者，是否有另一种算法可以解决问题的这种变化？
增加下半部分的值可能会导致错误的解决方案。您可以将其视为上半部分的角坐标（在您的示例中为坐标 0,1 和 5,6）将始终被视为最小 X 对，其中 X 是矩阵的大小。
我找到最小 X 对的解决方案
采用标准的匈牙利算法
您可以将对角线设置为大于未更改矩阵中元素的总和的值 - 此步骤可以让您加快实现速度，具体取决于您的实现如何处理空值。
1）标准算法的第一步是遍历每一行，然后是每一列，分别减少每一行和每一列，使得每一行和每一列的最小值为零。这是不变的。
该解决方案的一般原则是围绕对角线镜像原始算法的每个后续步骤。
2) 算法的下一步是选择行和列，以便每个零都包含在选择中，使用最少的行和列数。我对算法的更改意味着在选择行/列时，还要选择围绕该对角线镜像的列/行，但出于所有目的将其视为一行或一列选择，包括计算对角线（这将是这些的交集）镜像行/列选择对）只被选择一次。
3）下一步是检查您是否有正确的解决方案 - 这在标准算法中意味着检查选择的行数和列数是否等于矩阵的大小 - 在您的示例中，如果选择了六行和列. 然而，对于这种变化，在计算何时结束算法时，将每一行/列镜像选择对视为单个行或列选择。如果您有正确的解决方案，请在此处结束算法。
4）如果行数和列数小于矩阵的大小，则找到最小的未选中元素，称其为k。从所有未覆盖的元素中减去 k，并将其添加到所有被覆盖两次的元素（再次，将镜像的行/列选择计为单个选择）。
我对算法的更改意味着在更改值时，您将相同地更改它们的镜像值（这应该作为镜像选择过程的结果自然发生）。
然后回到第 2 步，重复第 2-4 步，直到第 3 步指示算法完成。
这将导致成对的镜像答案（即坐标——要获得这些坐标的值，请参考原始矩阵）——您可以安全地任意删除每对的一半。
要更改此算法以找到最小 R 对，其中 R 小于矩阵的大小，请将步骤 3 中的停止点减少到 R。此更改对于回答您的问题至关重要。
