問題タブ [graph-traversal]

Haskell でツリーを表現するのは非常に簡単です。

ただし、これは、各ノード/リーフに親が 1 つしかないため、命令型スタイルの「ポインター」の概念が必要ないためです。私はそれを s のリストのリストとして表すことができると思います...間にパスのないノードとパスを持つノードMaybe Intのテーブルを作成します...しかし、それは本当に醜くて扱いにくいようです。NothingJust n

nノード（重みが異なる）の完全に接続されたグラフが与えられた場合...ノードA（開始ノード）から他のすべてのノードに移動して戻るための最も安価なサイクルを提供するアルゴリズムがあるかどうか疑問に思っていましたノードAへ？これを達成するためにプリムのようなアルゴリズムを変更する方法はありますか?

ご協力いただきありがとうございます

編集：私は無向グラフを扱っていることを忘れていたので、各頂点のイン度=アウト度です。

私は人工知能から引用します: A Modern Approach :

深さ優先探索の特性は、グラフ探索とツリー探索のどちらを使用するかによって大きく異なります。繰り返される状態と冗長なパスを回避するグラフ検索バージョンは、最終的にすべてのノードを展開するため、有限状態空間で完全です。一方、ツリー検索バージョンは完全ではありません[...]。深さ優先ツリー検索は、ルートから現在のノードへのパス上の状態に対して新しい状態をチェックするように、追加のメモリ コストなしで変更できます。これにより、有限状態空間での無限ループは回避されますが、冗長パスの増殖は回避されません。

ツリーが特定のグラフであるため、グラフ検索が完了し、ツリー検索が完了しない方法がわかりません。

その上、「無限ループ」と「冗長パス」の違いがはっきりとわかりません...

誰かが私にこれを説明してもらえますか?

ps。本をお持ちの方は86ページ（第3版）です。

グラフ/ネットワークを操作するための優れた JavaScript ライブラリに関する推奨事項をお願いします。私は視覚化には興味がありません。最短経路を見つけたり、木にまたがったりするようなものです。

私はcrowを見てきましたが、かなり良さそうですが、オブジェクト指向です。

underscore.js のような機能モデルは私の好みですが、必須ではありません。

私はこれにドリルダウンする問題に取り組んでいます:

接続された無向グラフがあります。ノードに複数回アクセスせずに、すべてのノードにアクセスする必要があります。任意のノードで開始および終了できます。

これについてどうすればよいですか？可能なすべての開始ノードに同様のアルゴリズムを適用するFloyd-Warshall必要がありますか、それともより良い方法がありますか?

ありがとう。

これを行うにはどうすればよいですか？これは宿題で、私はそれで大きな問題を抱えています。さて、問題は、ライブラリを使用してはならないということです。

次のようなグラフがあります。

ファイルから取得した辞書を使用します。

http://www.python.org/doc/essays/graphs/のアルゴリズムを使用してすべてのパスを見つけているので、問題はありません。

しかし、あるポイントから別のポイントへのすべてのパスを取得したので、重みを合計して、その完全なコストを取得する必要があります。

あなたが私を助けて、それに近づくための良い方法を教えてくれたら、私はそれを感謝します.

次の検索を実行するTraversalDescriptionを作成しようとしています。

• 特定のプロパティ ("type" == "PERSON") を持つノードのみを返す
• 特定の固定数の結果を返す (グラフ全体が巨大で、ローカル グラフのみに関心がある)
• 任意の関係タイプを使用できます

ノード プロパティのエバリュエーターを作成する方法がわかりません。

以下のような無向グラフがあります。グラフ走査アルゴリズムを実装する必要があります。 例： http:
//i.imgur.com/15L6m.png

各頂点が都市であり、各エッジが道路であるという考え方です。
エッジの重みは、指定されたエッジを通過するのに必要な時間を表します。
条件は次のとおりです。

1. 各エッジは、指定された時間枠 (Time Open1、Time Open2、TimeClose1、Time Close2) でトラバーサル用に開いています。エッジをトラバースするには、現在の時間がこれらの間隔内にある必要があります。
   
2. 一部の頂点のみを訪問する必要があります。頂点は、それぞれ指定された時間枠内で少なくとも 1 回訪問する必要があります: Time Open1、Time Open2、TimeClose1、Time Close2 - 頂点を訪問済みとしてマークするには、現在の時間がこれらの間隔内にある必要があります。
   
