算法在一个连接所有顶点的图中找到最小权重的线性路径

给定一个具有n个顶点的带权无向图，我面临的问题是找到一个最小权重的路径，它将每个顶点连接到一条线。起初，我认为这是找到最小生成树的问题，但事实并非如此。在生成树的情况下，顶点处可能存在分支或度数可能大于2。我需要找到的是一个线性路径，即除了结束顶点之外的所有顶点的度数恰好为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.

贪婪的方法，我将不得不对所有的顶点为出发点做到这一点。我不确定这个算法是否正确，并且它的复杂度很高。什么应该是更好的方法来解决这个问题？

来源

2012-02-01 praveen

这个问题被称为是NP难从Hamiltonian path problem的减少，因为如果你给所有的边权重为1，问“是有重量的最多n的线性路径？”那么如果图形包含哈密尔顿路径，那么答案就是“是”。因此，你不可能找到比纯暴力更好的算法，因为除非P = NP，否则没有多项式时间解决方案。

对不起，在你的游行中下雨，并希望这有助于！

来源

2012-02-01 08:24:30 templatetypedef

路径的权重不一定是1.我必须找到最小权重的线性路径。需要探索的点数不大，可能不会超过100. – praveen 2012-02-01 08:27:51

@ praveen-为了减少这个问题，我们只需要证明Hamiltonian Path的任何实例都可以被编码为这个问题的一个实例。在这里，我们不需要使用问题的完整表达性，并且可以使用问题的更弱版本对其进行编码。 – templatetypedef 2012-02-01 08:30:06

虽然我认为@templatetypedef是正确的，并且这确实是哈密顿路径问题的一个实例，但您可能会通过Google搜索旅行推销员问题获得更好的结果 - 它足够接近以至于大多数（所有？）TSP启发式都会为你工作（唯一的区别是TSP至少通常被描述为从头到尾添加一条路径，所以它形成一个“环”而不是一条线）。 TSP通常也假设一个完整的图（即，每个节点彼此连接）;如果图形不完整，您仍然可以使用常规算法，在任何未连接的节点之间添加无限重量的连接。

你给出的贪婪方法通常被称为“最近邻居”启发式。这是几乎所有人都会遇到的第一种方法。它生产的非最佳解决方案在过去的一个世纪中已为人所知。不幸的是，在合理时间内运行的其他任何东西至少也会产生次优解决方案（至少在对问题没有限制的情况下）。 A *可能是在合理时间内产生合理（仅稍微不理想）结果的最常见算法。

来源

2012-02-01 09:36:31

_不幸的是，其他任何在合理时间内运行的东西至少也会产生次优解决方案的可能性_在实践中并非总是如此，有[非常大的]（http://www.tsp.gatech.edu/pla85900/index.html）已知最佳解决方案的TSP实例。 – swen 2012-02-01 16:48:17

算法在一个连接所有顶点的图中找到最小权重的线性路径

回答

相关问题