algorithm - 查找项目对之间的全局最小距离的算法

Question

商品广告将与商品 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。暴力强制和测试所有可能的组合是不可能的，因为现实世界中有超过四个项目的组。

Answer 1

这是二部图的经典优化任务，可以使用匈牙利算法/方法来解决。

Answer 2

这可以通过将其视为加权二分匹配问题的一个实例来解决。这个想法是将元素 ad 和 0-3 视为图中的节点，其中每个带字母的节点都连接到每个编号的节点，其边的权重由矩阵指定。一旦你有了这个图，你想找到一组匹配字母和数字的边，每个节点最多只连接一个边。这样的一组边称为匹配，并且由于您希望最小化距离，因此您正在寻找最小成本匹配。

正如 yi_H 所指出的，这个问题已经得到了充分的研究，并且有许多好的多项式时间算法。匈牙利算法可能是该问题最著名的算法，但从那时起，人们发明了其他算法，它们渐近（或实际上）更快。

这个问题值得记住，因为它在许多情况下都会出现。每当您需要将一组中的项目分配给另一组中的项目时，请检查是否可以将问题简化为二分匹配。如果是这样，您几乎肯定已经找到了最初问题的快速解决方案。