Erlangの有向非巡回グラフで1つの頂点から可能なすべてのパスを見つけます

StackOverflow https://stackoverflow.com/questions/7834702

質問

有向非巡回グラフGのソース頂点Vからすべての可能な頂点へのすべての可能なパスを見つける関数を実装したいと思います。

パフォーマンスは今は関係ありません。アルゴリズムを理解したいだけです。深さ優先探索アルゴリズムの定義を読みましたが、何をすべきかを完全には理解していません。

次の方法がわからないため、ここで提供する完成したコードはありません。

  • 結果を保存します（A-> B-> C->とともに、A-> BおよびA-> B-> Cも保存する必要があります）。
  • グラフを表す（有向グラフ？タプルのリスト？）;
  • 使用する再帰の数（隣接する各頂点で機能しますか？）

    Erlangの有向非巡回グラフで1つの特定のソース頂点から可能なすべてのパスを見つけるにはどうすればよいですか？

    UPD：これまでの回答に基づいて、グラフの定義を再定義する必要があります。これは非非巡回グラフです。私の再帰関数がサイクルにヒットした場合、それは不定ループであることを私は知っています。これを回避するには、現在の頂点が結果のパスのリストに含まれているかどうかを確認します。含まれている場合は、トラバースを停止してパスを返します。

    UPD2：考えさせられるコメントをありがとう！はい、1つのソース頂点から他のすべての頂点へのループがないすべての単純なパスを見つける必要があります。

    次のようなグラフの場合：

    非巡回グラフ

    ソース頂点Aを使用すると、アルゴリズムは次のパスを見つける必要があります。

    • A、B
    • A、B、C
    • A、B、C、D
    • A、D
    • A、D、C
    • A、D、C、B

      次のコードは機能しますが、頂点が20を超えるグラフでは使用できません（再帰の問題だと思います。メモリが多すぎて終了しません）： ジェネラコディセタグプレ

      UPD3：

      問題は、通常の深さ優先探索アルゴリズムが最初にパス（A、B、C、D）または（A、D、C、B）のいずれかに移動し、2番目のパスには移動しないことです。

      どちらの場合も、これが唯一のパスになります。たとえば、通常のDFSが（A、B、C、D）からバックトラックすると、Aに戻り、D（Aの2番目のネイバー）にアクセスしたかどうかを確認します。 。また、通常のDFSは各頂点のグローバル状態を維持するため、Dは「訪問」状態になります。

      したがって、再帰に依存する状態を導入する必要があります。（A、B、C、D）からAまでバックトラックすると、結果のリストに（A、B、C、D）が含まれるはずです。アルゴリズムの最初の時点で、Dを未訪問としてマークする必要があります。

      末尾再帰のソリューションを最適化しようとしましたが、それでもアルゴリズムの実行時間は実行不可能です。頂点ごとに3つのエッジを持つ16の頂点の小さなグラフをトラバースするのに約4秒かかります。 ジェネラコディセタグプレ

      これを許容可能な時間内に実行するためのアイデアはありますか？

役に立ちましたか？

解決

編集： わかりました。有向グラフの頂点からすべての単純なパスを見つけたいと思います。したがって、ご存知のように、バックトラックを使用した深さ優先探索が適しています。一般的な考え方は、隣人に行き、次に別の人（あなたが訪れた人ではない）に行き、行き止まりに達するまで行き続けることです。次に、最後にいた頂点に戻って、別の隣接頂点を選択します。 あなたは厄介なビットを正しくする必要がありますが、それはそれほど難しいことではありません。例えば。すべてのステップで、頂点に「探索済み」または「未探索」のラベルを付ける必要があります。これは、以前に頂点にアクセスしたことがあるかどうかによって異なります。パフォーマンスは問題ではないはずです。適切に実装されたアルゴリズムはおそらくO（n ^ 2）時間かかるはずです。だから私はあなたが間違っていることを知りません、多分あなたはあまりにも多くの隣人を訪問していますか？例えば。たぶん、あなたはすでに訪れた隣人を再訪し、ループか何かを回っています。

私はあなたのプログラムを実際には読んでいませんが、深さ優先探索のWikiページには、あなたの言語でコピーを試みることができる短くて単純な擬似コードプログラムがあります。グラフを隣接リストとして保存して、簡単にします。

編集： はい、申し訳ありませんが、その通りです。標準のDFS検索はそのままでは機能しません。以前にアクセスした頂点に再度アクセスできるように、少し調整する必要があります。したがって、現在のパスにすでに保存されている頂点を除いて、すべての頂点にアクセスできます。 もちろん、これは私の実行時間が完全に間違っていたことを意味します。アルゴリズムの複雑さは屋根の向こう側にあります。グラフの平均複雑度がd + 1の場合、およそd * d * d * ... * d= d ^ nの可能なパスがあります。 したがって、すべての頂点に隣接する頂点が3つしかない場合でも、頂点が20を超えると、かなりの数のパスが存在します。 プログラムにすべての可能なパスを出力させたい場合は、実際にそれらのすべてのd ^ nを出力する必要があるため、これを回避する方法は実際にはありません。

特定のタスクにこれが必要なのか、それとも単に興味を持ってプログラムしようとしているのかを知りたいです。後者の場合は、小さくてまばらに接続されたグラフに満足する必要があります。

他のヒント

質問がわかりません。グラフG=（V、E）=（{A、B}、{（A、B）、（B、A）}）がある場合、AからBへの無限のパスがあります{[A、B]、[ A、B、A、B]、[A、B、A、B、A、B]、...}。閉路グラフの頂点へのすべての可能なパスを見つけるにはどうすればよいですか？

編集：

いくつかのグラフで可能なパスの成長を計算したり推測したりしましたか？グラフが完全に接続されている場合は、次のようになります

  • 2-1
  • 3-4
  • 4-15
  • 5-64
  • 6-325
  • 7-1956
  • 8-13699
  • 9-109600
  • 10-986409
  • 11-9864100
  • 12-108505111
  • 13-1302061344
  • 14-16926797485
  • 15-236975164804
  • 16-3554627472075
  • 17-56874039553216
  • 18-966858672404689
  • 19-17403456103284420
  • 20-330665665962403999

    すべてのノードのすべてのパスを検索してもよろしいですか？つまり、1秒間に1ミリオンのパスを計算する場合、20ノードの完全接続グラフですべてのノードへのすべてのパスを計算するには1 0750年かかります。それはあなたの仕事の上限なので、あなたはそれをしたくないと思います。他に何か欲しいと思います。

決して改善されたアルゴリズムソリューションではありませんが、多くの場合、複数のワーカースレッドを生成することでパフォーマンスを改善できます。これにより、単純なブルートフォースアルゴリズムを比較的簡単に改善できることがよくあります。

ここに例を見ることができます：いくつかのErlang行列関数、maximise_assignment関数内（今日の時点で191行目からコメント）。繰り返しになりますが、基礎となるアルゴリズムにはかなり素朴で野蛮な力がありますが、並列化により、多くの形式の行列で非常に高速になります。

過去に同様のアプローチを使用して、グラフ内のハミルトンパスの数を見つけました。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top