問題タブ [graph-traversal]

私は現在、有向グラフ内の 2 つのノード (たとえば、と)の間のパスにあるすべてのノードを見つける効率的な方法を見つけようとしています。XY

私が最初に考えたのは、X から BFS を実行し、Y から BFS を実行し、訪問したノードの交差点を取ることでした。X と Y の間のすべてのパスを列挙する必要はなく、X から Y へのパス上にあるすべてのノードを見つけるだけであることに注意してください。

私の質問は、これを行うためのより最適化された方法はありますか?

シーンのエッジ マップがあり、空と地形を最もよく分離するエッジを抽出したいと考えています。これは、グラフ トラバーサルの問題として適切に組み立てられているようです。ただし、A* などの一般的な検索アルゴリズムは、開始点と終了点 (それぞれ最初と最後の列以外) の使用に依存しています。これらのパラメータを必要としないグラフ検索のアルゴリズムはありますか? また、滑らかさなど、抽出されたエッジのいくつかのグローバル機能を最大化したいと思います。注: 速度は重要な問題です。これはリアルタイムで行う必要があります。

各ノードと各エッジに値が付加された標準グラフがあるとします。最短時間でグラフ上の 1 つのノードから別のノードに移動したいと考えています。このグラフをトラバースするのにこれまでにかかった時間は T と呼ばれます。エッジの値が V の場合、そのエッジをトラバースすると V が費やされた時間に追加されます (T += V)。ノードの値が N の場合、そのノードをトラバースすると、費やした時間が N (T += (N - T % N) % N) で割り切れるまで待機する必要があります。

これは、通りや信号機のようなものと考えることができます。通りを運転すると、反対側に到達するまでに一定の時間がかかります。信号を通過すると、青になるまでの待ち時間が長くなります。

たとえば、次のグラフがあるとします。

一見すると、エッジが短く、遅延が短いトップ パスの方が高速に見えます。ただし、下のルートの方が速いことがわかります。最初に底を計算しましょう：

そしてトップ：

ご覧のとおり、下の方が短くなっています。このような小さなサイズでは計算が簡単ですが、都市のサイズでは、ある種のトラバーサル アルゴリズムを使用する必要があります。ブルートフォース以外に何らかの解決策があるかどうか知っている人はいますか?

ノードへの最小コストでルートを見つけたい。いくつかのルートが見つかりましたが、最小コストのルートはありません。

ノードに関する情報を格納するための私のクラス:

タプルにはint、intがあります-最初のintはエンドノード、2番目のintはこのノードへのルートのコストです

グラフをトラバースするクラス:

私の例では、ノード 6 への最小コストのルートを見つけたい

isConnected/1グラフを引数として取り、ペア間に無向パスがあるかどうかを判断する述語を作成する必要があります。

エッジのリストがあるとします（Gグラフはどこにありますか）：

したがって、3 と 4 の間にエッジがないため、これは失敗するはずです。
この問題にどのようにアプローチしますか？各エッジをトラバースして、エッジをリストに記録する必要がありますか? または、これを行うためのより良いアプローチはありますか?

からの値を持つ2つの互いに素な (サイズが のn) セット ( と と呼ばれる)0が与えられた場合、特定のトラバーサルによって形成された最後のエッジ (頂点のペア) を見つける必要があります。112n

トラバーサル アルゴリズム:

• start from value 1(この値がどのセットにあるかは関係ありません)
• それを反対側のセットからの最初の自由な値に接続します (最初は実際の値に対して相対的なので、現在の値が と等しい場合は、、、、...、、、3をチェックします)45672n - 12n12
• 2番目のステップを繰り返す

例：

この問題を2 * (1 + 2 ... + n) = 0(n^2)複雑に解決することができました。しかし、私はより良い解決策があると信じています。

PyYAML は、通常の Python オブジェクトで巡回グラフを処理できます。例えば：

スニペット #1。

このコードは成功するので、シリアライズされたオブジェクトをロードする際の無限再帰を防ぐ何らかのメカニズムがあることは明らかです。独自の YAML コンストラクター関数を作成するときにそれを利用するにはどうすればよいですか?

たとえば、は一時的なフィールドと、および非Node一時的なフィールド を持つクラスであるとします。yamlドキュメントにする必要があります。私はこれをしたいと思います：foobarchildchild

スニペット #2。

しかし、それは失敗します:

理由がわかります。私のコンストラクター関数は再帰用に構築されていません。親オブジェクトの構築を完了する前に子オブジェクトを返す必要があり、子と親が同じオブジェクトである場合は失敗します。

しかし、スニペット #1 が機能するため、明らかに PyYAML にはこの問題を解決するグラフ トラバーサルがあります。おそらく、すべてのオブジェクトを構築するための 1 つのパスと、それらのフィールドに値を設定するための 2 番目のパスがあります。私の質問は、カスタム コンストラクターをこれらのメカニズムにどのように結び付けることができるかということです。

その質問に対する答えは理想的です。しかし、答えがカスタムコンストラクターではこれを行うことができないというものであり、あまり望ましくない代替手段がある場合 (たとえば、YAMLObjectクラスを自分のNodeクラスに混在させるなど)、その答えも高く評価されます。