2018年7月22日日曜日

ユークリッド距離とマンハッタン距離の不思議

 
 はいどうも。ブログの保存が上手くいっておらず、せっせと書いた記事を丸ごと失ったB4の小林です。
 ミニ四駆非接触給電レースの話でもしようかなあと思っていましたが、それについてはリーダーである霜村君が鼻息荒く語りたがっているのでそちらに任せようと思います。
 というわけで困ったので、少しばかり不思議な話でも。
 
 皆さんは、ユークリッド距離マンハッタン距離を知っていますか? 因みに僕は今ググりました(正確には消えた記事を書いたときにググりました)。すると、こんな画像が出てくるかと思います。
https://mathtrain.jp/manhattanより引用

 まあ見れば分かると思うんですが、少しばかり補足をすると。
 ユークリッド距離とは、平地を最短で進んだ時の距離。
 マンハッタン距離とは、碁盤の目のようになっている街(例えば平城京とかね)を最短で進んだ場合の距離。

 ついでに言うと、これも見れば分かると思うんですが、ユークリッド距離よりマンハッタン距離の方が長くなるという特徴がありますよね。
 正方形で対角点まで移動する場合を考えると、マンハッタン距離はユークリッド距離の√2倍となります。
 ここからは、簡単のために正方形を移動する場合で考えるとしましょう。

 さてさて、僕は産声をあげた時から疑問に思っていることがあります。
「碁盤の目が超細かかったらマンハッタン距離はほぼ一本の直線になるし、それってユークリッド距離と同じじゃね?」
てなことです。僕は22年ほど生きてきて、これを疑問に思わなかった日はないです。ええ、面倒くさいガキだなと僕も思いますとも。

 分かりやすくするために図にしてみましょう。
ユークリッド距離

マンハッタン距離

 CADソフト使って三秒で書いたので見にくくて申し訳ないです。
 上の図がユークリッド距離。下の図がマンハッタン距離です。下の図は僅かにギザギザしているのが見て取れるかと思います。
 しかしながら、です。下もほぼ直線に見えますよね。なんならこの程度の差は「誤差」と感じてしまうほどです。少なくともフリーハンドではこんな直線引けません。
 これを見て、やっぱりマンハッタン距離はユークリッド距離の√2倍! なんてのたまう輩はいないはずです。そんなこと言うのは名探偵コナンぐらいのものです。それこそコナン=工藤新一ぐらい信じられません。

 しかし、真実はいつも一つ。
 冷静に考えると、マンハッタン距離はユークリッド距離の√2倍であることが分かってしまいます。コナン君すげえ。
 下の画像を見てみましょう。
マンハッタン距離2

 驚くべきことに、この画像と一枚前の画像は同一の長さである、というのがマンハッタン距離に於ける定義なんですね。やはり、マンハッタン距離はユークリッド距離の√2倍であるようです。つまり、江戸川コナン=工藤新一ってことです。嘘だぁ。

 冗談抜きにしても、実世界で言えばとても奇妙ですよね。だって普通は斜めに進んだ方が短いじゃないですか。多少ギザギザでも斜めが短いに決まってる。ましてや無限回曲がってるってそれもう直線だし、長さ同じだし……ってそう思うのは不思議ではないはずですよね。
 
 さて、なんでこんな話をしようと思ったかというと、「誤差」って何を以て「誤差」と言えるのかなと思ったためです。
 今回の例でもそうですが、パッと見では誤差に見えるものであっても、見方を変えると非常に大きな差に見えるかもしれません。まあ、今回のは単純な定義の違いでしょと言われればそれまでですが。
 
 小難しい話になった上に研究室となんも関係ないですが、しっかりとした記事は今週末にでもリーダーの霜村君が書くでしょう。
 それではそれでは。

5 件のコメント:

  1. 突然のご連絡失礼します。本サイトでユークリッド距離 マンハッタン距離について記載されていたのですが、1次元を考えた場合、両者に違いはあるのでしょうか?

    返信削除
    返信
    1. コメントありがとうございます。
      自分は別に距離函数に明るいわけではないので浅学ながらですが,お答えさせていただきます。
      1次元における距離函数は,ユークリッド距離と全て同値になります(定義にn=1を代入して計算すれば同値となると思います)。つまり,1次元における距離はユークリッド距離しか存在しない,とも言い換えることが出来るのではないかと思います。
      質問の返答をするのであれば,この2つの距離は1次元において違いはありません,ということになります。

      削除
    2. お答えいただき誠にありがとうございます。私もそう思うのですが。私は会社員でエンジニアをしておりますが、海外のメーカーが作った2点間の距離を計算するソフトウェアでは同じ1次元しか見ていないはずなのに、マンハッタン距離とユーグリッド距離に若干差があり、何か特別な計算式があるのでは?と思った次第です。社会に出ると数学的質問をできる人が減ってしまい、このサイトを見つけ急なご連絡を差し上げました。特に、怪しいものではございませんので、またご相談させていただければと思います。

      削除
  2. 失礼します、おそらくこの謎はもう解明されているかもしれませんがこの記事を見る人に対してもすっきりしていただけるようヒントを差し上げます。
    投稿者さんの疑問で碁盤の目がどこまでも小さくなった場合という考え方はつまるところ積分計算の基礎と同じです。もしかしたら高校数学でも習っているかもしれませんね。曲線の距離を求める式では、ΔxとΔyを媒介変数tを用いて計算する手法もあります。ここでいうΔx,yは投稿者のおっしゃるとっても細かい碁盤の目に該当します。
    参考になるサイトも上げておきますね
    http://www.geisya.or.jp/~mwm48961/electro/integral_length1_m.htm
    このような観点で距離を考えたことがなかったので私も改めて勉強になりました。

    返信削除
    返信
    1. コメントありがとうございます。
      昔にお遊び半分で書いたブログが今でも多くの方に見て頂けているようで,嬉しさ半分,恥ずかしさ半分といった感じです。
      とても参考になるコメントでこちらこそ勉強になります。言われてみれば微小のx,yとはまさにといった感じですね。
      存外身近に数学的な考え方というのは潜んでいるものだなあと,今更ながら自分も学ばされました。ありがとうございます。

      削除