我正在寻找一种算法来在六边形(蜂窝)图上找到成对的相邻节点,以最小化成本函数。
- 每个节点连接到三个相邻节点
- 每个节点“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 难的,但我真的不需要真正的最佳解决方案,一个好的解决方案就足够了。
- 朴素算法倾向于得到“锁定”的节点,即它们的所有邻居都被占用。
注意:我不熟悉该领域的常用术语(是图论吗?)。如果您能对此提供帮助,那么也许这可以让我在文献中寻找解决方案。