マンハッタン距離が最大である2点を選ぶ問題
問題
空間に個の点がある.点から2つの点を選び,2点間のマンハッタン距離を最大化したい.
ただし,マンハッタン距離とは,2点に対して
で与えられる距離のことである.
単純に全通り試すとだけの計算量がかかるが,が大きいと計算コストがかなり大きくなる.
そこで,に比例する計算量のアルゴリズムが知りたい.どうすればよいか.
制約条件
はに比べてとても小さい.(具体的にはくらい.)
解法
Step 1
まず,という距離を導入しておく.
これは,
…(1)
で定義される.
Step 2
マンハッタン距離は,定義より次のようにも表すことが出来る.
[tex:||x||_{1} = \max\{
ここで,[tex:
ここで,とし,また写像を
[tex:f(x) = \{
とおく.*1
すると,(1)式を用いると,(2)はさらに
…(4)
と記すことができる.
Step 3
問題は,が最大となるような点の組をに比例する計算量で探すことであった.
(3)の定義よりfには線型性が成り立つ()から,(4)より
…(5)
となる.
(5)より,問題は空間上にて点の距離を最大化する問題に帰結できる.
を求めるにはの計算量がかかる.
Step 4
距離を最大化するのは簡単である.実際,とすると
…(6)
となる.は番目の座標軸の中で最大のものから最小のものを引いたものに等しく,これはで求められる.
そこで,(6)式はで求めることが出来る.
計算量
上のStep 3, Step 4より,全体ではの計算量がかかる.
が少しでも大きくなるとこのアルゴリズムは使えなくなることに注意.
参考文献
15-859(J) Metric Embeddings, Fall 2003 Lecture Notes, Sep 2
*1:yの元はk'個あるのでこれらを単純に並べることでk'次ベクトルを作れる.