找到访问所有节点的图中的最短路径 [英] Find the shortest path in a graph visiting all nodes

问题描述

我有一个加权和无向图 G ，其中 n 顶点。其中两个顶点是 X 和 Y 。
我需要找到以 X 开头的最短路径，结束于 Y 并穿过所有顶点的G（以任何顺序）。

我该如何做到这一点？

这不是旅行推销员问题：我不需要仅访问每个顶点一次，也不想返回第一个顶点。

解决方案

这个问题基本上是NP-Hard，我将给出一个证明草图（而不是适当的简化）除非 P = NP ，否则这个问题没有多项式解决方案。

假设这个问题可以用多项式 O（P（n））通过一些算法解决， A（G，X，Y）

定义以下算法：

<$ p （x，y）== | V | - 1）：$ b $ HamiltonianPath（G）：每个对b $ b返回true
返回false


该算法解决了哈密顿路径问题。

- >如果某对 x，y 遍历所有节点，其长度正好 | V | ，这意味着它不会使用任何
顶点两次，并且找到的路径是哈密​​尔顿算子

- 如果存在Hamiltonian路径v1-> v2 - > ...-> vn，那么当调用
A（G，v1，vn），你会发现最短的路径，它的
长度最多为 | V | -1 （并且它不能小于它，因为它需要
遍历所有顶点），并且算法会生成真实的。

复杂性：

算法的复杂性是 O（n ^ 2 * P（n）） ，这是多项式时间。因此，假设存在这样的算法，哈密顿路径可以在多项式时间内求解，并且因为它（哈密尔顿路径问题）是 NP-Complete ，P = NP。

I have a weighted and undirected graph G with n vertices. Two of these vertices are X and Y.
I need to find the shortest path that starts at X, ends at Y and passes through all the vertices of G (in any order).
How I can do this?

This is not the Travelling Salesman Problemm: I don't need to visit each vertex just once and I don't want to return to the first vertex.

解决方案

This problem is basically NP-Hard, I am going to give a sketch of a proof (and not a proper reduction), that explains that unless P = NP, there is no polynomial solution to this problem.

Assume torwards contradiction that this problem can be solved in polynomial time O(P(n)) by some algorithm A(G,x,y)

Define the following algorithm:

HamiltonianPath(G):
  for each pair (x,y):
      if A(G(x,y) == |V| - 1):
          return true
  return false

This algorithm solves Hamiltonian Path Problem.

-> If there is a path between some pair x,y that goes through all nodes and its length is exactly |V|, it means it did not use any vertex twice, and the path found is Hamiltonian.

<- If there is a Hamiltonian Path v1->v2->...->vn, then when invoking A(G,v1,vn), you will find the shortest possible path, which its length is at most |V|-1 (and it cannot be less because it needs to go through all vertices), and the algorithm will yield true.

Complexity:

Complexity of the algorithm is O(n^2 * P(n)), which is polynomial time.

So, assuming such an algorithm exists, Hamiltonian Path can be solved in polynomial time, and since it (Hamiltonian Path Problem) is NP-Complete, P=NP.

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