匹配算法

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. 看看你的边缘，并试图通过使用启发式来更改它们以存档更高的成本。第一个出现在我脑海中的是：你循环遍历节点（A，B，C，D）的所有4元组，如果你当前的图有边AB，CD但是AC，BD会更好，然后你做出改变。
3. 可选用6元组或其他遗传算法（它们被称为这种方式，因为它们通过突变工作）。

Answer 2

是否有可能通过从任何给定起点贪婪地选择下一个最昂贵的选项（省略跳至访问节点）并停止所有节点访问？如果你死路回到前一个地方，你并没有死路一条，贪婪地选择。这需要一些工作，可能像堆栈一样，以保持您的路径。我认为这将非常有效地工作，只要成本有序且非负面。

Answer 3

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

Answer 4

为了完整为别人着想，着眼于本文中，我会建议重新审视你的图论算法：

• 的Dijkstra
• 爱仕达
• 贪婪
• 深度/广度优先
• 即使动态编程（在某些情况下）
• 等。等。

在那里有一个地方是你的问题的正确解决方案。我会建议先看看Dijkstra。

我希望这可以帮助别人。

Answer 5

这相当于旅行商问题（因此是NP-Complete），因为如果你能够有效地解决这个问题，你可以简单地通过用它的倒数代替每个成本来解决TSP。

这意味着你不能准确解决。另一方面，这意味着你可以像我说的那样完全按照它的倒数来代替每个成本，然后在这个问题上使用任何已知的TSP近似方法。

Answer 6

对我来说好像是一个max flow problem。