3

重み付けされた有向グラフがあるとします。私たちのタスクは、2 つの頂点 (始点と終点) 間のコストが =< N であるすべてのパスを見つけることです。すべての頂点を 1 回だけ訪れます。それ以降のバージョンでは、ソースが宛先になることができるという条件を追加したいと思います (ループを作成するだけです)。

修正されたダイクストラのアルゴリズムで実行できると思いますが、そのようなことをどのように実装するかわかりません。助けてくれてありがとう。

4

3 に答える 3

3

この問題を解決するには、再帰的なバックトラッキングを使用できます。次の場合に再帰を終了します。

  • 目的地に着きます
  • すでに訪問したノードにアクセスします
  • パスの長さが N を超えています。

擬似コード:

list curpath := {}
int dest, maxlen
def findPaths (curNode, dist):
    if curNode = dest:
        print curpath
        return
    if curNode is marked:
        return
    if dist > maxlen:
        return
    add curNode to curpath
    mark curNode
    for nextNode, edgeDist adjacent to curNode:
        findPaths(nextNode, dist + edgeDist)
    remove last element of curpath
于 2012-11-18T01:04:33.623 に答える
1

A から B までの距離が N よりも小さく、A = B の可能性を許容するなど、有向グラフ内の点 A から点 B までのすべてのパスを見つけたいとします。

Dijkstra のアルゴリズムは、グラフ内のある点から別の点への最小パスを見つけるように調整されており、いわば途中で他の多くのパスを削除します。このため、重複するパスを含めると、すべてのパスを見つけるために使用することはできません。

グラフで幅優先検索を実行し、カバー ツリーの各ブランチをオン スタックに保持し (ノードが非常によく接続されている場合は膨大な量のブランチを取得します)、深さ N で停止することで、目標を達成できます。 B に到達したすべてのブランチは脇に置かれます。深さ N をカバーしたら、B に到達しなかったすべてのパスを削除します。残りのパスと、脇に置いたパスをまとめて解とします。

パスにサイクルを持たないという制限を追加することを選択できます。その場合、検索の各ステップで、新しく到達したノードがこれまでにカバーされたパスに既にあるかどうかを確認し、そのパスが場合。

ここにいくつかの擬似コードがあります:

function find_paths(graph G, node A):
list<path> L, L';

L := empty list;
push path(A) in L;
for i = 2 to N begin
   L' := empty list;
   for each path P in L begin
       if last node of P = B then push P in L'
       else
       for each successor S of last node in P begin
           if S not in P then
              path P' := P;
              push S in P';
              push P' in L';
           endif
       end
       endif
   end
   L := L';
end

for each path P in L begin
  if last node of P != B
  then remove P from L
  endif
end
return L;
于 2012-11-18T01:15:25.077 に答える