项a-d将以使所有项对之间的总距离最小化的方式与项0-3配对。例如,此矩阵可以描述第一组中的每个项目与其对应组中的项目之间的距离:
[[2, 2, 4, 9],
[4, 7, 1, 1],
[3, 3, 8, 3],
[6, 1, 7, 8]]这意味着'a‘-> '0’距离是2,'a‘-> '1’距离是2,'a‘-> '2’距离是4,'a‘-> '3’距离是9,'b‘-> '0’距离是4,依此类推。
有没有一种算法可以将每个字母与一个数字进行匹配,从而使总距离最小化?例如:
[('a', 1), ('b', 3), ('c', 0), ('d', 2)]将是一个合法的解决方案,总距离:2+1+3+7= 13。暴力强制和测试所有可能的组合是不可能的,因为现实世界中有超过四个项目的组。
发布于 2011-08-17 20:30:46
这是一个经典的二部图优化任务,可以使用Hungarian algorithm/method来解决。
发布于 2011-08-18 00:40:58
这可以通过将其视为加权二部匹配问题的实例来解决。其思想是将元素a-d和0-3视为图中的节点,其中每个字母节点连接到每个编号节点,其边的权重由矩阵指定。一旦有了这个图,您就需要找到一组将字母与数字匹配的边,其中每个节点最多只能连接到一条边。这样的一组边被称为匹配,由于您希望最小化距离,因此您正在寻找最小成本的匹配。
正如yi_H指出的那样,这个问题已经得到了很好的研究,并且有许多很好的多项式时间算法。匈牙利算法可能是解决该问题的最著名的算法,但从那时起,已经发明了其他算法,它们的速度逐渐(或实际上)更快。
这个问题值得记住,因为它在许多情况下都会出现。任何时候,您需要将一个组中的项分配给另一个组中的项,请检查是否可以将问题减少到二部匹配。如果是这样的话,您几乎肯定已经找到了初始问题的快速解决方案。
https://stackoverflow.com/questions/7092530
复制相似问题