山登りアルゴリズムを実装して、特定の基準に基づいて一連の場所から選択する場所を決定しようとしています。最大 5000 の場所から選択できます。
これらの基準の 1 つは地理的な分散です。したがって、場所の任意のサブセットに分散を表す値を割り当てることができる必要があります。
各場所には緯度と経度のデータがあります。
速度が問題であり、そのため、特定の場所のセット (つまり、可能な解決策) がどの程度分散しているかを推定するヒューリスティックが必要です。
潜在的な解の各位置のペアごとの距離を合計しようとしましたが、これは遅すぎることがわかりました。
次に、潜在的なソリューションのすべての場所の中心からの距離の合計を試しました。これはより高速であることが証明されましたが、効果的ではありません。このアプローチを使用すると、場所のいくつかのクラスターが優先されます。
他の提案は大歓迎です。
最初に、ペアワイズサムの意味をもう一度説明していただけますか? 考えられるすべてのペアを形成しているように聞こえますが、それは非常に非効率的です。この場合、最初に 1) 最も近い隣人を見つけ、次に 2) 最長のパスを見つけるのはどうですか?
1) 私の記憶が正しければ、これを O(n log n) 時間未満で実行できます。2) 形成されたツリーが切断されている場合は、ツリー間の最短距離も見つける必要があります。また、ツリーがあるため、これは NP 完全問題ではありませんが、実際には最短パス alg で十分です。
現時点では、私があなたの問題を正しく理解していなかったという大きな疑いがありますが、極端なポイント間で均等に分割されるか、以前のヒューリスティックで選択された、ジオグ領域での発生数のある種の偏差はどうですか.
分散の概念を定義またはさらに詳しく説明できますか?
次の 3 つの状況を考えてみましょう。
すべてのペアワイズ距離の合計は、(1) と (2) を適切にキャプチャします。クラスターが近いと、大きなクラスターよりも小さな結果が得られます。(3) はどうするか。ここでは、eノードの総数のN一部が遠く離れており、平均距離が離れていDます。他の(1-e)Nノードは、平均距離 でクラスター化されていdます。
では、いくつのペアワイズ接続を考慮する必要がありますか? クラスター化されたノードには、((1-e)N)^2=e^2*N^2-2*e*N^2+N^2このような接続があります。離れたノードの場合、e^2*N^2接続があります。
次に、これらの値に平均距離を掛けます。これにより、 の合計ペアワイズ平均が得られ(d*(e^2*N^2-2*e*N^2+N^2)+D*(e^2*N^2))/Nます。ここで、eが小さいと仮定すると、 を組み込んだ項を無視できe^2ます。したがって、平均はd*(N^2-2*e*N^2)/Nです。
次に、2 番目のメトリクスである、平均中心点からの全員の距離を考えてみましょう。これは (1) と (2) についても問題ありません。クラスターが近いほど、大きなクラスターよりも結果が小さくなります。3でどうなるの？上記と同じものを使用してe、外れ値の割合を表します。ここで、中心点からのノードの平均距離は で与えられ(d*(1-e)*N+D*e*N)/Nます。言い換えれば、クラスタ化されたノードはもはや重く重み付けされていません。
計算を軽量化しながら、クラスター化されたノードをより適切に重み付けする方法はありますか? そう思います。
私の提案は、リストからノードのランダムなペアを選択し、ノード間の距離を計算してから、結果を平均することです。(1) タイトなクラスターの場合、すべてのノードが近くにあるため、描画するすべてのランダム ペアは、計算で取得したペアごとの平均に近くなります。(2) のゆるいクラスターについても、同じことが当てはまります。(3) 外れ値のあるクラスターの場合、クラスター外からよりもクラスター内からノードを描画する可能性が高いため、外れ値は無視されてしまいます。
サンプリングするノードの数を増やすと、クラスタがランダム サンプリングを支配する傾向があります。O(N)これにより、時間ではなく適切な精度が得られると思いますO(N^2)。