ポイントのセット(座標が不明)と距離マトリックスがあります。これらの点をプロットしてアルゴリズムの解を表示するには、これらの点の座標を見つける必要があります。
これらの点の 1 つを座標 (0,0) に設定して簡略化し、他の点を見つけることができます。他の点の座標を見つけることが可能かどうか、誰か教えてもらえますか?
前もって感謝します!
EDIT xyのみの座標が必要だと言うのを忘れました
ポイントのセット(座標が不明)と距離マトリックスがあります。これらの点をプロットしてアルゴリズムの解を表示するには、これらの点の座標を見つける必要があります。
これらの点の 1 つを座標 (0,0) に設定して簡略化し、他の点を見つけることができます。他の点の座標を見つけることが可能かどうか、誰か教えてもらえますか?
前もって感謝します!
EDIT xyのみの座標が必要だと言うのを忘れました
角度に基づく答えは実装が面倒で、高次元のデータに簡単に一般化することはできません。より良いアプローチは、ここで私と WimC の回答で言及されていることです:距離行列が与えられた場合D(i, j)
、定義します
M(i, j) = 0.5*(D(1, j)^2 + D(i, 1)^2 - D(i, j)^2)
k
これは、ポイントを埋め込むことができる最小のユークリッド次元に等しいランクを持つ正の半正定行列でなければなりません。点の座標は、ゼロ以外の固有値に対応する のk
固有ベクトルから取得できます。ベクトルを行列の列として配置します。の各行はポイントです。言い換えれば、すべてのポイントの th コンポーネントを提供します。v(i)
M
q(i)
sqrt(q(i))*v(i)
n x k
X
X
sqrt(q(i))*v(i)
i
行列の固有値と固有ベクトルは、ほとんどのプログラミング言語で簡単に取得できます (たとえば、C/C++ で GSL を使用するeig
、Matlab で組み込み関数を使用する、Python で Numpy を使用するなど)。
この特定の方法では、常に最初のポイントが原点に配置されますが、ポイントの回転、反射、または移動も元の距離マトリックスを満たすことに注意してください。
ステップ 1、1 つの点 P1 を (0,0) として任意に割り当てます。
ステップ 2、正の x 軸に沿って 1 つの点 P2 を任意に割り当てます。(0, Dp1p2)
ステップ 3、次のような点 P3 を見つけます。
Dp1p2 ~= Dp1p3+Dp2p3
Dp1p3 ~= Dp1p2+Dp2p3
Dp2p3 ~= Dp1p3+Dp1p2
そのポイントを「正の」y ドメインに設定します (これらの基準のいずれかを満たす場合、ポイントは P1P2 軸上に配置する必要があります)。
余弦法則を使用して距離を決定します。
cos (A) = (Dp1p2^2 + Dp1p3^2 - Dp2p3^2)/(2*Dp1p2* Dp1p3)
P3 = (Dp1p3 * cos (A), Dp1p3 * sin(A))
これで、正常に直交する空間が作成され、その空間に 3 つの点が配置されました。
ステップ 4: 他のすべての点を決定するには、ステップ 3 を繰り返して仮の y 座標を取得します。(Xn、Yn)。
距離 {(Xn, Yn), (X3, Y3)} を行列の Dp3pn と比較します。一致する場合は、点 n の座標を特定できたことになります。それ以外の場合、点 n は (Xn, -Yn) にあります。
ステップ 4 に代わる方法がありますが、土曜日の午後には計算量が多すぎることに注意してください。
点 p、q、および r に対して行列に pq、qr、および rp がある場合、三角形があります。
行列に三角形がある場合は、その三角形の 2 つの解のうちの 1 つを計算できます (平面上の三角形のユークリッド変換とは無関係)。つまり、計算する三角形ごとに、その鏡像は、p、q、および r の距離制約を満たす三角形でもあります。三角形にも 2 つの解があるという事実は、キラリティの問題につながります。各三角形のキラリティー (方向) を選択する必要があり、すべての選択が問題の実行可能な解につながるとは限りません。
それにもかかわらず、いくつかの提案があります。エントリ数が少ない場合は、シミュレーテッド アニーリングの使用を検討してください。アニーリングステップにキラリティを組み込むことができます。これは大規模なシステムでは遅くなり、完全な解に収束しない可能性がありますが、問題によってはこれが最善の方法です。
2 番目の提案は完全な解決策ではありませんが、エラーを分散させます:最小二乗法. あなたの場合、目的関数は、マトリックス内の距離とポイント間の実際の距離の間の誤差になります。