人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

今、添付画像の様な有向グラフが有ります。
ノード数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程度に設定する事も可能です。)

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

1493194204
●拡大する

●質問者: cdaotg
●カテゴリ:コンピュータ 科学・統計資料
○ 状態 :キャンセル
└ 回答数 : 0/0件

▽最新の回答へ

質問者から

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


関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