在六边形图中寻找最优节点对的算法

Question

我正在寻找一种算法来找到六角形(蜂窝)图上的相邻节点对，从而使成本函数最小化。

• 每个节点都连接到三个相邻的节点
• 每个节点“i”应该与恰好一个邻居节点“j”配对。

• 每对节点定义一个代价函数

  c = pairCost( i, j )

• 然后计算总成本为

  totalCost = 1/2 sum_{i=1:N} ( pairCost(i, pair(i) ) )

其中 pair(i) 返回与“i”配对的节点的索引。 (总和除以二是因为总和对每个节点计数两次)。我的问题是，如何找到最小化总成本的节点对？

链接的图像应该使解决方案的外观更清晰(粗红线表示配对):

一些进一步的说明:

• 我真的不关心最外面的节点
• 我的成本函数类似于|| v(i) - v(j) || (与节点关联的向量之间的距离)
• 我猜这个问题可能是 NP-hard 问题，但我真的不需要真正最优的解决方案，一个好的解决方案就足够了。
• 朴素算法倾向于获得“锁定”的节点，即它们的所有邻居都被占用。

注意:我不熟悉该领域的常用术语(是图论吗？)。如果您能提供帮助，那么也许这能让我在文献中寻找解决方案。

Answer 1

这是 maximum weight matching problem 的一个实例在一般图表中 - 当然你必须否定你的权重以使其成为最小权重匹配问题。埃德蒙兹的 paths, trees and flowers algorithm ( Wikipedia link ) 为您解决这个问题(还有一个公开的 Python implementation )。对于 n 个顶点，简单的实现是 O(n⁴)，但对于n 个顶点和 m 个边使用 Micali 和 Vazirani 的算法(抱歉，找不到它的 PDF)。