2D平面上の点のリストが与えられた場合、点のリストから最も近い配置された点までのすべての距離の合計が可能な限り小さくなるように、平面上にN個の点を配置するにはどうすればよいでしょうか。環境は目立たず、リストには[（0,0）;の範囲内の一意のポイントが含まれます。（〜200：〜100）]
できれば、アルゴリズムの最悪の場合のパフォーマンスは多項式である必要があります（したがって、リアルタイムで計算される小さな範囲を使用します）。どんな概算も歓迎します。
2 に答える
3
これは、 K-Meansクラスタリングアルゴリズムが行うことと本当に似ています。あなたの場合、ポイントのリストは入力であり、ポイントの数Nはクラスターの数です。
悲しいことに、それが行うのはNP困難です。しかし、多くの研究が行われており、それを改善するための多くの方法があります（wikiページを下にスクロールするだけでいくつか見つかります）。
また、k-meansは学者によって非常に頻繁に使用されているため、より良いアルゴリズムがあるとは思えません。私は彼らがそのために実行するより良いアルゴリズムがあるかどうかを推測します:)
繰り返しになりますが、データマイニングの最高のチュートリアルであるAndrewMooreのスライドを紹介します。私はあなたの目的を知りませんが、これはあなたが必要とするものに非常に近いはずです。
于 2011-07-29T19:03:15.093 に答える
0
ノードのリストの重心を取得できます（重み= 1）。
または、距離のx^2による分散。
問題を、残りの部分までの距離が最小である重心の領域のどこにNノードを配置するかという問題を減らしました。
完璧な世界では、重心に1つのポイントを置くだけです。ただし、同じ場所に2点を配置することはできないと思いますので、重心付近を選択する必要があります。
これにより、問題が重心に近い8つのポイントから最適なものを選択し、重心を再計算して、もう一度実行するようになります。
于 2011-07-29T19:07:53.863 に答える