完整图形上最便宜的成本遍历

本文介绍了完整图形上最便宜的成本遍历的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我想知道是否有一种算法可以: 给定一个完全连接的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.