6

ノードが平面上のポイント上のポイントを表し、エッジがポイント間のおおよそのユークリッド距離である合計無向グラフがあります。このグラフを 2 次元空間に「埋め込み」たいと思います。つまり、各頂点を (x,y) 位置タプルに変換して、任意の 2 つの頂点 v と w について、エッジ (v,w) の重みが dist(v,w) に近い値になるようにします。

たとえば、ノード A、B、C、および D と重み (A,B) を持つエッジを持つグラフがある場合: 20; (A、C): 22; (A、D): 26; (B、C): 30; (B, D): 20、(C, D): 19 の場合、点 A: (0,0); を割り当てることができます。B: (10, 0); C: (0, 10); D: (10、10)。明らかにこれは不完全ですが、妥当な近似値です。

私は可能な限り最善の解決策を得ることは気にしません。妥当な時間内に合理的な解決策が欲しいだけです。

（この問題の動機が必要な場合に備えて。私は物理システムを持っており、すべてのポイントのペアからの距離の測定値にノイズがあります。距離の測定値にはノイズがありますが、真の値の 2 倍以内になる傾向があります。これらの測定をすべて行い、数千のノードと数百万のエッジを含むグラフを作成し、ポイントを平面に配置したいと考えています。)

4

2 に答える 2

3

必要に応じて、力ベースのグラフ描画アルゴリズムを適応させることができる場合があります。

G(V,E)このアルゴリズムは、の各頂点をVデカルトポイントとして扱い、の各エッジをE線形ばねとして扱うことにより、無向グラフの適切なレイアウトを見つけようとします。さらに、ペアワイズ反発力（つまりクーロンの法則）が頂点間でグローバルに計算されます。これにより、で隣接していないデカルト空間の頂点のクラスター化が防止されG(V,E)ます。

あなたの場合、スプリングの平衡長をエッジの重みに等しく設定できます。これにより、エッジの重みに近いペアワイズユークリッド頂点距離を持つレイアウトが得られます。

アルゴリズムは、各頂点での力の合計に基づいて、疑似時間ステップ方式で初期分布（場合によってはランダム）を更新します。アルゴリズムは、おおよその定常状態に達すると終了します。簡略化された擬似コード：

while(not converged)
    for i = vertices in V
        F(i) = sum of spring + repulsive forces on ith vertex
    endfor
    Update vertex positions based on force vector F 
    if (vertex positions not changing much)
        converged = true
    endif
endwhile

アルゴリズムの複雑さを軽減するために適用できる最適化がいくつかあります。たとえば、空間インデックス（四分木など）を使用すると、低速のグローバル計算ではなく、「近くの」頂点間のおおよその反発力を効率的に計算できます。マルチレベルのグラフ凝集手法を使用して、収束と最適性を向上させることもできます。

最後に、このアルゴリズムの最適化されたバージョンを実装するグラフ描画用の優れたライブラリがいくつかあることに注意してください。たとえば、 Graphvizをチェックすることをお勧めします。

于 2013-01-15T00:50:06.920 に答える
1

手始めに、私はヒューリスティック検索アプローチを採用すると思います。

実際には、関数を最小化する点 p1,p2,...,p_n のセットを見つけたいとします。

f(X) = Sum (|dist(p_i,p_j) - weight(n_i,n_j)|) [for each i,j ]

この問題は、 Hill ClimbingやGenetic Algorithmsなどのアルゴリズムによってヒューリスティックに解決できます。

私は個人的にヒルクライムが好きで、そのアプローチは次のとおりです。

best <- [(0,0),(0,0),...,(0,0)]
while there is still time:
    S <- random initialized vector of points
    flag <- true
    while (flag):
        flag <- false
        candidates <- next(S) (*)
        S <- X in candidates such that f(X) <= f(Y) for each X in candidates (**)
        if f(S) was improved:
            flag <- true
    if f(S) <= f(best):
        best <- S
return best

(*)next() は候補のリストを生成します。たとえば、関数の勾配に関する情報を利用したり（基本的には勾配降下に似たものに崩壊したり）、いくつかのランダムな「方向」をサンプリングして候補として配置したりできます（すべて多次元ベクトルで、各点は次元です） ）。
(**)ここでは、基本的に「最良の」候補を選択して S に保存するので、次の反復でそれを続行します。

アルゴリズムはいつでも使用できることに注意してください。そのため、時間をかければかけるほど良くなると予想されます。この動作は、最終結果を変更する可能性がある開始点のランダムな初期化と、候補の点のランダムな選択によって実現されます。

于 2013-01-14T22:46:23.043 に答える