0

我有一个匹配问题,并设计了一种解决方法。我需要知道是否存在算法,如果存在名称,对于以下情况,我看了很多,但找不到任何东西。我最接近的是循环赛,但这并不完全相同。

它类似于一些网络问题,但他们通常不会得到最佳路由,他们只是满足于一个好的路由。我需要最优化的。

这是一篇很长的文章,也是对 SO 的一个不寻常的请求,但我在任何地方都找不到它的名字。

问题 我有一堆物品。每个项目都可以潜在地连接到一个或多个其他项目。每个项目只能配对一次。每个连接都有一个值。

我需要找出什么样的配对组合会产生最高的连接值。

我的解决方案 找到所有项目的所有对并将其存储在地图中,获取第一项并将其与地图值中的第一项配对。拿下一个项目并将其与第一个未使用的项目配对。继续这样做,直到不再存在未使用的项目。保存此组合或配对总值。如果可能,更改对中的最后一对。与已保存的组合相比,如果在无法再更改配对时保存更多新组合,请将其删除并更改新的最后一对,找到更多可能的配对。这一直持续到组合列表减小到零

最后保存的组合是最好的组合。(鳍)

4

2 回答 2

3

这个问题基本上只是一个最大加权匹配。

对于二分图,找到最大匹配很容易。对于任意图,它更难但仍然可行。维基百科建议 Edmonds 提出一种称为 Blossom 算法的算法。

至于你的算法,不清楚你在做什么,但它看起来像是一个贪婪的任务,然后是爬山。我担心您的算法不能保证产生最佳结果。你真的证明了这一点吗?你怎么知道它不会陷入局部最小值?

于 2013-04-27T04:31:45.613 回答
0

我相信您正在寻找解决稳定婚姻问题的Gale-Shapley 算法。

于 2013-04-27T04:32:15.763 回答