为什么在图形中找到最长的路径是NP难的 [英] Why finding the longest path in a graph is NP-hard

问题描述

此链接提到:

加权图中两个给定顶点s和t之间的最长路径G与从G通过以下公式得出的图-G中的最短路径相同改变每一个分量到它的否定.因此，如果路径最短可以在-G中找到，然后最长的路径也可以在G中找到.

A longest path between two given vertices s and t in a weighted graph G is the same thing as a shortest path in a graph −G derived from G by changing every weight to its negation. Therefore, if shortest paths can be found in −G, then longest paths can also be found in G.

那么，如果这种转换可以将最长路径简化为最短路径问题，那么为什么找到最长路径却是NP难题呢?

So why is finding the longest path an NP-hard problem if this transformation can reduce it to the shortest path problem?

转换后，我们有以下几种情况:

After the transformation, we have have these cases:

• -G 具有负周期，在这种情况下，无法找到 -G 中的最短路径
• -G 没有负周期，在这种情况下，Floy-Warshall或Bellman-Ford算法可以在多项式时间内找到 -G 中的最短路径

• -G has a negative cycle, in which case the shortest path in -G cannot be found
• -G does not have a negative cycle, in which case Floy-Warshall or Bellman-Ford algorithm can find the shortest path in -G in polynomial time

问题:

1. 说没有负周期是否正确，找到最长路径的问题不是NP难的?

1. Is it correct to say if there is no negative cycle, the problem of finding longest path is not NP-hard?

在存在负周期时是否正确地说，节点之间仍然存在最长的简单路径，难于发现NP?

Is it correct to say in the presence of negative cycles, there is still a longest simple path between nodes which is NP-hard to be found?

如果是这样，说在图中找到最长的简单路径是否具有NP难度会更准确?

If so, is it more accurate to say finding the longest simple path in a graph is NP-hard?

如果是这样，是否由于说 -G 变换而在图中找到最短的简单路径也是NP难道?

If so, because of -G transformation is it also correct to say that finding the shortest simple path in a graph is also NP-hard?

修改

此链接更详细地解释了关于最长路径问题的困惑: https://hackernoon.com/shortest-and-longest-path-algorithms-job-interview-cheatsheet-2adc8e18869

This link explains the confusion about longest path problem in more details: https://hackernoon.com/shortest-and-longest-path-algorithms-job-interview-cheatsheet-2adc8e18869

推荐答案

此处的困惑在于，最长路径问题通常要求最长的简单路径，即没有重复顶点的最长路径.因此，可以将其简化为哈密顿路径问题，该问题被认为是NP难的.

The confusion here is that the Longest Path Problem generally asks for the longest simple path, i.e., the longest path without repeated vertices. For this reason, it can be reduced to the Hamiltonian Path problem, which is known to be NP-hard.

Bellman-Ford和类似的算法计算图形中的最短路径(注意:没有简单)，即可以重复顶点.

Bellman-Ford and similar algorithms, on the other hand, compute the shortest path in a graph (note: without simple), i.e. vertices can be repeated.

您的四个问题:

1. 不.如果 -G 中存在负循环，则 G 中根本没有最长的路径，因为您可以永远继续循环.最长的 simple 路径可能仍然存在，但是无论是否存在负循环，该问题都可以归结为哈密顿路径，因此仍然是NP问题.
2. 的确！(如果图形是无向的.)
3. 是
4. 是

1. No. If there is a negative cycle in -G, a longest path does not exist at all in G, because you can just continue walking around the cycle forever. A longest simple path might still exist, but with or without negative cycle, the problem can be reduced to Hamiltonian Path and is therefore still NP-hard.
2. Indeed! (If the graph is undirected.)
3. Yup
4. Yup

这篇关于为什么在图形中找到最长的路径是NP难的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！