1

最小スパニング ツリー問題は、接続された重み付きグラフを取得し、グラフを接続したまま (結果として非循環グラフが生成される) で、合計重みが最小のエッジのサブセットを見つけることです。

私が検討しているアルゴリズムは次のとおりです。

  • すべてのサイクルを見つけます。
  • 各サイクルから最大のエッジを削除します。

このバージョンの推進力は、反復的な構造を持たない「ルールの満足」に制限された環境です。また、非常に並列なハードウェア (つまり、サイクル数より数倍の並列度が期待されるシステム) にも適用できる場合があります。

編集:

上記はステートレスな方法で行われます (どのサイクルでも最大のエッジではないすべてのエッジが選択/保持/無視され、その他はすべて削除されます)。

4

7 に答える 7

1

2 つのサイクルが重なるとどうなりますか? 最長のエッジが最初に削除されたのはどれですか? それぞれの最長エッジが 2 つのサイクル間で共有されているかどうかは重要ですか?

例えば：

V = { a, b, c, d }
E = { (a,b,1), (b,c,2), (c,a,4), (b,d,9), (d,a,3) }

a -> b -> c -> a サイクルと、a -> b -> d -> a があります。

于 2008-09-01T05:16:46.487 に答える
1

あなたのアルゴリズムは明確に定義されていません。完全なグラフがある場合、アルゴリズムは、最初のステップで 2 つの最小要素を除くすべてを削除する必要があるように見えます。また、グラフ内のすべてのサイクルを一覧表示するには、指数関数的な時間がかかる場合があります。

詳細:

n 個のノードとノードのすべてのペアの間にエッジがあるグラフでは、サイクルをサブグラフとしてカウントしている場合、私の数学が正しければ、サイズ k の n!/(2k(nk)!) サイクルがあります。各ノードの次数が 2 の k 個のノードと k 個のエッジ。

于 2008-09-01T05:21:53.293 に答える
1

@shrughes.blogspot.com:

2つを除くすべてを削除することについてはわかりません-アルゴリズムのさまざまな実行をスケッチしており、並列実行によりエッジが複数回削除される可能性があると想定しています。スパニングツリーなしで残っている状況を見つけることができません. 最小かどうかはわかりません。

于 2008-09-01T05:29:56.987 に答える
1

これが機能するには、明らかに反復構造なしですべてのサイクルを見つける方法を詳しく説明する必要があります。これは簡単ではないタスクだからです。それが可能かどうかはわかりません。反復構造を使用しない MST アルゴリズムを本当に見つけたい場合は、PrimまたはKruskal のアルゴリズムを見て、ニーズに合わせてそれらを変更できるかどうかを確認してください。

また、この理論上のアーキテクチャでは再帰は禁止されていますか? もしそうなら、グラフ上のすべての頂点/エッジを検査する手段がまったくないため、グラフ上で MST を見つけることは実際には不可能かもしれません。

于 2008-09-01T06:46:27.300 に答える
1

それが機能するかどうかはわかりませんが、アルゴリズムが何であれ、実装する価値さえありません。すべてのサイクルを見つけることは、それを殺す非常に大きなボトルネックになります。また、反復なしでそれを行うことは不可能です。Primの.

于 2008-09-01T07:17:30.567 に答える
0

OK、これは正当性の証明を完成させる試みです。逆削除アルゴリズムと同様に、十分なエッジが削除されることがわかります。残っているのは、多くのエッジが削除されないことを示すことです。

多くのエッジを削除することは、グラフノードのバイナリパーティションの側面の間のすべてのエッジを削除することとして説明できます。ただし、サイクル内のエッジのみが削除されるため、パーティション間のすべてのエッジを削除するには、サイクルを完了するためのリターンパスが必要です。パーティション間のエッジのみを考慮する場合、アルゴリズムはエッジの各ペアの大きい方を最大で削除できますが、最小のブリッジエッジを削除することはできません。そのため、任意のバイナリパーティション分割の場合、アルゴリズムはサイド間のすべてのリンクを切断できません。

残っているのは、これが2ウェイ以上のパーティションに拡張されることを示すことです。

于 2008-09-01T21:33:42.067 に答える
0

@Tynanシステムは、分類を記述するルールのシステムとして（やや単純化されすぎて）説明できます。「B にあるが C にないものはカテゴリ A にある」、「Z のノードに接続されたノードも Z にある」、「M のすべてのカテゴリはノード N に接続され、「子」カテゴリを持ち、 N に接続されたすべてのノードに対して M". これより少し複雑です。(不安定なルールを作成することで旋盤をモデル化できることを示しましたが、それは的外れです。) 繰り返しや再帰を明示的に定義することはできませんが、2 番目と 3 番目のようなルールを使用して再帰データを操作できます。

@Marcin、無制限の数のプロセッサがあると仮定します。プログラムが O(n^2) で実行され、n が最長サイクルであることを示すのは簡単です。より良いデータ構造を使用すると、これを O(n*O(set lookup function)) に減らすことができ、すべてのサイクルを一定時間で評価できるハードウェア (量子コンピューター?) を想像できます。MST 問題に O(1) ソリューションを提供します。

リバース削除アルゴリズムは、正しさの部分的な証明 (提案されたアルゴリズムが非最小スパニング ツリーを生成しないこと) を提供するように思われます。ただし、私のアルゴリズムがそのアルゴリズム以上のものを削除しないことを示す方法がわかりません。

うーん....

于 2008-09-01T19:47:27.847 に答える