疎結合グラフがあります。このグラフのすべてのエッジについて、位置p(v)およびp(w)でのノードvとwの間のおおよその距離d(v,w)を、ユークリッド距離としてだけでなく、 R3 のベクトルとして知っています。エラーは小さく (< 3% としましょう)、最初のノードは <0,0,0> です。
エラーがまったくなかった場合、次の方法でノードの位置を計算できます。
set p(first_node) = <0,0,0>
calculate_position(first_node)
calculate_position(v):
for (v,w) in Edges:
if p(w) is not set:
set p(w) = p(v) + d(v,w)
calculate_position(w)
for (u,v) in Edges:
if p(u) is not set:
set p(u) = p(v) - d(u,v)
calculate_position(u)
距離の誤差は等しくありません。しかし、単純にするために、相対誤差(d(v,w)-d'(v,w))/E(v,w)が N(0,1) 正規分布であると仮定します。二乗誤差の合計を最小化したい
sum( ((p(v)-p(w)) - d(v,w) )^2/E(v,w)^2 ) for all edges
グラフには適度な数のノード (> 100) が含まれる場合がありますが、ノード間の接続はわずかであり、「事前にフィルター処理」されています (これらのサブグラフ間に接続が 1 つしかない場合は、サブグラフに分割されます)。
私はフックが低い単純な「物理モデル」を試しましたが、遅くて不安定です。この種の問題に対するより良いアルゴリズムまたはヒューリスティックはありますか?