完整图形上最便宜的成本遍历 [英] Cheapest cost traversal on Complete graph

问题描述

我想知道是否有一种算法可以: 给定一个完全连接的n个节点的图(具有不同的权重)...将为我提供从节点A(起始节点)到所有其他节点并返回到节点A的最便宜的周期吗?有没有办法改变像Primm这样的算法来实现这一目标?

I was wondering if there is an algorithm which: given a fully connected graph of n-nodes (with different weights)... will give me the cheapest cycle to go from node A (a start node) to all other nodes, and return to node A? Is there a way to alter an algorithm like Primm's to accomplish this?

感谢您的帮助

我忘了提到我正在处理一个无向图，所以每个顶点的入度=出度.

I forgot to mention I'm dealing with a undirected graph so the in-degree = out-degree for each vertex.

推荐答案

不需要任何此类路径.当且仅当每个节点的入度等于其出度时，它才存在.

There need not be any such path. It exists if and only if the in-degree of every node equals its out-degree.

您想要的是最便宜的欧拉路径.找到它的问题称为旅行商问题.没有，也没有，有一个快速的算法可以解决它.

What you want is the cheapest Eulerian path. The problem of finding it is called the Traveling Salesman Problem. There is not, and cannot be, a fast algorithm to solve it.

修改: 再三考虑:旅行推销员问题"搜索的巡回演出恰好一次访问了每个节点.您要进行的游览至少要访问每个节点一次.因此，您的问题可能只是P.我对此表示怀疑.

Edit: On second thought: The Traveling Salesman Problem searches for a tour that visits every node exactly once. You're asking for a tour that visits every node at least once. Thus, your problem might just be in P. I doubt it, though.

这篇关于完整图形上最便宜的成本遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！