加权二分图中寻找最优匹配的快速算法

Question

加权二分图中寻找最优匹配的快速算法

5

我需要有效地解决作业问题（给定完全加权二分图，选择最大总权重的完美匹配），目前我一直在使用这里的O（n ^ 3）版本 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm 。然而，我阅读的一篇论文提到了“更有效的方法”，该方法在“用于稠密和稀疏线性分配问题的最短增广路径算法”中，但可惜的是它被设置了付费墙。是否有任何更快的算法应该让我知道（无论是渐近的，还是具有更小的常数/更均匀的内存访问或其他什么因素）？与匈牙利方法不同，我正在使用浮点权重而不是整数权重，这似乎对于匈牙利方法并不重要，但对于更快的整数实现可能会有影响。任何相关链接将不胜感激。

- theotherphil

2

您可以根据该文章下载代码：http://www.assignmentproblems.com/LAPJV.htm - Evgeny Kluev

1

你要解决的问题规模是多少？匈牙利算法可以通过优先队列加速到n^2*logn，但对于较小的规模可能得不偿失。 - Ants Aasma

几百个顶点。这种加速会非常有用。你有参考资料吗？ - theotherphil

1

我猜@AntsAasma是在指这篇文章。 - Ilya Orson

1个回答

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

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

- nichole · Accepted Answer

有一些论文提出了用于加权二分图的快速算法。

最近的一篇论文Ramshaw和Tarjan，2012年《不平衡二分图中的最小成本分配问题》提出了一种名为FlowAssign and Refine的算法，解决了最小成本、不平衡、二分图分配问题，并使用权重缩放来解决完美和不完美的分配问题，但运行时间复杂度不是增量式的，为O(m * sqrt(n) * log(n * C))，其中m是图中的边数，n是要匹配的两个图中节点的最大数量，C是大于等于最大边权重的常数，且大于等于1。

权重缩放是使算法在匹配节点数量s方面表现更好的原因。

在20世纪90年代初，还可以找到其他快速解决方案。1993年的一篇名为“QuickMatch：用于分配问题的非常快速算法”的论文由Lee和Orlin提出了一种算法，他们估计其运行时间与图中弧的大小成线性关系。 http://jorlin.scripts.mit.edu/docs/publications/WP4-quickmatch.pdf QuickMatch算法将分配问题解决为n个最短路径问题的序列。他们使用起点节点和终点节点之间的交替最短路径以及启发式方法来减少计算量。作者通过实证结果和与理论上界算法的比较来估计平均运行时间复杂度。他们发现他们的算法是与图边数（也称为弧）成线性关系的，但该算法不如Bertsekas的“正反向拍卖”算法表现好，后者也使用交替最短路径。后者的参考文献未在论文中打印，但可能在“分配问题的反向拍卖算法”，Castanon，1992，MACS离散数学和计算机科学系列中。

伯克利分割基准代码在比较与人工绘制边界的分割结果时，还使用了二分图匹配算法。他们使用了Goldberg CSA包，这个包被报告为具有与图形大小线性的运行时间，并解决稀疏最小成本分配问题。参考文献是1993年Goldberg和Kennedy撰写的“一种有效的成本缩放算法用于指派问题”和Cherkassky和Goldberg的“关于实现PushRelabel方法的最大流问题”，第四届整数规划和组合优化会议论文集，1995年5月，第157-171页。