8

n ノードのセットが 2 つあります。ここで、あるセットの各ノードを別のセットの別のノードに接続したいと考えています。結果のグラフには交差がないはずです。

私はいくつかのスイープ ライン アルゴリズムを知っています (交差が発生する場所を確認するための Bentley-Ottmann-Algorithmですが、これらの交差を解決するためのアルゴリズムは、ブルート フォース アプローチを除いて見つかりませんでした。

1 つのセットの各ノードは、他のセット内の任意のノードに接続できます。

この問題を解決する (効率的な) アルゴリズムへのポインターはありますか? 実装は必要ありません。

EDIT1：

の問題に対する 1 つの解決策を次に示しますn=7。

交差点の問題

黒い点はノードのセットで、赤い点はセットです。黒の各ノードは、それらを結ぶ線が交差しないように、1 つの赤のノードに接続する必要があります。

EDIT2：

さらに明確にするために：すべてのノードの位置は固定されており、結果のグラフにはn個のエッジがあります。また、解決策が存在するという証拠もありませんが、解決策がない例を作成できませんでした。このような平面グラフの作成が常に可能であるという証拠がどこかにあると確信しています。また、考えられるすべてのソリューションではなく、 1 つのソリューションのみが必要です。

4

1 に答える 1

7

解が存在する場合 (そうでない例を示す私のコメントを参照してください)、すべての点とすべての赤について (赤または黒の) 頂点を含む完全な 2 部グラフで一致する最小の重みを見つけることによって見つけることができます。頂点 u と黒い頂点 v、重みが対応する点間のユークリッド距離に等しいエッジ (u, v)。これは O(V^4) 時間で最適に解決できます。

なぜこれが機能する必要があるのですか？David Eisenstat の同様の質問への回答から得た主なアイデアは、点 X で交差する線分 AB と CD のペアがあるときはいつでも、三角形の不等式を使用して、それぞれの端点のいずれかを選択することを示すことができるということです。それらを交換すると、全長が短いか等しい線分のペアが得られます。

A
|\
| \
|  \ X
C---+-----D
     \   /
      \ /
       B

AX + XC >= AC (tri. ineq.)
BX + XD >= BD (tri. ineq.)
AX + XC + BX + XD >= AC + BD (sum both sides)
(AX + BX) + (XC + XD) >= AC + BD (rearrange LHS)
   AB     +    CD     >= AC + BD (combine pairs of segments on LHS)

さらに、三角形 AXC と BXC が非縮退であると仮定すると、 は に>=なります>。(このための十分条件は、少なくとも 1 つの赤点と 1 つの黒点を含む 3 つの点のセットが同一線上にないことです。) したがって、任意の解 (赤のノードを黒のノードに割り当てる) について、その解に交差が含まれる場合、線分の長さの合計は、交差する 2 つの線分セグメントの赤 (または黒) の端点を交換することにより、0 以外の量だけ減らすことができます。

言い換えると、

Solution contains a crossing => sum of segment lengths is not minimal.

対偶を取ると、すぐに得られます

Sum of segment lengths is minimal => solution contains no crossing.

最小重みマッチング アルゴリズムは可能な限り最小の重みの解を返すため、これによってその正確性が確立されます。

(エンドポイントの交換が実際に線分 AC と BD の新しいペアが交差しないことを保証するかどうかについて心配する必要はないことに注意してください -- 交差しないことは明らかですが、実際に必要なのは正しさの証明はそれを示すことcrossing exists => sum not minimalです。)

于 2016-06-29T14:35:25.797 に答える