无向图中给定两个顶点之间的最长简单路径
Longest simple path between given two vertices in an undirected graph
Input: n-node undirected graph G(V,E); nodes s and t in V; positive integer k
Question: Is there a simple path between s and t in G that contains at least k edges?
我知道这个问题是 NP-hard 问题，但问题是我应该如何以及使用哪种算法来解决这个问题？
到目前为止我已经使用了 BFS 算法，但我认为它不是我应该使用的算法。在这一点上，我不知道如何继续。我不太确定我是否能找到这个问题的解决方案。近似值也可以。
这可以通过 BFS 的变体来解决：不是在队列中存储节点，而是存储路径。另一个区别是，我们不会忽略已经访问过的节点，而是只忽略已经包含在当前路径中的节点。
- 用单一路径初始化队列，仅包含节点
s。
- 当队列非空时：
- 从队列中轮询
path。让 u 成为路径中的最后一个节点。
- 如果
u = t：
- 若
path中的节点数至少为k + 1，则path为解； return 结果 "true".
- 否则如果
u != t：
- 对于
u 的每个邻居 v 尚未在 path 中，通过将 v 附加到 path 构造一条新路径，然后插入它进入队列。
- 如果循环没有找到解决方案就终止了，那么none存在； return 结果 "false".
完全相同的解决方案使用 DFS 而不是 BFS，通过用堆栈替换队列。在那种情况下，堆栈通常会使用较少的内存，但不一定会找到最短的解决方案。由于您只想回答 true/false 如果存在这样的路径，则不需要找到最短路径，因此 DFS 可能更好。
Input: n-node undirected graph G(V,E); nodes s and t in V; positive integer k
Question: Is there a simple path between s and t in G that contains at least k edges?
我知道这个问题是 NP-hard 问题，但问题是我应该如何以及使用哪种算法来解决这个问题？
到目前为止我已经使用了 BFS 算法，但我认为它不是我应该使用的算法。在这一点上，我不知道如何继续。我不太确定我是否能找到这个问题的解决方案。近似值也可以。
这可以通过 BFS 的变体来解决：不是在队列中存储节点，而是存储路径。另一个区别是，我们不会忽略已经访问过的节点，而是只忽略已经包含在当前路径中的节点。
- 用单一路径初始化队列，仅包含节点
s。 - 当队列非空时：
- 从队列中轮询
path。让u成为路径中的最后一个节点。 - 如果
u = t：- 若
path中的节点数至少为k + 1，则path为解； return 结果 "true".
- 若
- 否则如果
u != t：- 对于
u的每个邻居v尚未在path中，通过将v附加到path构造一条新路径，然后插入它进入队列。
- 对于
- 从队列中轮询
- 如果循环没有找到解决方案就终止了，那么none存在； return 结果 "false".
完全相同的解决方案使用 DFS 而不是 BFS，通过用堆栈替换队列。在那种情况下，堆栈通常会使用较少的内存，但不一定会找到最短的解决方案。由于您只想回答 true/false 如果存在这样的路径，则不需要找到最短路径，因此 DFS 可能更好。