問題タブ [closest-points]

shop_id、緯度、経度を含むリストがあります。ポイントが均等にあると仮定すると、各ショップを別のショップと一致させて、接続が一意になり、全体の距離が最小になるようにしたいと考えています。

私のアプローチがあまりにもばかげていないかどうか、そしてより良いアプローチが何であるかに興味がありました. これは現在、1000 ポイントに対して妥当な時間 (1 時間) で機能します。

次のようなリストがあるとします。

そして、PuLP を使用して、このワークフローを使用して .lp ファイルを作成します。

いくつかのジェネレーター関数を呼び出す場所 (RAM を支援するため...)

これを 100 店舗で実行すると、非常に高速で、デフォルトの PuLP ソルバーを使用できます。それ以外の場合は、LP ファイルを NEOS サーバーの CPLEX に送信します。結果の一致を視覚化する小さなヘルパー関数を作成しました。

以下は、私の LP ファイルが 10 店舗の簡単な例 (省略) を検索する方法です。

結果：

最後に、1000 ポイントのより大きな例を次に示します。

分割統治アルゴリズムが 2 より大きい次元でどのように機能するか、特に 2 つのサブ問題間で最も近い点のペアを見つける方法について頭を悩ませています。

軸d上の 2 つの間の分割の距離内にある点のみを考慮する必要があることはわかっています。x

3 次元の場合、各点を他の 15 点のみと比較する必要があることはわかっています。

私が理解できないのは、それらの 15 点を選択する方法です。2 番目のケースでは、単純に値をy値でソートし、順番に調べます。y ただし、3D の場合、各ポイントは、軸と 軸の両方で最も近い 15 個のポイントと比較する必要がありますz。最悪の場合を除いて、これらの 15 ポイントが何であるかを判断する方法を見つけることができないようですO(n^2)...

ここで何が欠けていますか？

次のコードは、最も近いペアを見つけることをシミュレートしますが、250 を超えるランダムな量のペアを生成すると、スタック オーバーフロー エラーがスローされます。しかし、250 ペア以下の偶数でも問題なく動作するようです。何か案は？

エラーは、if ステートメントの下の ComparePoints の再帰呼び出しで発生します。

そのため、このコードをデバッグしようとして問題が発生しています。[4,5,7,3,5,2,3] などの数値のリストがあり、最も近い 2 つの点を見つける必要があります。この場合、3 と 3 の差はゼロであるためです。 . ただし、正しい出力が返されません。リスト内で番号が繰り返されていない場合は機能しますが、番号が複数回表示されている場合は機能しません。

最初から時計回りに進み、閉じた形状を形成する2Dデカルト ポイントのセットがあります。[b]これらのそれぞれには、独自のコンパニオン 2D デカルト ポイントがq0ありq1、ポイントの周りのベジエ曲線を定義します (前後のポイントと共に)。これらすべての点が一緒になって、閉じた 2D合成ベジエ曲線を定義します。

p同じ平面上の任意の 2D デカルト ポイントである別のポイントがあります。へのパス上の最も近い点である新しい 2D デカルト点の座標を見つけるための簡単なアルゴリズムはありますか?(x, y)qp

ここに示されているように、ポイントb[0]とb[3]そのハンドルb[n].q0およびb[n].q1があり、任意のポイント がありpます。q曲線に沿った浮動小数点位置としてではなく、(x, y)座標のペアとしてpoint を計算しようとしています。

これを検索してみましたが、非常に小さな曲線だけのように見えるものもあれば、抽象的な数学や科学研究論文で私の頭をはるかに超えているものもありました。

特に、上記のSOの回答の純粋な数学ではなく、Cのような言語に翻訳できる場合は特に、アルゴリズムの解決策に私を導く助けがあれば大歓迎です。