2

我想在无向图中找到固定长度的路径（在运行程序时给出）。我正在使用我的图的邻接矩阵。
我尝试使用一些算法，如 DFS 或 A*，但它们只返回最短路径。

无法再次访问节点。

所以假设我的图有 9 个节点，最短路径是由 4 个节点构建的。
我想要有一个额外的变量来“告诉”算法我想要找到有 7 个节点的路径（例如），它将返回包含在我的预期路径 {1,2,4,5,6, 7,8}。
当然，如果没有我想要的路径解决方案，它不会返回任何内容（或者它会返回接近我的期望的路径，比如说 19 而不是 20）。

有人告诉我关于回溯的 DFS，但我对此一无所知。
有人可以解释如何使用带有回溯的 DFS 或推荐一些其他算法来解决这个问题吗？

4

5 回答 5

6

回溯确实似乎是一个合理的解决方案。这个想法是递归地找到所需长度的路径。

伪代码：

DFS(depth,v,path):
  if (depth == 0 && v is target): //stop clause for successful branch
       print path
       return
  if (depth == 0): //stop clause for non successful branch
       return
  for each vertex u such that (v,u) is an edge:
       path.append(v) //add the current vertex to the path
       DFS(depth-1,u,path) //recursively check all paths for of shorter depth
       path.removeLast() // clean up environment

上述算法将生成所需深度的所有路径。
调用DFS(depth,source,[])（其中[]是一个空列表）。

笔记：

  • 该算法将生成可能并不简单的路径。如果您只需要简单的路径 - 您还需要维护visited集合，并在将每个顶点附加到找到的路径时添加它，并在将其从路径中删除时将其删除。
  • 如果您只想找到一个这样的路径 - 您应该从函数返回值（如果找到这样的路径，则返回 true），并在返回值为 true 时打破循环（并返回 true）。
于 2012-06-04T15:14:31.257 回答
2

如上所述的问题是NP完全的。给定一个有效的算法来解决您的问题，您可以轻松解决哈密顿循环问题。

因此，不存在多项式时间解（除非 P=NP）。对于详尽的搜索、指数时间解决方案，请查看@amit 的答案。

于 2012-06-04T15:29:15.417 回答
0

尝试找到最长的路径，然后将其切割成所需的长度。最长的路径也称为图的直径。通过对每个顶点运行 DFS 可以找到最长的路径。

于 2012-06-04T12:19:02.033 回答
0

假设您可以在图中找到长度为 d 的路径，那么您可以运行此算法 |V| 次并找到最长的 NP 完全路径。所以你可以尝试以下方法 -

1）近似算法 2）蛮力方法（更适合编程）。使用 GPU 加速您的代码。

此外，您可能会感兴趣 -

DAG 存在线性时间算法。

于 2012-07-10T17:21:22.923 回答
0

一个 dfs 应该就足够了：

void dfs(int start, int hops)
{
  if(hops == k && start == t)
    {
      path++;
      return;
    }
  else if(hops >= k)
    return;
  for(int w = 1; w <= n; w++)
    if(routes[start][w])
      dfs(w, hops + 1);
}

这里，k 是路径的长度，routes[][] 是图的邻接矩阵。path 是一个全局变量。这可以考虑循环 - 它考虑了给定长度的所有路径。从主，调用

path = 0;
dfs(source, k);
cout<<path;

请注意，节点数比跳数多一。另请注意，如果路径的长度很大，则此功能会快速叠加。没有双关语的意思。

于 2012-06-05T13:47:08.057 回答