algorithm - 需要配对算法 - 基于匈牙利语？

Question

匈牙利或 Kuhn-Munkres 算法(很好的描述 here)将来自两组的对象配对(分别为 n 和 m 对象，n>=m ) 以便配对对象之间的总体“差异”(或分配的“成本”)最小。然而，该算法的一个特性并不适合我:它只进行详尽的配对，从某种意义上说，它将所有 m 个对象与 n 个对象中的一些对象配对。取而代之的是，我希望能够创建任意数量 k 对 (k<=m)，同时总成本最低。例如，有一个 50x30 的输入成本矩阵； Kuhn-Munkres 将以最佳方式创建所有 30 对。虽然我只需要 20 对就能以最佳方式创建。

是否可以对匈牙利算法进行任何修改以允许这样做，或者可能完全是另一种算法来做到这一点？我非常感谢您的回答。

Answer 1

以下是一些需要考虑的想法:

1) 假设您写下了包含 n 列和 m 行的成本矩阵。如果 n 大于 m，则添加具有恒定大成本的填充行以使其成为正方形。行和列的最小成本分配现在将通过将它们与填充行匹配来丢弃一些列。假设您现在添加一个填充列，普通行的成本非常低，填充列的成本恒定。该解决方案现在会将适当的行之一与该列匹配，以利用非常低的成本。这减少了与某些合理匹配的行数。我认为如果您添加 m-k 个这样的列，您最终会得到一个最小成本匹配，它实际上只分配了 k 行。

Here is an example of pairing 3 with 3 in 5x5, assuming ?
marks problem-specific values > 0 but < 100 (you may 
need more extreme values than 0 and 100 to force the sort of
solution you want depending on what your data values are).

?   ?   ?   ?   ?   0   0
?   ?   ?   ?   ?   0   0
?   ?   ?   ?   ?   0   0
?   ?   ?   ?   ?   0   0
?   ?   ?   ?   ?   0   0
100 100 100 100 100 100 100
100 100 100 100 100 100 100

我希望最佳解决方案将使用 远处的两个0 右边和底行的两个 100。剩余的细胞 在 ?s 的正方形内有一个 3 x 3 匹配

好的 - 这是一个证明，如上添加列然后添加行会产生您想要的匹配类型:

假设您采用一个值为 0 < x < 100 的成本矩阵，并如上所述添加 s 列和 0 和 100 行的边框，然后将其作为分配问题解决。在 0 和 100 的边界处画两条线，将它们延伸以将正方形切割成四个区域，其中左上角的区域是原始矩阵。如果分配算法没有选择右下区域的任何单元格，那么它会选择右上区域的 s 个单元格(选择最右边的 s 列)，所以左上区域的原始成本矩阵中的 s 行是与零列中的单元格配对。顶部区域中的其他行必须与非零列配对，因此您在原始区域中有一个匹配，留下 s 行和 s 列，未配对(即与零单元格配对)。

分配解决方案是否有可能选择了 s x s 右下角区域中的任何单元格？考虑任何这样的任务。为证明必须选择左上区域中的至少一个单元格，假设未选择任何单元格。然后我们必须以某种方式从前 n 行的每一行中选择一个单元格，大概是从右上角的区域中选择单元格。每个这样的单元格必须在一个单独的列中，但右上角区域只有 s 列，这是不够的，因为我们只需要一列来表示我们要跳过的每个匹配项，而我们在此中使用了一列region 已经填充在右下方区域的一个单元格中。因此，假设解决方案选择了原始左上区域中的至少一个单元格和右下区域中的至少一个单元格。选择另外两个单元格，使其成为正方形的四个角。无法选择这些单元格。如果我们选择那些单元格而不是当前选择的两个单元格，我们会得到不同的解决方案。这两个新单元格是右上角的 0 单元格和左下角的 100 单元格。他们将替换右下角的 100 单元格和主矩阵中值大于零的单元格。所以这会使我们假设的解决方案更好，所以任何在右下区域包含单元格的解决方案都不是最佳解决方案，并且分配算法不会将其返回给我们。

因此，这种先添加 0 列然后添加大值行的技巧将产生一种分配算法解决方案，该解决方案确实会为每个添加的(行、列)从原始解决方案中省略一个匹配项。

2) 分配问题是 http://en.wikipedia.org/wiki/Minimum-cost_flow_problem 的特例.我想你想要一个最小的成本流，将 k 个单位从行转移到列，所以你可以尝试像这样解决它。

3) 最小成本流问题是线性规划的一个特例。我认为您可以写下一个线性程序，将 [0,1] 范围内的数字分配给矩阵的单元格，使得每一行和每一列的总和不超过 1，并且所有单元格的总数为 k。目标函数就是每个单元格中的数量乘以其成本。