3. 始点は常に頂点 0
   

私の例では、
訪問する必要がある頂点とその時間枠 (-1 の値は考慮されません):

エッジは次の時間枠で開いています (-1 の値は考慮されません)。

したがって、基本的な考え方は、頂点 0 から開始し、指定された時間を考慮して頂点 1、4、および 5 を通過する最短ルートを見つけることです。
また、たとえば、0-1 を実行したが 1-5 を使用できない場合は、0-1-0-1-5 を実行できます。

私が現在取り組んでいる可能な解決策は次のとおりです
。0から開始します。最短時間でマークする最も近い頂点を見つけます（修正されたダイクストラアルゴリズムを使用します）。必要なすべての頂点をマークするまでこれを行います。問題
は 、私がすべての可能性を見つけているとは思わないことです.0-1-0-1-5の組み合わせのように動き回ることもでき、最終的にはより短いルートになる可能性があるためです. .

より明確にするために、エッジとターゲット頂点に課せられた条件を考慮して、他のすべてのターゲット頂点を少なくとも 1 回訪れながら、頂点 0 から開始し、1 つのターゲット頂点で終了するように、最短パスを見つける必要があります。
例:
考えられる解は 0 - 4 - 3 - 5 - 1 で、合計時間は 60+50+60+50=220
0 から 5 に直接行くこともできますが、頂点 5 をマークするための条件に記載されているとおりです。累積時間は 170 から 450 の間でなければなりません。また、0-4 にすると、エッジ 4-2 を使用できません。これは、80 で開き、累積時間が 60 であるためです。4 であるため、0-4-3 を使用できることに注意してください-3 は 60 で開き、0-4 を実行するには 60 の時間がかかります。

まず、最大で 20 個の頂点と最大で約 50 個のエッジを使用するという制約があります。

解決策 1:
0
1 4 5 0 2 5 0 2 3 0 1 3

私がしていることは、ツリーに似たものを構築する隣接する各頂点にアクセスして、グラフをトラバースすることです。次の場合に枝の展開を停止します:
1. 0 1 0 4 0 1 0 のように重複が多すぎます - 重複する 0 値のセット数が 4 であるため停止します
2. すべてを含む道路を見つけますマークする頂点
3. 別の完全な道路よりも時間がかかる道路を見つけた
4. エッジが閉じているため、別のノードを作成できない

解決策 2:

@Boris Strandjevの例を適用していますが、いくつか問題があります:

ノード 1、4、および 5 をその間隔で少なくとも 1 回訪問する必要があります。間隔外の訪問は許可されますが、マークは付けられません。頂点の場合、{(< id1, id2id3id4>, time)} があります。ここで、id1 は現在の頂点の ide であり、id2-4 は、指定された間隔でアクセスされた場合、1,4,5 の bool 値を表します。時間 -パス内の現在の時刻

編集：

上記の2つのソリューションを組み合わせて使用​​することになりました。すべてがうまくいくようです。

トラバースしたい有向非循環加重グラフがあります。

有効なソリューション ルートの制約は次のとおりです。

1. ルートで通過するすべてのエッジの重みの合計は、2 番目の制約を念頭に置いて、グラフ内で可能な限り高くする必要があります。
2. 選択したルートで正確に N 個の頂点を訪れている必要があります (開始頂点と終了頂点を含む)。

通常、グラフには大量の頂点とエッジがあるため、すべての可能性を試すことはオプションではなく、非常に効率的なアルゴリズムが必要です。

この問題に対するいくつかのポインタまたは適切なアルゴリズムを探しています。ダイクストラのアルゴリズムを使用して最初の条件が簡単に満たされることはわかっていますが、2 番目の条件を組み込む方法や、どこから調べればよいかさえわかりません。

追加情報が必要な場合はお知らせください。

無向巡回グラフが与えられた場合、幅優先探索または深さ優先探索を使用して、可能なすべてのトラバーサルを見つけたいと考えています。それは隣接リストとしてグラフを与えられます:

したがって、ルート A からのすべての BFS パスは次のようになります。

DFS の場合:

これらのトラバーサルを意味のある方法でアルゴリズム的に生成するにはどうすればよいですか? 文字のすべての順列を生成してその有効性をチェックできると思いますが、それは最後の手段のように思えます。

どんな助けでも大歓迎です。