连接特定的节点无向图最短路径 [英] shortest path connecting certain nodes in an undirected graph

问题描述

我有一个无向和加权图的节点的某个子集。我试图确定是否存在所有这些节点之间的路径，并且，如果有，什么是包括哪些不是在节点子集最少节点的最短路径。

我一直在努力想办法修改最小生成树算法来做到这一点，但到目前为止，我还没有想出一个可行的解决方案。

有没有好的办法做到这一点，或这是一个已知算法的描述？

解决方案

  

我试图确定是否存在所有这些之间的路径   节点

（我从此明白你正在寻找访问所有标注节点的单一路径）

好了我的朋友，这可能是一个问题 - 你所描述的 旅行商的变化问题 和汉弥尔顿路径问题（如果你正在寻找一个简单的路径的，从哈密尔顿路径减少是直截了当：标记所有节点）。
但恐怕这些问题是 NP难 。

这是NP-Hard问题是，我们的个问题不知道任何多项式时间的解决方案以解决它，和周围的一般的假设是 - 不存在 ¹ 。

因此​​，你最好的拍摄很可能会出现一些指数的解决方案。有为O（n ^ 2 * 2 ^ n）的解决方案TSP使用动态编程，或蛮力解决方案，这是 O（N！）

---

（1）真的不是一个正式的定义，但是这是足够的信息来理解这个问题，真的是有很多更进NP难的问题。

I have a certain subset of nodes of an undirected and unweighted graph. I am trying to determine whether there is a path between all of these nodes, and, if there is, what is the shortest path which includes the fewest nodes which are not in the subset of nodes.

I have been trying to think of a way to modify a minimum spanning tree algorithm to accomplish this, but so far I haven't come up with a workable solution.

Is there a good way to do this or is this a description of an already known algorithm?

解决方案

I am trying to determine whether there is a path between all of these nodes

(I understand from this you are looking for a single path that visits all the marked nodes)

Well my friend, this could be a problem - you are describing a variation of the Traveling Salesman Problem and the Hamiltonian Path Problem (If you are looking for a simple path, the reduction from Hamiltonian Path is straight forward: mark all the nodes).
But I am afraid these problems are NP-Hard.

An NP-Hard problem is a problem that we do not know of any polynomial time solution to solve it, and the general assumption around is - one doesn't exist¹.

Thus, your best shot is probably going to be some exponential solution. There is O(n^2 * 2^n) solution to TSP using dynamic programming, or brute force solution which are O(n!)

---

(1) Really not a formal definition, but this is enough information to understand the problem, there is really a lot more into NP-Hard problems.

这篇关于连接特定的节点无向图最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！