Let G(V,E) be the original graph, let N be the set of nodes that must be visited.
1. Compute the shortest-path matrix M for the entire graph (|V|x|V| matrix that contains
the length of the shortest path between each two nodes).
2. Generate a new graph G`, containing N alone, with the distances between each
two nodes taken from the shortest-path matrix M.
3. Solve the Minimum Weight Hamiltonian Path Problem on G`.
注意，这里的"hardest"部分是第三部分，它需要指数时间 . 但如果组 N 不是太大，你就能解决它：
Bruteforce算法将让您解决 N 在几秒钟内包含大约11个节点的问题（ O(|N|!) 复杂性）
动态编程将让您解决 N 在几秒钟内包含大约20个节点的问题（ O(2^|N|*|N|^2) 复杂性 .
1 回答
正如我评论的那样，这是一个难题，所以不要指望多项式时间算法 .
但是，如果您正在寻找一种算法，您可以在可接受的时间内为您提到的问题实例进行计算，这可能会有效：
注意，这里的"hardest"部分是第三部分，它需要指数时间 . 但如果组
N不是太大，你就能解决它：Bruteforce算法将让您解决
N在几秒钟内包含大约11个节点的问题（O(|N|!)复杂性）动态编程将让您解决
N在几秒钟内包含大约20个节点的问题（O(2^|N|*|N|^2)复杂性 .基本上你可以将解决最小权重哈密顿路径问题的任何算法应用到第三部分，这些算法通常等同于TSP算法（这些问题之间的唯一区别是在TSP中你在访问所有其他算法后返回源节点节点） .