問題タブ [minimum-spanning-tree]

プリムのアルゴリズムの優先キュー実装の最悪のケースの実行が確認されている V 頂点と E エッジを持つグラフのファミリをどのように説明できますか?

ノードのグラフ (ネットワーク) があるとします。重み付けは次のとおりです。 1. 2 つのノード間のリンクを片道移動する。2. 2 つのノード間のリンクを逆方向に移動する (これらは異なる場合があります)。3. あるリンクから別のリンクへの変更。

また、一部のノードは一方向のみです。

この場合、次の場合に最適なアルゴリズムは次のとおりです。a) 最小スパニング ツリーを見つける b) 2 つのノード間の最短ルートを見つける c) 「巡回セールスマン」パス (つまり、どこにでも行き、重複を最小限に抑える最短ルート) を見つける?

また、双方向のものを、各方向に異なる重みを持つ双方向パスではなく、2 つの単方向パスとして扱うのが最善でしょうか?

- -例 - -

<2/3> は、左に移動する 2 と右に移動する 3 の重量を意味します。^1/4 は、1 が上に移動し、4 が下に移動することを意味します。2 つのリンク間の 1 つの数値は、リンクを変更するコストです。たとえば、AD から DF に移動するには 8 のコストがかかり、AB から BE に移動するには 2 のコストがかかります。

それが理にかなっていることを願っています...

サイモン

（ps悪い用語についてお詫びします-「リンク」、「エッジ」-好きなものなら何でも;））

重み付けの種類をよりよく説明するために、エッジが線路であり、ノードが駅であると想像してください。エッジのコストは 2 つの駅間の電車の移動時間であり、ノードのコストはインターチェンジ時間の長さです (プラットフォームがどれだけ離れているかによって、同じノードであってもエッジ間で異なる場合があります。サービスの定期性など）。

私には本当に苦労している問題があります。重み付けされたエッジを持つポイントのセットがあり、必要なエッジの最短量を見つけるために最小スパニング ツリーを作成する必要があります。私はJavaでそれを行う必要があります。現在、隣接行列を作成していますが、それが問題です。次にどこに行けばいいのか本当にわかりません。どんな助けでも素晴らしいでしょう。

環境：

小さい (現在は 100 未満) ですが、正規表現のコレクションが増えています。特定のテキスト文字列に対して、コレクション内のどの正規表現がテキスト文字列と一致するかを判断するプロセスを最適化したいと考えています。

一部の RE には順序関係があります。たとえば、文字列 $t が /windows/i に一致することがわかっている場合、$t が /windows.*2000/i に一致することもわかっています。したがって、コレクション内の RE に対して $t をテストするとき、/windows.*2000/i に対して $t を既にテストして一致が見つかった場合は、/windows/i のテストをスキップできます (ただし、/windows.*2000/i が一致する場合)。一致しない場合、もちろん/windows/i に対するテストをスキップできません)。

私のコレクションの RE はどれも完全に同等ではないことに注意してください (RE の任意のペアには、一方に一致し、他方に一致しないテキスト文字列が少なくとも 1 つ存在します)。

ストラテジー：

コレクション内の各 RE のノードと、順序関係 (A -> B は「A との一致は B との一致を意味する」という意味) を持つ RE の各ペアの有向エッジを持つ有向グラフ G を構築し、グラフのノードの「最小スパニング セット」(G 内のすべてのノードが S から始まる有向パス上にあるようなノード S の最小セット)。

簡単な部分:

有向非巡回グラフを操作するための自由に利用できるアルゴリズムが多数あります。したがって、グラフ G が RE のコレクションに対して構築されると (G が非巡回であることは明確であることが保証されるはずです)、G の最小スパン集合を見つけるための適切なアルゴリズムを見つけるのにそれほど苦労することはないと思います。

助けが必要な場所:

コレクション内の RE 間のすべての順序関係を見つける効率的な方法を見つけたいと考えています。また、コレクション内の 2 つの RE が同等でないことを確認するためにも必要です (新しい RE が同じであるため、これを自動的に検証する方法が必要になります)。追加した）。

したがって、私の (基本的にランダムな) Web 検索では、2 つの RE 間に存在する順序関係 (存在する場合) を計算する合理的な方法が実際に存在するというもっともらしい主張が少なくとも 1 つ見つかりましたが、完全なアルゴリズムの説明はまだ見つかっていません。

合理的に効率的で、自由に利用でき、(理想的には) 一般的なスクリプト言語または C/C++ のいずれかで実装されている (RE を比較するための) 既存の実装を知っている人はいますか?

プロジェクトの1つに隣接行列を作成しましたが、その行列から最小全域木を構築できる必要があります。読んでみると、この場合にはプリムのアルゴリズムが最適であるように見えますが、作業する必要のあるグラフの少なくとも1つに約数千のグラフがあることを知っているため、グラフが1つの大きな連結成分であるとは想定できません。接続されたコンポーネント。プリムのアルゴリズムはここでも実行可能ですか？実行可能な場合、私が行う必要のある追加のことはありますか？

ここではJavaでコーディングしていますが、隣接行列をうまく構築できます。この部分に固執しているだけです。

グラフを調べて、ある ID のすべてのインスタンスを新しい ID に変更しようとしましたが、それでもサイクルが発生しました。非環式解を解く計画とは?

MST (Minimum Spanning Tree)新しいノードを追加した後、またはウェイの距離を変更した後、どのように見つけますか？

これを解決するために助けが必要です。誰か助けてもらえますか？

ありがとう。

「したがって、プリムのアルゴリズムの合計時間は O(V lg V + E lg V) = O(E lg V) であり、これはクラスカルのアルゴリズムの実装と漸近的に同じです。」

http://serverbob.3x.ro/IA/DDU0137.htmlより

しかし、なぜ O(V lg V + E lg V) = O(E lg V) なのですか??

E が少なくとも V-1 だからですか?

igraph ライブラリを使用して、C で作業しています。特定のグラフ ストアの最小スパニング ツリーを igraph_graph_t タイプ (g) で取得する必要があります。また、各エッジの重み (w) を含む igraph_vector もあります。以下は私の呼び出しです：

mst グラフの各エッジの重みを取得するにはどうすればよいですか? 必要なのは、mst のコストだけです。

ありがとう、ギレルモ。

私は igraph ライブラリを使用して C で作業しています。

次の呼び出しを使用して、グラフの最小スパニング ツリーを計算する必要があります。

どこ：

• input_graph:処理するグラフ。igraph_t型です。
• mst_tree:関数によって返される mst ツリー。igraph_t型です。
• w: input_graph グラフの各エッジの重みを持つベクトル。igraph_vector_t型です。

igraph ライブラリで要求されているように、エッジと重みの間の関連付けはインデックスによって与えられます。つまり、 input_graphの最初のエッジにはwベクトルの最初の要素によって与えられる重みがあり、2 番目のエッジの重みは次のように与えられます。 wベクトル の 2 番目の要素など。

mst_treeのエッジはinput_graph のエッジのサブセットであるため (したがって、input_graph と mst_tree のエッジの量は異なります) 、インデックスを関連付けてmst_treeのエッジの重みを取得することはできません。

mst_tree、input_graph、および wのみを知っているmst_treeの各エッジの重みを取得する igraph 関数がいくつかありますか?

ギレルモ。