3

nポイント セットのコレクションがあり、各ポイント セットには最大mポイントが含まれます。

ポイントの選択結果ができるだけ近くなるように、各ポイント セットから 1 つのポイントを選択したいと考えています。(ここで、「近さ」には、選択した一連の点の重心からの距離の 2 乗の合計のように、合理的な定義があります。)

たとえば、入力コレクションは次のようになります。

Point Set A: [(2, 1), (1, 2), (6, 5)]
Point Set B: [(1, 1), (7, 3)]
Point Set C: [(3, 7), (5, 3)]

ここに画像の説明を入力

各ポイント セットから 1 つずつ、ポイントが最も近い 3 つのポイントを選択します。この例では、左下の 3 つの点が最も近くなっていますが、C からの点は含まれていません。ここでの解は、右側の点 (6, 5)、(7, 3)、および（5、3）。これらは、重心 (6, 3⅔) の周りに集まっています。

ブルート フォース アルゴリズムは、コレクションからのポイントのすべての可能な組み合わせを試行し、「近さ」関数 (つまり、 O(m^n)アルゴリズム)の最小値を追跡しますが、より効率的な方法があるかどうか疑問に思っています。nとmの大きな値に対応する方法- 最悪の場合ではないにしても、少なくともほとんどの入力に対して。

更新: ポイントは座標として実際の値を持ちます。上記では、例を簡略化するために整数が使用されています。

4

3 に答える 3

3

まず第一に、ブルート フォース アルゴリズムの改善を検討できます。

O(m^n)はすごい数です！この検索をどのように強化できますか? 最小値を保証するセットのグローバル カバレッジを検索しているわけではありません。さらに、各セットのポイントがソリューションに含まれている必要があります。新しいブルート フォース アルゴリズムは次のようになります。

S0の各点pについて、S1のpに最も近い点を見つける... S(n-1)

このアルゴリズムの計算量はO(m n m)です

アルゴリズムをさらに改善できますか? はい。

近隣探索を高速化するためにKd-Treeを採用できます。基本的に、O(m log(m)) でn Kd-Treeを構築し、それらを使用して平均的なケースで複雑さをO(m n*log(m))に減らす必要があります。

このアルゴリズムは常に最小値を見つけますか? いいえ

この例の広告を見てください:

極小値

前のアルゴリズムで取得されたクラスター間距離が最適ではないことがわかるように、これは単なる最近傍ヒューリスティックです。良いニュースは、解決に近づいているということです。ランダム再起動の山登りアルゴリズムを採用して、グローバル最小値を見つけることができます

于 2013-06-18T19:59:16.780 に答える
1

これは、組み合わせ最適化問題と見なすことができます。これを解決する 1 つの方法は、ツリーを構築し、現在の最適なポイント セットを保持することによって、ツリーの各ブランチ (これをBranch and Boundと呼びます) の DFS 検査を行うことです。これがあなたの例の図です：

木

一番左の分岐を下ると、最初の結果が見つかります。その後、ブランチを下るたびに、ある時点で計算している距離が実際の結果よりも優れている場合は、ブランチの探索を停止できます。下に行ってもより良い結果は得られません。

点数が少ない場合は関係ないかもしれませんが、10点×10セットあれば良い方法です。プロセスを高速化する簡単な方法は、最小のセットをツリーの一番上に置くことです (ノードとブランチを減らします)。

明らかに、最悪の場合、一番右のブランチが最適です。しかし、連続する各分岐が前の分岐よりも優れている可能性は非常に低いため、まだ時間を稼ぐ必要があります。

注 : 計算したときに 2 点間の距離を保存することを忘れないでください。後で計算をやり直す必要はありません。

于 2013-06-19T20:52:48.293 に答える
1

点の Delaunay 三角形分割を使用できます。その三角形分割のグラフは、近接情報をエンコードします。各頂点は、ドロネー三角形分割のエッジによって最も近い隣接点に接続されます。その Delaunay 三角形分割と和集合を使用して、ポイント セットを作成できます。

于 2013-06-19T08:54:14.273 に答える