問題を解決しようとしています。多数の線分が与えられた場合、すべての線から点までの合計距離が最小になるように点を最適に配置する必要があります(つまり、最適な場所を見つけます)。点線の距離は、線上のどこからでも点までの距離である可能性があり、距離は他の線分を介して計算することもできます (たとえば、(0,0) から (0,1) および (1,0) への 2 つの線があるとします)。 (1,1) であり、私のポイントは (2,0.5) であり、最初の線から 2 番目の線までの距離を計算できます。十分に明確であることを願っています)。線はすべて端点として整数座標を持ちますが、点は平面上のどこにでも配置できます。
私はこれについて多くのことを考えましたが、一般的な戦略を思いつくことができません. 誰かが私に読み物を教えてくれるか、これのアルゴリズムを説明してもらえますか? 他の場所でこのようなものを見たことがありますが、これはある種の一般的な問題ですか?
ありがとう。
あなたの説明に基づいて、最短のライン距離は、ラインセグメントによって定義されたゾーンに基づいて個別に議論する必要があります. たとえば、線分が (0,0) から (0,1) の場合、空間を 3 つの部分空間にスライスする必要があります (d は最小距離関数を示します)。
関数 d には凸特性があるため、標準の凸最適化ソフトウェアを実行することで最適化問題を解決できます。cvx パッケージは優れたソフトウェアです。凸最適化理論の詳細については、凸最適化を参照することをお勧めします。
結果を得るために何らかの最適化ソルバーをわざわざ使用しない場合は、ヒューリスティックに基づいて代替バージョンを解決する方がはるかに簡単です。
線分が両端で無限に伸びている場合、問題は些細なことであることに注意してください。したがって、私が考えることができるのは、セグメントを線であるかのように扱い、端点にペナルティ距離を追加することです。そうは言っても、次のメトリックは必要性を満たします。
L = [(ax + by - c)^2] + [(x-x1)^2 + (x-y1)^2] + [(x-x2)^2 + (y-y2)^2]
ここで、(x, y) は決定する必要があるポイントです。ax* + by* = c は線を定義し、(x1,y1)、(x2,y2) は 2 つの終点です。したがって、最初の [...] 項は、直線までの距離の 2 乗です。第 2 項と第 3 項は、2 つの端点までの距離の 2 乗です。
L の最小化とは、次のことを意味します。
これは最小二乗距離問題に分類されるため、一次方程式を解くだけで解を得ることができます。これは、私が L で 2 次形式に固執する理由でもあります。
もちろん、これは単純な解決策につながるヒューリスティックな方法にすぎません。用語 L の他の定式化は、視覚認知の観点から、より良い結果につながる可能性があります。さまざまな L で遊ぶことを検討し、視覚的な結果に基づいて最適なものを選択することができます。
私は機能するアルゴリズムを持っています（Googleで見つけました）、それが機能するのはおかしいようです。誰かが私になぜそれが起こるのか説明してもらえますか? ありがとう..
To solve this, we start by placing the point at any random location and moving
it around in various directions, decreasing the amount that we move it by.To begin
place the point at any location. Next move it in large increments (20) about
10 times.Now we decrease the amount by which we move by an amount to 1/10;Running
the whole placement process about 5 times, decreasing the amount by
which we move the power source each time, will give us the best location
for the point.