在六角图中寻找最佳节点对的算法
我正在寻找一种算法来查找六边形（蜂窝）图上的相邻节点对，以最小化成本函数。
- 每个节点连接到三个相邻节点，
- 每个节点“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 困难的，但我真的不需要真正的最优解决方案，一个好的解决方案就足够了。
- 朴素的算法往往会得到“锁定”的节点，即它们的所有邻居都被占用。
注意：我不熟悉该领域的常用术语（是图论吗？）。如果您可以提供帮助，那么也许这可以让我在文献中寻找解决方案。
I'm searching for an algorithm to find pairs of adjacent nodes on a hexagonal (honeycomb) graph that minimizes a cost function.
- each node is connected to three adjacent nodes
- each node "i" should be paired with exactly one neighbor node "j".
each pair of nodes defines a cost function
c = pairCost( i, j )
The total cost is then computed as
totalCost = 1/2 sum_{i=1:N} ( pairCost(i, pair(i) ) )
Where pair(i) returns the index of the node that "i" is paired with. (The sum is divided by two because the sum counts each node twice). My question is, how do I find node pairs that minimize the totalCost?
The linked image should make it clearer what a solution would look like (thick red line indicates a pairing):
Some further notes:
- I don't really care about the outmost nodes
- My cost function is something like || v(i) - v(j) || (distance between vectors associated with the nodes)
- I'm guessing the problem might be NP-hard, but I don't really need the truly optimal solution, a good one would suffice.
- Naive algos tend to get nodes that are "locked in", i.e. all their neighbors are taken.
Note: I'm not familiar with the usual nomenclature in this field (is it graph theory?). If you could help with that, then maybe that could enable me to search for a solution in the literature.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这是一般图中的最大权重匹配问题的一个实例 -当然，您必须否定权重才能使其成为最小权重匹配问题。 Edmonds 的路径、树木和花朵算法 (维基百科链接）为您解决了这个问题（还有一个公共Python 实现）。对于 n 个顶点，简单的实现是 O(n4)，但可以将其降低到 O(n1/2m)使用 Micali 和 Vazirani 的算法计算 n 个顶点和 m 个边（抱歉，找不到相应的 PDF）。
This is an instance of the maximum weight matching problem in a general graph - of course you'll have to negate your weights to make it a minimum weight matching problem. Edmonds's paths, trees and flowers algorithm (Wikipedia link) solves this for you (there is also a public Python implementation). The naive implementation is O(n4) for n vertices, but it can be pushed down to O(n1/2m) for n vertices and m edges using the algorithm of Micali and Vazirani (sorry, couldn't find a PDF for that).
这似乎与最小边缘覆盖问题有关，附加约束是只能有一个边缘每个节点，并且您试图最小化成本而不是边的数量。也许你可以通过搜索该短语找到一些答案。
如果做不到这一点，您的问题可以被表述为整数线性规划问题，它是 NP 完全的，这意味着即使对于中等规模的问题，您也可能会得到可怕的性能。 （但这并不一定意味着问题本身是 NP 完全的。）
This seems related to the minimum edge cover problem, with the additional constraint that there can only be one edge per node, and that you're trying to minimize the cost rather than the number of edges. Maybe you can find some answers by searching for that phrase.
Failing that, your problem can be phrased as an integer linear programming problem, which is NP-complete, which means that you might get dreadful performance for even medium-sized problems. (This does not necessarily mean that the problem itself is NP-complete, though.)