次数10 ^ 5の完全グラフのEMSTを見つけるための最も単純で最も簡単なアルゴリズムは何ですか

タイトルが示すように、実際にはEMSTが必要であり、TSPはそのための手段にすぎず、実際の目標そのものではないと想定します。この2つには非常に異なる制限があり（TSPははるかに制限が厳しい）、したがって非常に異なる最適なソリューションがあります。

概要概要

アイデアは、修正されたクラスカルのアルゴリズムを実行したいということです。これは、kdツリーを利用して、すべての潜在的なエッジを評価せ​​ずに最も近いペアを見つけます。接続されたコンポーネントの各頂点への最短のエッジを見つけ、全体として最短にし、そのエッジを介して接続されたコンポーネントを接続できます。ご覧のとおり、これは各反復で接続されたコンポーネントの少なくとも半分を接続するためlogn、完了するまでに最大で反復が必要です。

最近傍検索

EMSTを構築するには、データ構造を使用して4D空間の最近傍を照会する必要があります。八分木を拡張してより高い次元で機能させることもできますが、私は個人的にkd木を使用します。O(nlogn)中央値の中央値アルゴリズムを使用して時間内にkdツリーを構築し、各レベルの中央値を見つけることができますO(logn)。また、バランスの取れたkdツリーを時間内に挿入/削除できます。

kdツリーを構築したら、各ポイントに最も近いネイバーをクエリする必要があります。次に、これら2つの頂点の間にエッジを作成します。これらのエッジの多くは、いくつかの頂点のように、複製されますAとB、Aの最も近い隣人はかもしれB、とBの最近傍であってもよいですA。これは、各頂点が属する連結成分を格納することで処理します。2つの頂点がエッジで結合された後、重複するエッジは同じ連結成分の2つの頂点を明確に接続するため、破棄します。これを実現するために、（クラスカルのアルゴリズムの多くの実装と同様に）互いに素なセットを使用して、連結成分を各頂点に割り当てます。これにより、グラフにサイクルを作成して、MSTに不要なエッジを導入することもできなくなります。

マージ

ただし、各エッジを作成するときは、保持するエッジと、すでに接続されている頂点を接続しているエッジを確認する前に、それを最小ヒープ優先度キューに挿入する必要があります。これはこの最初の反復の結果には影響しませんが、後で距離を増やしてエッジを処理する必要があります。次に、すべてのエッジをデキューし、disjoint-setを介して不要/冗長なエッジをチェックし、有効なエッジをMSTに挿入して、それぞれのdisjoint-setをマージします。もちろん、これはすべてnlogn、最小ヒープから要素を構築およびデキューするための要素を導入します（必要に応じて、単純な配列に要素を並べ替えることもできます）。

エッジを追加するこの最初の反復の後、MSTの少なくとも半分、おそらくそれ以上を接続します。これは、頂点ごとに1つのエッジを追加し、エッジごとに最大で1つの複製を作成できるため、vertices / 2エッジとしていくつか追加しましたが、最大でvertices - 1。これで、MSTの少なくとも1/2が構築されました。vertices - 1合計でエッジを追加するまで、次の段落で説明するプロセスを続行します。

NN検索の一般化

続行するには、接続された各コンポーネントの頂点のリストを作成して、グループごとに頂点を反復処理できるようにします。互いに素な集合の検索（マージも）にはO(α(n))時間がかかり（α逆アッカーマン関数である）、正確にn何度も繰り返すため、これはほぼ線形の時間で実行できます。接続されたコンポーネントごとの頂点のリストができたら、残りはかなり簡単です。既存のkdツリーを取得し、現在接続されているコンポーネントのすべての頂点を削除します。次に、連結成分の各頂点の各頂点に最も近い隣接ノードをクエリし、これらのエッジを最小ヒープに追加します。次に、これらの頂点をkdツリーに追加し直し、次に接続されているコンポーネントで繰り返します。合計で挿入/削除するのでn要素の場合、これは平均的なケースO(nlogn)時間の複雑さになります。

接続されたコンポーネントを接続する最短の潜在的なエッジのキューができたので、これらを順番にデキューし、前と同じように有効なエッジを挿入して、互いに素なセットをマージします。以前と同じ理由で、これにより、コンポーネントの少なくとも半分、場合によってはすべてが接続されることが保証されます。すべての頂点を単一の連結成分（MST）に接続するまで、このプロセスを繰り返します。反復ごとに切断されたコンポーネントの数が半分になるためO(logn)、MSTのすべての頂点を接続するのに最大で反復が必要になることに注意してください（おそらくはるかに少ない）。

備考

全体として、これにはO(nlog^2(n))時間がかかります。log(n)ただし、反復よりもはるかに少ない可能性が高いため、実際にはそこでの高速化を期待してください。また、Rツリーはkdツリーの優れた代替手段である可能性があることにも注意してください。ただし、実際にどのように比較されるかはわかりません。