11

実装を開始する直前に、自分の理論があることを確認したいだけです。

定数：

  • m=頂点の質量（すべて同じ-おそらくこれをノードの半径に設定します）
  • k=一定のエッジ力。
  • l=「エネルギー最小状態」でのエッジの長さ。

変数：

  • d=2つの頂点間の距離。
  • cl=エッジの現在の長さ。

理論： すべての頂点には、他のすべての頂点に反発力がありますm / (d^2)。すべてのエッジについて、両方の頂点がエッジを「エネルギー最小状態」にする方向に「ドラッグ」する力を示します。したがって、各頂点：-k * ((l - cl) / 2)。

擬似コード：

until energy minimal state
   for each vertex v1
      for each vertex v2
         if v1 != v2
            v1.velocity += m / square_distance (v1, v2)
         endif
      end
   end
   for each edge e
      e.v1.velocity += -k * (delta_min_energy_len (e) / 2)
      e.v2.velocity += -k * (delta_min_energy_len (e) / 2)
   end
   for each vertex v
      v.position += (v.velocty * dampening_constant)
   end                
end

コメント：それで、これはうまくいくでしょうか？何に設定すればよいmですkか？

4

2 に答える 2

5

あなたは正しい方向に進んでいます。あなたの用語/物理学は少しずれています：あなたが質量と呼んでいるものと「k」は、「電荷」（逆二乗の法則の反発の場合）および「ばね定数」と呼ばれるものと混同されていますフックの法則の魅力。

あなたの質問へのコメントの返信で述べたように、実際にシステムからエネルギーを取り出すダンピングが必要です。そうしないと、位置エネルギーを運動エネルギーに変換して永久に戻すだけです。さらに悪いことに、シミュレーションの精度の問題は、エネルギーが無期限に増加し、注意しないとシミュレーションが「狂ってしまう」ことにつながる可能性があります。

このウィキペディアの記事には、あなたのものと非常によく似たいくつかの素晴らしい擬似コードがありますが、上記の点に対処しています（ただし、その擬似コードでさえ、加速度の計算で質量による除算が欠落していることに注意してください。ページの説明を参照してください）。

また、シミュレーションを開始する初期分布について少し考える必要があります。また、（おそらく）はるかに優れたグローバル最小値が存在する場合に、ローカル最小値でスタックする可能性についてどの程度気にする必要があります。これらの点は関連しています。多くはグラフのトポロジーに依存します。単純なツリーの場合、適切なレイアウトを取得するのにほとんど問題はありません。ループと構造がたくさんある場合は...頑張ってください。

于 2011-05-13T19:59:19.180 に答える
1

各頂点に同じmを選択することはありません。代わりに、接続されている他の頂点の数に比例させます。そうすれば、高度に接続されたものよりも速く離れて自分の位置に飛んでいくグラフの端。

kがわからない。

于 2011-05-13T19:01:25.743 に答える