-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)，以便算法满足于次完美匹配。这有时会起作用，当它起作用时，它会像我想要的那样创建一些相互对，但有些顶点是不成对的。并且仍然存在分段错误。

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

4

3 回答 3

0

我认为您想要的是非二分图的最大匹配版本。在http://en.wikipedia.org/wiki/Blossom_algorithm有一个为此描述的算法，最后一段讨论了加权案例。您需要最小成本匹配，但每个最大匹配具有相同数量的边，因此如果您否定每个链接的成本，或从某个非常大的常数中减去成本，您会将最小值变为最大值。

一般的最大问题是足够恒定的，我认为你很难让匈牙利算法来做它，因为如果你能用匈牙利算法来做，人们就不会发现一般问题如此复杂。

于 2014-12-13T05:48:02.350 回答
0

我不知道为什么您不能在“正常”匈牙利算法的两侧使用相同的集合，并在每个元素与其自身的配对上分配“无穷大”。这将为您提供最大的配对，并保证没有人与自己匹配。

于 2015-03-16T17:46:10.353 回答
0

该问题称为最优非二分匹配。一个经典的参考资料是：DERIGS, U. (1988)。用最短路径技术解决非二分匹配问题。运筹学年鉴 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-27T17:20:56.790 回答