首页 文章

如何在图中找到精确长度的路径

提问于
浏览 次
1

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

无法再次访问节点 .

因此，假设我的图表有9个节点，最短路径是从4个节点构建的 .
我希望有一个额外的变量"tell"我想找到有7个节点的路径的算法（例如），它将返回包含在我预期路径中的节点{1,2,4,5,6,7， 8} .
当然，如果没有我想要的路径解决方案，它将不返回任何东西（或者它会返回接近我的表达的路径，让我们说19而不是20） .

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

algorithm graph-algorithm path-finding

5 回答

  • 1

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

    Psuedo代码：

    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） .

    回复于
  • 2

    所述问题是NP完全的 . 鉴于解决问题的有效算法，Yo可以简单地解决Hamiltonian Cycle Problem .

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

    回复于
  • 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是路径的长度，而路由[] []是图的邻接矩阵 . path是一个全局变量 . 这可以解释周期 - 它考虑了给定长度的所有路径 . 从主要，打电话

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

    请注意，节点数比跳数多一个 . 另请注意，如果路径的长度很大，则此函数会快速堆叠 . 没有双关语 .

    回复于
  • 6

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

    回复于
  • 0

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

    1）近似算法2）强力方法（更适合编程） . 使用GPU加速代码 .

    您也可能感兴趣的是 -

    存在DAG的线性时间算法 .

    回复于

相关问题