the*_*hil 5 algorithm optimization graph-algorithm
我需要有效地解决分配问题(给定一个完整的加权二分图,选择最大总重量的完美匹配)并且我一直在使用这里的O(n ^ 3)版本http://community.topcoder.com/tc？module = Static&d1 = tutorials&d2 = hungarianAlgorithm.然而,我读过的一篇论文在"密集和稀疏线性分配问题的最短增强路径算法"中提到了一种"更有效的方法",这是一个付费墙背后的遗憾.有没有我应该注意的更快的算法(渐近,或者只是更小的常数/更均匀的内存访问或其他什么)？我正在使用浮点权重而不是整数权重,这对于匈牙利方法似乎并不重要,但对于更快的整数实现可能是一个问题.任何相关的链接将不胜感激.
有一些论文有加权二分图的快速算法.
最近的一篇论文Ramshaw和Tarjan,2012年"关于非平衡二分图中的最小成本分配"提出了一种称为FlowAssign和Refine的算法,该算法解决了最小成本,非平衡的二分分配问题,并使用权重缩放来解决完美和不完美的分配问题,但不是增量的,运行时复杂度为O(m*sqrt(n)*log(n*C))其中m是图中边的数量(也就是弧),n是节点中的最大节点数两个要匹配的图形,C是大于或等于最大边缘权重的常数,并且大于或等于1.
权重缩放允许算法相对于s获得更好的性能,其中s是匹配节点的数量.
其他快速解决方案可以在1990年代早期找到.Lee和Orlin在1993年发表的一篇名为"QuickMatch:一种非常快速的分配问题算法"的论文提出了一种算法,根据弧线,算法的运行时间与曲线图的大小有关. http://jorlin.scripts.mit.edu/docs/publications/WP4-quickmatch.pdf
QuickMatch算法将分配问题解决为n个最短路径问题的序列.它们使用原始节点和目标节点之间的交替最短路径以及启发式来减少计算次数.作者通过实证结果和理论上有界算法的比较来估计平均运行时间的复杂性.他们发现他们的算法是线性的,具有图形边缘的数量(也就是弧线),但算法的效果不如Bertsekas的"前向 - 反向拍卖"算法,后者也使用交替的最短路径.后者的参考文献没有印在论文中,但可能出现在"转让拍卖算法中的任务问题",Castanon,1992,MACS Seris in Discrete Mathematics and Computer Science
还有一种算法,Berkeley分割基准代码在评估分割结果的过程中用于二分匹配,与人类绘制的边界相比较. http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/ 他们使用Goldberg CSA软件包 http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/ 据报道,代码/ CSA ++ /具有与图形大小成线性的运行时,并解决了稀疏的最小成本分配问题.这些参考文献是"分配问题的有效成本缩放算法",1993年由Goldberg和Kennedy以及Cherkassky和Goldberg撰写,"关于实现最大流动问题的PushRelabel方法",Proc.Fourth Integer Programming and Combinatorial Optimization Conf.,pp.157-171,1995年5月.