...Return
マンハッタンは，道路が東西南北に走っていて，街が碁盤の目のようになって いる(残念ながらマンハッタンに行ったことがない人は京都市街を思い出して みよう)．こういった構造の街でA地点からB地点まで最短経路で移動すること を考えてみる．
通常の街であれば，最短経路を探す場合，よく知られた大きな通りに沿って行 くよりも，現在地と目標地の間にある，なるべく直線的な道路を探すだろう． いわゆる「近道」というやつである． これの背景にある理由は，三角形の任意の二辺の長さの和は，残りの一辺の長さよ り大きいということである． もしくは日常では，二点間の距離を，無意識のうちにユークリッド距離で考え ているからであろう(皆さんはどうだろうか?)．
ところがマンハッタンでは，これらの数学的経験則がほとんど役に立たない． すべての道路は東西もしくは南北に走っており，互いに直交しているからで ある．
例えばA地点の二次元座標を(Xa,Ya)，B地点のそれを(Xb,Yb) とすると，マン ハッタンではA地点からB地点への最短距離は|Xa-Xb| +|Ya-Yb| とな る．この距離の定義を「マンハッタン距離」と呼ぶ．
さらに，A地点とB地点の間に多数の交差点があれば，おそらく同等な長さの最 短経路も複数存在することになるだろう．経験から言うと，マンハッタンのビル の谷間を歩いている時は，おおよその方向さえ間違えていなければ，交差点で 曲がろうと直進しようと目標地点までの距離に大差はない．
さて，以下の例題を考えてみる．
以下の図のような8×8の2次元格子世界(grid world)がある． 世界は自由格子(free grid)から構成され，そこにはあなたとあなたの友人がいる．
........
.@......
........
........
........ @: you
........ *: your friend
.....*.. .: free grid
........ #: obstacle
この世界では，上下左右で隣接する格子間の距離を1と定義する．
次に各格子に座標を与える．ある格子の座標が(X,Y)であったと
すると，その上に隣接する格子の座標は(X,Y-1)，下は(X, Y+1)，左は(X-1,Y)，
右は(X+1,Y)である．座標はすべて整数値をとる．あなたは現在自分がいる格子の上下左右の隣接自由格子に移動することができ る(つまり，斜め方向には動けない)．
上記の例におけるあなたと友人のマンハッタン距離は9である．
...Return