匹配算法

Question

这里的奇怪问题不是真正的代码，而是逻辑，希望它可以在这里发布，在这里是

我有一个可以将其视为图形的数据结构。每个节点可以支持许多链接，但仅限于每个节点的值。所有链接都是双向的。每个链接都有成本。成本取决于节点之间的欧几里得差异，每个节点中两个参数的最小值。和全球修饰符。

我希望找到该图的最高成本。

想知道是否有一种聪明的方法可以找到这样的匹配，而不是在蛮力中经历……这很丑陋……而且我不确定如果不花700万年的历史，我什至不确定如何做到这一点。

澄清：

Global variable = T
many nodes N each have E,X,Y,L
L is the max number of links each node can have.
cost of link A,B = Sqrt(  min([a].e | [b].e)  ) x 
     ( 1 + Sqrt( sqrt(sqr([a].x-[b].x)+sqr([a].y-[b].y)))/75 + Sqrt(t)/10 )


total cost =sum all links.....and we wish to maximize this.

节点的平均值为40-50可以范围为（20..600）平均节点链接因子为3范围0-10。

Answer 1

如果我正确理解问题，那么可能没有多项式解决方案。因此，我将实施以下算法：

1. 通过孟找到一些解决方案 贪婪的. 。为此，您按成本对所有边缘进行排序，然后以最高的速度从它们开始，在可能的情况下向图形添加边缘，然后在节点无法接受更多的边缘时跳过。
2. 查看您的边缘，并尝试通过使用一个将它们更改为归档更高的成本 启发式方法. 。我想到的第一个：您循环浏览所有4个节点（a，b，c，d），如果您的当前图具有边缘AB，CD，但是AC，BD会更好，那么您会进行更改。
3. 可选的是6个tuply或其他的东西 遗传算法 （它们是这样称呼的）。

Answer 2

为了使本文的其他任何人的完整性，我建议重新访问您的图形理论算法：

• Dijkstra
• 一个明星
• 贪婪的
• 深度 /广度首先
• 甚至动态编程（在某些情况下）
• ect。 ect。

在某个地方，是您问题的正确解决方案。我建议您先看Dijkstra。

我希望这可以帮助别人。

Answer 3

这等同于旅行推销员问题（因此是NP填充），因为如果您可以有效地解决此问题，则可以通过将每个成本替换为互惠来解决TSP。

这意味着您无法准确解决。另一方面，这意味着您可以按照我说的（将每个成本替换为倒数），然后在此问题上使用任何已知的TSP近似方法。

Answer 4

看起来像个 最大流量问题 大部头书。

Answer 5

是否有可能从任何给定的起点（省略跳跃到访问的节点）中选择下一个最昂贵的选项并在访问所有节点后停止？如果您回到死胡同，回到前面的位置，那些您不在死胡同并贪婪地选择的地方。这将需要一些工作，并且可能像堆栈一样，以保持您的道路。我认为这将有效地有效，只要成本良好且不负面。

Answer 6

使用遗传算法。它们旨在解决您所陈述的问题，以迅速降低时间复杂性。用您选择的语言检查AI库。