分布を分けるには

Question

平面上のある領域内に人が分布しているとする。
その領域のどこかに旗を立て、なるべく皆がその旗をできるだけ近い距離で見られるようにしたい。
旗を１本だけ立てるならば、ある点からすべての 人へのベクトルを求め、
すべてのベクトルの平均の場所に旗を立てればいいと思いますが、
旗をｎ本立てたいときはどう計算すればいいでしょうか。 
人は自分に一番近い旗だけを見るものとします。

stomachman · Accepted Answer

ANo.1へのコメントについてです。
　色々書きすぎて、却って混乱させてしまったかもしれないな、と反省中。

[1] まず旗が1本だけのときについて。ご質問に、各人の位置の重心に旗を置けばいい、とお書きですが、これは最小化すべき目的関数Eが「旗と各人との距離の２乗の総和」である場合の解です。この場合、旗の位置を(p,q)として、
　　∂E/∂p = 0
　　∂E/∂q = 0
という連立方程式を解けば良いのですが、人iの位置を(x[i], y[i])とするとき
　　E = ∑ ((x[i] - p)^2 + (y[i] - q)^2)
なので、
　　∂E/∂p = 2∑ (x[i] - p)
　　∂E/∂q = 2∑ (x[i] - q)
ですから、
　　p = (∑x[i])/(∑1), q = (∑y[i])/(∑1)
つまり、おっしゃる通り、各人の位置の重心に旗を置けばいいわけです。

[2] しかし、Eを「旗と各人との距離の総和」
　　E = ∑ ((x[i] - p)^2 + (y[i] - q)^2)^(1/2)
とすると途端に難しくなります。
　　∂E/∂p = -∑ (((x[i] - p)^2 + (y[i] - q)^2)^(-1/2))(x[i] - p)
　　∂E/∂q = -∑ (((x[i] - p)^2 + (y[i] - q)^2)^(-1/2))(y[i] - q)
であり、p,qについてキレイに解くことはできません。じゃあどうするか。たとえば(p,q)を仮に(p0,q0)と決めておいて
　　∑ (((x[i] - p0)^2 + (y[i] - q0)^2)^(-1/2))(x[i] - p) = 0
　　∑ (((x[i] - p0)^2 + (y[i] - q0)^2)^(-1/2))(y[i] - q) = 0
（これはそれぞれ一次方程式）を解いてp,qを更新する、ということを繰り返す。ただしこれだとp,qの値が振動して収束しない恐れもあり、そういうときには、たとえば方程式を解いて得られた(p, q)と(p0, q0)との中点を次の(p0, q0)として繰り返す、のような安定化が必要になるでしょう。

[3] で、ご質問の問題についてですが、実際どうやるかを考えてみますと、まず全人口の最外殻に居る者を繋いだ多角形を作る。そして、
(1) この多角形の中に、何とかn本の旗を立てる。たとえば、乱数で位置(p,q)を作り、それが多角形の外に行っちゃったら捨てて、多角形の中にn個の点が決まるまで乱数を作り続ける。
(2) 全人口の各人について、最寄りの旗がどれであるかを調べ、これで全人口をn個の組に組分けする。
(3) それぞれの組j (j=1〜n) について
　最寄りの1本の旗jだけを考え、E[j]=「その旗jと組jの各人との距離の総和」を最小化する問題（これは[2]に書いたやつです）を解いて、旗jの位置を修正する。（この修正によって、組jに入っている人の最寄りの旗が旗jではない、ということが生じ得るわけです。で、）
組分けが変化しなくなるまで、操作(2)〜操作(3)を繰り返す。
(4) E = ∑E[j] (j=1〜n) を計算する。

という操作(1)〜(4)をうんと沢山繰り返して、一番成績が良いのを採用する。

もちろんこれでは、得られた解が最適解だという保証はないわけで、数学の答としては落第ですが、実用を考えるのならアリでしょう。

[4] ちなみに、「n本の旗の位置を決めた時に、旗jが最寄りになるのは平面上のどの領域か」という問題は「計算幾何学」という分野で「ボロノイ分割」と呼ばれていて、高速かつ安定なアルゴリズムが知られています。ご質問の問題と関係がありそうな気がする回答者が居るかもしれないが、実は残念ながら何の関係もない…と、また余計なことを書いてます。

stomachman · Answer

領域が円形で分布が一様、のような対称性が極めて高い場合を除くと解析的には解けそうになく、決定的に旨い手はないだろうと思います。
　n本の旗の座標を2n次元ベクトルxで表し、「ある目的関数E(x)の最小値を探したい」という極値問題として定式化出来ます。E(x)はご質問の場合には「N個の点から最寄りの旗までの距離の総和」でしょうか。（距離をどう定義するかでも、扱いやすさは変わります。ユークリッド距離、その２乗、あるいはマンハッタン距離、などなど。）
　数値計算によって、2n次元空間中でxを動かしつつE(x)をちょっとずつ改良して行って停留点を見つける、これはいわゆる「最急降下法」の類ですが、これだけでは局所最適解に収束してしまいますから、停留点からまたわざと動かして、別のより良い局所最適解を探す、いわゆる「焼き鈍し法」が必要でしょう。近頃はやりのneural networkのアルゴリズムには、もうちょっとだけ効率の良いやり方がいろいろ考案されていると思うけれども、桁違いに速くなるわけじゃないでしょう。
　xの出発値を選ぶのには「クラスター分析」の手法が使えそうな気がします。これはN個の点の2次元平面上での分布を数値計算で幾つかのクラスターに分割し、同じクラスターに属する点同士は互いに比較的近く、異なるクラスターに属する点同士は互いに比較的遠い、というふうにしようとするものです。こうして得たクラスターそれぞれの重心に旗を立てた状態を出発値xにしてみると良さそうだ、という、これはただの勘ですけどね。

エビス · Answer

旗Aと旗Bを直線で結ぶ。
直線の中点に直角に線を引く。
この線が領域Aと領域Bの境界になる。

以下旗の数だけ繰り返すと多角形の領域が得られる。

分布を分けるには

領域が円形で分布が一様、のような対称性が極めて高い場合を除くと解析的には解けそうになく、決定的に旨い手はないだろうと思います。

旗Aと旗Bを直線で結ぶ。

ANo.1へのコメントについてです。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング