曼哈頓距離
計程車幾何(Taxicab geometry)或曼哈頓距離(英語:Manhattan distance/Manhattan length)或方格線距離是由十九世紀的赫爾曼·閔可夫斯基所創辭彙,為歐幾里得幾何度量空間的幾何學之用語,用以標明兩個點上在標準坐標系上的絕對軸距之總和。
曼哈頓距離
編輯我們可以定義曼哈頓距離的正式意義為L1-距離或城市區塊距離,也就是在歐幾里得空間的固定直角坐標系上兩點所形成的線段對軸產生的投影的距離總和。
例如在平面上,坐標(x1, y1)的點P1與坐標(x2, y2)的點P2的曼哈頓距離為:
要注意的是,曼哈頓距離依賴坐標系統的旋轉,而非系統在座標軸上的平移或映射。
曼哈頓距離的命名原因是從規劃為方型建築區塊的城市(如曼哈頓)間,最短的行車路徑而來(忽略曼哈頓的單向車道以及只存在於3、14大道的斜向車道)。任何往東三區塊、往北六區塊的的路徑一定最少要走九區塊,沒有其他捷徑。
在計程車幾何學中,一個圓是由從圓心向各個固定曼哈頓距離標示出來的點圍成的區域,因此這種圓其實就是旋轉了45度的正方形。如果有一群圓,且任兩圓皆相交,則整群圓必在某點相交;因此曼哈頓距離會形成一個超凸度量空間。對一個半徑為r 的圓來說,這個正方形的圓每邊長√2r。此'"圓"的半徑r對切比雪夫距離(L∞空間)的二維平面來說,也是一個對座標軸來說邊長為2r的正方形,因此二維切比雪夫距離可視為等同於旋轉且放大過的二維曼哈頓距離。然而這種介於L1與L∞的相等關係並不能延伸到更高的維度。
在棋盤上的距離計量
編輯在西洋棋裡,車(城堡)是以曼哈頓距離來計算棋盤格上的距離;而王(國王)與后(皇后)使用切比雪夫距離,象(主教)則是用轉了45度的曼哈頓距離來算(在同色的格子上),也就是說它以斜線為行走路徑。只有國王需要一步一步走的方式移動,皇后、主教與城堡可以在一或兩次移動走到任何一格(在沒有阻礙物的情況下,且主教忽略它不能走到的另一類顏色)。
參見
編輯參考資料
編輯- Eugene F. Krause. Taxicab Geometry. Dover. 1987. ISBN 978-0-486-25202-5.
外部連結
編輯- City Block Distance (頁面存檔備份,存於網際網路檔案館),by Kardi Teknomo
- city-block metric (頁面存檔備份,存於網際網路檔案館) on PlanetMath
- 埃里克·韋斯坦因. Taxicab Metric. MathWorld.
- Manhattan distance (頁面存檔備份,存於網際網路檔案館)。Paul E. Black, Dictionary of Algorithms and Data Structures (頁面存檔備份,存於網際網路檔案館),NIST