2

無向グラフで（プログラムの実行中に与えられた）固定長のパスを見つけたいのですが。グラフの隣接行列を使用しています。
DFSやA*などのアルゴリズムを使用しようとしましたが、最短パスしか返されません。

ノードに再度アクセスすることはできません。

したがって、グラフに9つのノードがあり、最短パスが4つのノードから構築されているとします。
たとえば、7つのノードを持つパスを見つけたいというアルゴリズムを「伝える」追加の変数が必要です。これにより、予想されるパスに含まれるノードが返されます{1,2,4,5,6、 7,8}。
もちろん、必要なパスの解決策がない場合は、何も返されません（または、私の説明に近いパスが返されます。たとえば、20ではなく19になります）。

誰かがバックトラックを使用した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、setを維持し、見つかったパスに追加するときに各頂点を追加し、パスから削除するときに削除する必要があります。
  • そのようなパスを1つだけ見つけたい場合は、関数から値を返し（そのようなパスが見つかった場合はtrue）、戻り値がtrueのときにループを中断します（そしてtrueを返します）。
于 2012-06-04T15:14:31.257 に答える
2

述べられている問題はNP完全です。あなたの問題を解くための効率的なアルゴリズムがあれば、 Yoはハミルトン閉路問題を自明に解くことができます。

したがって、多項式時間解は存在しません（P = NPでない限り）。徹底的な検索、指数関数的な時間の解決策については、@amitの回答を確認してください。

于 2012-06-04T15:29:15.417 に答える
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;

ノードの数はホップの数より1つ多いことに注意してください。また、パスの長さが長い場合、この関数はすぐにスタックすることに注意してください。しゃれは意図されていません。

于 2012-06-05T13:47:08.057 に答える
0

グラフで長さ d のパスを見つけることができると仮定すると、このアルゴリズム |V| を実行できます。回し、NP 完全である最長パスを見つけます。したがって、次のアプローチを試すことができます-

1) 近似アルゴリズム 2) ブルート フォース アプローチ (プログラミングに適しています)。GPU を使用してコードを高速化します。

また、それはあなたにとって興味深いかもしれません -

DAG には線形時間アルゴリズムが存在します。

于 2012-07-10T17:21:22.923 に答える
0

最長のパスを見つけて、必要な長さにカットしてみてください。最長パスは、グラフの直径とも呼ばれます。最長パスは、頂点ごとに DFS を実行することで見つけることができます。

于 2012-06-04T12:19:02.033 に答える