1493194204 有向グラフの部分パスを列挙するアルゴリズムを教えて下さい。


今、添付画像の様な有向グラフが有ります。
ノード数Nは12~40程度です。
このグラフから、以下の条件を満たす部分パスを列挙するアルゴリズムを教えて貰いたいです。

1. 任意のノードを始点とする。
2. パスのn番目とn+1番目のノードは、有効エッジで結ばれている。
3. パス中に含まれるノードは、重複しないか、又は、重複するノードでパスが終端する。

例えば、添付画像のKを始点とする場合に、以下の集合を得たいです。

 { K→L, K→L→M, K→L→M→K, K→M, K→M→K }

ざっと検索した結果、BDD/ZDDというキーワードが出てきましたが、これが私の希望するアルゴリズムでしょうか?
(この方向で情報収集を続けて良いか、もっと良い別のアルゴリズムがあるか迷っています。)

また、BDD/ZDDはどの程度のオーダで計算可能でしょうか?
(実用上はパスの長さの上限を5~10程度に設定する事も可能です。)

長々と書いてしまいましたが、一部の回答のみでも結構ですので、よろしくお願いします。

回答の条件
  • 1人10回まで
  • 登録:2017/04/26 17:10:04
  • 終了:2017/05/26 17:10:04
id:cdaotg

質問者から補足です。
列挙アルゴリズムですが、並列化による性能向上は無視してもらって構いません。
多数の有向グラフに対して、1スレッドで1グラフのパス列挙を行う方式で並列化しますので、単一グラフに対してはシングルスレッドでの解法があれば十分です。
以上です。よろしくお願いします。

回答(0件)

回答はまだありません

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません