匈牙利算法与相互对？

-4

我试图使用匈牙利算法的以下实现：http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm。匈牙利算法与相互对？

我想修改这个算法，使我可以配对了一套与自身。也就是说，如果“a”被分配给“b”，“b”也被分配给“a”。我唯一的想法是改变以下内容。

for (int cx = x, cy = y, ty; cx != -2; cx = prv[cx], cy = ty) 
    { 
      yx[cy] = cx; 
      xy[cx] = cy; 
    }

以下几点：

for (int cx = x, cy = y, ty; cx != -2; cx = prv[cx], cy = ty) 
    { 
      yx[cy] = cx; yx[cx]=cy; 
      xy[cx] = cy; xy[cy]=cx; 
    }

因此，该算法总是检查其中的配对是相互的路径。但是，我确信这是错误的 - 代码通常是段错误。

我试图通过将if (max_match == n)更改为更宽松的约束来解决此问题，如if (max_match >= n-1)，以便该算法具有亚完美匹配的内容。这有时会起作用，并且当它出现时，它会像我想要的那样创建一些相互配对，但是某些顶点不会配对。并且仍然存在分段错误。

那么，有没有什么办法来解决这个问题呢？还有其他更适合的算法吗？

来源

2014-12-13 Kenneth Woods

匈牙利语算法计算加权双方匹配。你正在尝试做一些不同的事情，而这完全不清楚。 – tmyklebu 2014-12-13 03:39:52

我仍然试图做这样的匹配。例如，如果我有六个人a，b，c，d，e，f和我被赋予了每个可能配对的“成本”，我想要找到如何将这六个人分成三对成本。它就像是一个加权的二部分匹配两个相等的集合，约束配对是相互的。有没有不同的算法呢？ – 2014-12-13 04:53:24

这是nonbipartite匹配。是的，有一个有效的算法，但它不是双方匹配。 – tmyklebu 2014-12-13 17:39:20

我想你想要的是不是偶一图的最大匹配的版本。在http://en.wikipedia.org/wiki/Blossom_algorithm有一个算法描述，最后一段讨论加权的情况。你希望有一个最小的成本匹配，但是每个最大匹配都有相同的边数，所以如果你否定每个链接的成本，或者从某个非常大的常量中减去成本，就把最小值变成最大值。

一般的最大问题是充分恒定的，我认为你将有麻烦匈牙利算法来做到这一点，因为如果你能与匈牙利算法的人这样做不会发现的一般问题那么复杂。

来源

2014-12-13 05:48:02 mcdowella

我不知道为什么你不能只使用了“正常”匈牙利算法两侧的同一组，并指定“无限”与自身的每个元素的配对。这会给你一个最大的配对，并保证没有人与他自己匹配。

来源

2015-03-16 17:46:10

该问题被称为最佳非二部匹配。经典的参考文献是： DERIGS，U.（1988）。用最短路径技术解决nonbipartite匹配问题。运筹学年报13,225-261。对于小集合，更简单的方法可能就足够了。请参阅： https://gis.stackexchange.com/questions/179559/how-to-group-10k-points-into-closest-pairs 有一个R软件包nbpMatching可解决此问题。

顺便说一句，如果你试图简单地用一个双向匹配算法，并把重罚的配对与自己，你没有得到一致的配对。原因是更优化的安排可以是A与B'配对，B与C'配对并且C与A'配对，或者类似的这种安排。

来源

2016-04-27 17:20:56 hutch

匈牙利算法与相互对？

回答

相关问题