ttn*_*hns 6 algorithm graph variable-assignment
匈牙利语或Kuhn-Munkres算法(这里的良好描述)将来自两组(分别为n和m个对象,n> = m)的对象配对,使得配对对象之间的总体"差异"(或分配的"成本")最小.算法的一个特征并不适合我:它只进行详尽的配对,因为它会将所有 m个物体与n个物体配对.取而代之的是,我希望能够创建任意数量 k对(k <= m),总体成本最低.例如,有一个50x30的输入成本矩阵; Kuhn-Munkres将最佳地创造30对.虽然我需要只有20对才能最佳地创建.
可以对匈牙利算法进行任何修改,或者可能是另一个算法吗？我非常感谢你的回答.
以下是一些值得思考的想法：
1) 假设您写下 n 列 m 行的成本矩阵。如果 n 大于 m，则添加具有恒定大成本的填充行以使其成为正方形。行和列的最小成本分配现在将通过将某些列与填充行匹配来丢弃它们。假设您现在添加一个填充列，其对于普通行的成本非常低，而对于填充列的成本则恒定较大。该解决方案现在会将适当的行之一与该列相匹配，以利用非常低的成本。这减少了与合理内容匹配的行数。我认为如果你添加 mk 这样的列，你最终会得到一个最小成本匹配，它实际上只分配 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 列未配对（即与零单元格配对）。
分配解是否有可能选择了 sxs 右下区域中的任何单元格？考虑任何此类任务。为了证明必须选择左上区域中的至少一个单元格，假设没有选择任何单元格。然后我们必须以某种方式从前 n 行的每一行中选择一个单元格，大概是通过从右上角区域中选择单元格来实现。每个这样的单元格必须位于单独的列中，但是右上角区域中只有 s 列，这还不够，因为对于要跳过的每个匹配，我们只需要一列，并且我们在此使用了一列区域已填充右下区域中的单元格。因此，假设解决方案选择了原始左上区域中的至少一个单元格和右下区域中的至少一个单元格。选择其他两个单元格，使其成为正方形的四个角。这些单元格无法选择。如果我们选择这些单元格而不是当前选择的两个单元格，我们会得到不同的解决方案。这两个新单元格是右上角的 0 单元格和左下角的 100 单元格。他们将替换主矩阵中右下角的 100 个单元格和值大于零的单元格。因此，这将使我们假设的解决方案更好，因此任何包含右下区域单元格的解决方案都不是最佳解决方案，并且分配算法不会将其返回给我们。
因此，这种添加 0 列然后添加大值行的技巧将产生一个分配算法解决方案，该解决方案确实会为添加的每个（行、列）省略原始解决方案中的一个匹配。
2）分配问题是http://en.wikipedia.org/wiki/Minimum-cost_flow_problem的一个特例。我认为您想要一个将 k 个单位从行转移到列的最小成本流程，因此您可以尝试像这样解决它。
3）最小成本流问题是线性规划的一个特例。我认为你可以写一个线性程序，将 [0,1] 范围内的数字分配给矩阵的单元格，使得每行和每列的总和不超过 1，并且所有单元格的总和为 k。目标函数就是每个单元格中的数量乘以其成本。