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

Question

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

6

匈牙利算法或Kuhn-Munkres算法（好的描述在这里）将两个集合（分别为n和m个对象，其中n>=m）中的对象进行配对，使得配对对象之间的总“差异”（或“分配成本”）最小。然而，算法的一个特点并不适合我：它只进行穷举匹配，也就是说，它将所有的m个对象都与一些n个对象进行配对。相反，我希望能够创建任意数量的k个配对（k<=m），使得总成本最小。例如，有一个50x30的输入成本矩阵；Kuhn-Munkres将最优地创建所有30对。而我只需要最优地创建20对。

是否有任何修改匈牙利算法以允许此操作，或者可能有完全不同的算法可以实现？我非常感谢您的回答。

- ttnphns

2个回答

0

也许你的方法是错误的，但匈牙利算法仅适用于二分图。对于一般（非二分图）图形（即加权匹配），请参见http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm。或者你想作弊，只给出最大成本对匹配的前十名？

- Micromega

我的图是完全二分图：输入是一个nxm的矩形距离矩阵。匈牙利算法可以产生所有n或m（较小者）对，最小化对内距离之和；而我需要相同的最小化，只是我想能够“提取”更少的对。 - ttnphns

@ttnphns：但那是错误的算法。也许你想要寻找 Floyd-Warshall 算法？它可以找到所有配对吗？或者你想要制作一个随机配对算法？ - Micromega

我并没有提出任何算法，让你能够称之为错误。我明确表示我正在寻找具有以下属性的匹配（配对）算法：输入是N个实体和M个实体之间的NxM距离矩阵。在其中找到K个元素 - 每行和每列最多只有1个元素 - 并且K是自定义数字，介于1和min（N，M）之间，以便这些元素的总和最小化。你知道这样的算法吗？ - ttnphns

据我理解，这是匈牙利算法。 - Micromega

2

是的，但匈牙利算法只允许K=min(N,M)。它不允许自定义K。至少根据我从各种来源所了解到的情况是这样。 - ttnphns

这意味着完美匹配是不可能的，可以在这里查看：http://wilanw.blogspot.com/2009/09/maximumminimum-weighted-bipartite.html - Micromega

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mcdowella · Accepted Answer

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

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。其余单元格是在填有?的正方形内部进行3x3匹配。

好的 - 这里是添加列和行以产生所需匹配的证明：

假设您拿一个具有值为0 < x < 100的成本矩阵，并像上面那样添加s列和0和100的行边框，然后将其作为分配问题进行求解。在0和100的边界处绘制两条线，将它们延伸到将正方形划分为四个区域的位置，其中左上角的区域是原始矩阵。如果分配算法没有选择右下角区域中的任何单元格，则它选择了顶部右侧区域中的s个单元格（以选取最右侧的s列），因此原始成本矩阵中左上角区域中的s行与零列中的单元格配对。顶部区域中的其他行必须与非零列配对，因此在原始区域中留下s行（即与零单元格配对的行）和s列未配对。

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

因此，添加0和大值的行以产生一种分配算法解决方案，该解决方案省略了每个添加的（行，列）对原始解决方案的一个匹配。

2）分配问题是最小费用流问题的一种特殊情况。我认为您需要从行到列传输k单位的最小成本流，因此可以尝试像这样解决它。

3) 最小费用流问题是线性规划的特殊情况。我认为您可以编写一个线性规划，将数字分配到矩阵单元格中，范围在[0,1]之间，使得每行和每列的总和不超过1，并且所有单元格的总和为k。然后，目标函数就是每个单元格中的数字乘以其成本。