用于在图形中找到最小权重的线性路径的算法,该图形将所有顶点恰好连接一次

Question

给定具有n个顶点的加权无向图,我面临着找到连接线中每个顶点的最小权重路径的问题.起初,我认为这是找到最小生成树的问题,但事实并非如此.在生成树的情况下,在顶点处可能存在分支,或者该程度可以大于2.我需要找到的是一个线性路径,即除了端点之外的所有顶点都有两个度数.起点和终点顶点可以是n个顶点中的任何一个.

我是一个贪婪的方法,即

first chose any vertex, maintain a sum 
    check all its neighbors such that the cost of reaching it is 
    least among all the neighbors
    mark this neighbor as visited
    add the cost to sum
repeat the procedure above until all the points have been visited.

我必须以所有顶点为起点进行此操作.我不确定这个算法是否正确,而且它的复杂性也很高.对这个问题应该采取什么更好的方法？

Answer 1

通过减少汉密尔顿路径问题,已知这个问题是NP难的,因为如果给出所有边缘权重1并且问"是否存在最多n的线性路径？" 如果图形包含哈密尔顿路径,那么答案肯定是"是".因此,您不太可能找到比纯蛮力更好的算法,因为除非P = NP,否则没有多项式时间解.

很抱歉在你的游行中下雨,希望这有帮助!