匹配算法
这里奇怪的问题不是真正的代码而是逻辑，希望可以将其发布在这里，这是
我有一个可以被认为是图形的数据结构。 每个节点可以支持许多链接，但仅限于每个节点的一个值。 所有链接都是双向的。 并且每个环节都有成本。 成本取决于节点之间的欧氏差（每个节点中两个参数的最小值）。 和一个全局修饰符。
我希望找到该图的最大成本。
想知道是否有一种聪明的方法来找到这样的匹配，而不是用蛮力来完成……这很丑陋……而且我不确定如果不花费 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。
Odd question here not really code but logic,hope its ok to post it here,here it is
I have a data structure that can be thought of as a graph.
Each node can support many links but is limited to a value for each node.
All links are bidirectional. and each link has a cost. the cost depends on euclidian difference between the nodes the minimum value of two parameters in each node. and a global modifier.
i wish to find the maximum cost for the graph.
wondering if there was a clever way to find such a matching, rather than going through in brute force ...which is ugly... and i'm not sure how i'd even do that without spending 7 million years running it.
To clarify:
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.
average values for nodes is 40-50 can range to (20..600)
average node linking factor is 3 range 0-10.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
为了让其他人看到这篇文章的完整性，我建议重新审视你的图论算法：
那里有解决您问题的正确方法。 我建议先看看 Dijkstra。
我希望这可以帮助别人。
For the sake of completeness for anybody else that looks at this article, i would suggest revisiting your graph theory algorithms:
In there somewhere is the correct solution for your problem. I would suggest looking at Dijkstra first.
I hope this helps someone.
如果我正确理解这个问题，很可能没有多项式解。 因此，我将实现以下算法：
If I understand the problem correctly, there is likely no polynomial solution. Therefore I would implement the following algorithm:
这相当于旅行商问题（因此是 NP 完全问题），因为如果您可以有效地解决这个问题，您可以简单地通过用其倒数替换每个成本来解决 TSP。
这意味着你无法准确地解决。 另一方面，这意味着您可以完全按照我所说的那样进行（将每个成本替换为其倒数），然后使用任何已知的 TSP 近似方法来解决此问题。
This is equivalent to the traveling salesman problem (and is therefore NP-Complete) since if you could solve this problem efficiently, you could solve TSP simply by replacing each cost with its reciprocal.
This means you can't solve exactly. On the other hand, it means that you can do exactly as I said (replace each cost with its reciprocal) and then use any of the known TSP approximation methods on this problem.
对我来说似乎是一个最大流量问题。
Seems like a max flow problem to me.
是否有可能通过从任何给定的起点贪婪地选择下一个最昂贵的选项（省略跳转到访问的节点）并在访问所有节点后停止？ 如果你走到了死胡同，回溯到之前没有陷入死胡同的位置并贪婪地选择。 这需要一些工作，可能需要一些类似堆栈的东西来保存你的路径。我认为，只要成本排序良好且非负，这将非常有效。
Is it possible that by greedily selecting the next most expensive option from any given start point (omitting jumps to visited nodes) and stopping once all nodes are visited? If you get to a dead end backtrack to the previous spot where you are not at a dead end and greedily select. It would require some work and probably something like a stack to keep your paths in. I think this would work quite effectively provided the costs are well ordered and non negative.
使用遗传算法。 它们旨在解决您提出的问题，快速降低时间复杂度。 检查您选择的语言的 AI 库。
Use Genetic Algorithms. They are designed to solve the problem you state rapidly reducing time complexity. Check for AI library in your language of choice.