グラフ内のすべての「長い」単純な非循環パスを見つけるにはどうすればよいですか？

Question

完全に接続された有向グラフGがあるとします。頂点は[a,b,c]です。各頂点の間には両方向にエッジがあります。

出発点がaの場合、私はすべての方向でグラフをたどり、既にパスにある頂点に当たったときにのみそのパスを保存したいと思います。

ので、機能full_paths(a,G)は返す必要があります：

- [{a,b}, {b,c}, {c,d}] 
- [{a,b}, {b,d}, {d,c}] 
- [{a,c}, {c,b}, {b,d}] 
- [{a,c}, {c,d}, {d,b}] 
- [{a,d}, {d,c}, {c,b}] 
- [{a,d}, {d,b}, {b,c}] 

をそれはすでに最初の結果に含まれているので、私は、[{a,b}]または[{a,b}, {b,c}]のような「不完全」な結果を必要としません。

Gのパワーセットを生成し、特定のサイズの結果を除外する方法はありますか？

どうすれば計算できますか？

編集は：イーサンが指摘したように、これは深さ優先探索の方法で解決できるが、残念ながら、私はそれを変更する方法を理解していない、それは（私が実装するためのRuby Gratr使用後戻りする前に、それはパスを保存すること私のアルゴリズム）

Answer 1

depth first searchまたはいくつかのバリエーションを調べましたか？深さの最初の探索は可能な限り横切ってから後退します。バックトラックする必要があるたびにパスを記録することができます。

Answer 2

あなたが知っている場合は、あなたのグラフGはNグラフGの頂点の数であるとき、長さNのN!パスがあり、完全に接続されています。この方法で簡単に計算できます。 Nの開始点を選択できます。開始点ごとに、N-1頂点をパス上の2番目の頂点として選択することができます。最後に訪問しなかった頂点のみを選択することもできます。したがって、可能なパスはN*(N-1)*...*2*1 = N!です。開始点を選ぶことができない場合、つまり、グラフ内のパスを見つけることと同じです。G'N-1の頂点を使用します。すべての可能なパスは、すべての頂点のセットの並べ替えです。つまり、開始点を除くすべての頂点です。あなたは順列を持っている場合、あなたはしてパスを生成できます。

perm_to_path([A|[B|_]=T]) -> [{A,B}|perm_to_path(T)]; 
perm_to_path(_) -> []. 

順列を生成するための方法を

最も簡単な方法は、だからあなたの場合には

permutations([]) -> []; 
permutations(L) -> 
    [[H|T] || H <- L, T <- permutations(L--[H])]. 

です：

GVはの頂点のリストである

paths(A, GV) -> [perm_to_path([A|P]) || P <- permutations(GV--[A])]. 

グラフG。

もっと効率的なバージョンをご希望の場合は、少しばかげてしまいます。