Page List

Search on the blog

2010年12月4日土曜日

いろいろな距離概念

日常生活で距離というと、「ユークリッド距離」のことを指す。

他にもいろいろと距離があるので、代表的な3つの距離をまとめてみる。

  1. ユークリッド距離
  2. マンハッタン距離
  3. チェビシェフ距離

まずは、「ユークリッド距離」について。
n次元空間中の2点x, yのユークリッド距離は次のように表される。





これは、ベクトル空間でいう距離や3次元空間における一般的な距離と同じである。

次に、マンハッタン距離。
同じく2点x,yの距離を式で表すとこんなかんじ。



これは、マンハッタンのようなブロックで区画されたまちにおいて、北に○ブロック、西に×ブロック移動した言われた場合に、移動しなければいけないブロックの数を表す。

最後に、チェビシェフ距離。
同じく式で。




これは、あんまり日常生活では使われない。
斜めに移動するという概念を縦横に移動するのと同じと考えた距離概念である。
たとえば、チェスでルークは斜め方向に4移動する場合、縦横二回にわけてそれぞれ4マス移動しなければならない。(マンハッタン距離=4+4=8)
これに対して、クイーンなら一気に斜めに移動できる。(チェビシェフ距離=4)

最後に、それぞれの距離概念において、原点から等距離にある点を結んだ場合にできる線を下図に示す。





赤:チェビシェフ距離
青:ユークリッド距離
緑:マンハッタン距離
である。

0 件のコメント:

コメントを投稿