我需要有效地解决分配问题（给定一个完整的加权二分图，选择一个具有最大总权重的完美匹配），并且我一直在使用来自这里http://community.topcoder.com的 O(n^3) 版本/tc?module=Static&d1=教程&d2=hungarianAlgorithm. 然而，我读到的一篇论文在“A shortest augmenting path algorithm for dense and sparse linear assignment questions”中提到了一种“更有效的方法”，遗憾的是它落后于付费墙。有没有我应该知道的更快的算法（渐近，或者只是使用更小的常量/更统一的内存访问或其他）？我正在使用浮点权重而不是整数权重，这对于匈牙利方法似乎并不重要，但对于更快的整数实现来说可能是一个问题。任何相关链接将不胜感激。
问问题
2813 次
1 回答
6
有几篇论文具有用于加权二分图的快速算法。
最近的一篇论文 Ramshaw 和 Tarjan，2012 “On Minimum-Cost Assignments in Unbalanced Bipartite Graphs”提出了一种称为 FlowAssign 和 Refine 的算法，它解决了最小成本、不平衡、二分分配问题，并使用权重缩放来解决完美和不完美的分配问题，但不是增量的，运行时复杂度为 O(m * sqrt(n) * log(n * C)) 其中 m 是图中的边数（也称为弧），n 是图中的最大节点数两个要匹配的图，C是一个常数，大于等于最大边权重，大于等于1。
权重缩放允许算法相对于 s 实现更好的性能，其中 s 是匹配节点的数量。
其他快速解决方案可以在 1990 年代初期找到。Lee 和 Orlin 于 1993 年发表的一篇名为“QuickMatch: A Very Fast Algorithm for the Assignment Problem”的论文提出了一种算法，他们估计该算法的运行时间在图的大小上以弧线表示有效。 http://jorlin.scripts.mit.edu/docs/publications/WP4-quickmatch.pdf
QuickMatch 算法将分配问题解决为一系列 n 最短路径问题。他们使用源节点和目标节点之间的交替最短路径以及启发式方法来减少计算次数。作者通过经验结果和与理论上有界算法的比较来估计平均运行时复杂度。他们发现他们的算法与图边（又名弧）的数量成线性关系，但该算法的性能不如 Bertsekas 的“正反向拍卖”算法，后者也使用交替最短路径。后面的参考文献没有印在论文中，但可能在“Reverseuctionalgorithms for assignment questions”，Castanon，1992，MACS Seris in Discrete Mathematics and Computer Science
还有一种算法，伯克利分割基准代码在评估分割结果期间与人工绘制的边界相比用于二分匹配。 http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/ 他们使用 Goldberg CSA 包 http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/ code/CSA++/ 据报道其运行时与图大小成线性关系，并解决了稀疏的最小成本分配问题。参考文献是“分配问题的有效成本缩放算法”，Goldberg 和 Kennedy 以及 Cherkassky 和 Goldberg 于 1993 年出版的“关于实现最大流量问题的 PushRelabel 方法”，Proc。第四次整数规划和组合优化会议，第 157-171 页，1995 年 5 月。
于 2016-05-18T00:51:09.053 回答