algorithm - 匹配算法

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

为了阅读本文的其他人的完整性，我建议重新审视您的图论算法:

• 迪杰斯特拉
• 阿斯塔
• 贪心
• 深度/广度优先
• 甚至是动态规划(在某些情况下)
• 等等。等等。

某处是您问题的正确解决方案。我建议先看看 Dijkstra。

我希望这对某人有帮助。