0

我正在寻找一种算法来在六边形（蜂窝）图上找到成对的相邻节点，以最小化成本函数。

  • 每个节点连接到三个相邻节点
  • 每个节点“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 难的，但我真的不需要真正的最佳解决方案，一个好的解决方案就足够了。
  • 朴素算法倾向于得到“锁定”的节点，即它们的所有邻居都被占用。

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

4

2 回答 2

1

这是一般图中最大权重匹配问题的一个实例- 当然，您必须否定权重才能使其成为最小权重匹配问题。Edmonds 的路径、树木和花朵算法（维基百科链接）为您解决了这个问题（还有一个公共Python 实现）。对于 n 个顶点，朴素的实现是 O(n 4 ) ，但是对于n个顶点和m个边，可以使用 Micali 和 Vazirani 的算法将其下推到 O(n 1/2 m) （对不起，找不到 PDF为了那个原因）。

于 2011-06-23T09:44:46.537 回答
0

这似乎与最小边覆盖问题有关，附加限制是每个节点只能有一条边，并且您试图最小化成本而不是边数。也许您可以通过搜索该短语找到一些答案。

如果做不到这一点，您的问题可以表述为整数线性规划问题，它是 NP 完全的，这意味着即使是中等规模的问题，您也可能获得可怕的性能。（但这并不一定意味着问题本身是 NP 完全的。）

于 2011-06-23T09:19:56.920 回答