맨해튼 거리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
맨해튼 거리와 유클리드 거리의 비교: 빨간색, 파란색, 노란색 선은 길이가 12로 같으며, 유클리드 거리와 맨해튼 거리 양쪽 모두 가지고 있다. 유클리드 기하학의 경우 초록색 선의 길이는 6×√2 ≈ 8.48로, 선들 가운데 유일하게 길이가 가장 짧으며, 맨해튼 거리의 경우 초록색 선의 길이는 12로, 이보다 길이가 더 짧은 선은 없다.

맨해튼 거리(Manhattan distance, 혹은 택시 거리, L1 거리, 시가지 거리)는 19세기의 수학자 헤르만 민코프스키가 고안한 용어로, 보통 유클리드 기하학거리 공간을 좌표에 표시된 두 점 사이의 거리(절댓값)의 차이에 따른 새로운 거리 공간으로 대신하기도 한다.

정의[편집]

맨해튼 거리는 d_1과 벡터 \mathbf{p}, \mathbf{q} 사이에 차원 실수직교 좌표계에 일정한 좌표축의 점 위에 투영한 선분 길이의 합을 말하는데, 이를 공식으로 표현하면 다음과 같다.

d_1(\mathbf{p}, \mathbf{q}) = \|\mathbf{p} - \mathbf{q}\|_1 = \sum_{i=1}^n |p_i-q_i|이면

\mathbf{p}=(p_1,p_2,\dots,p_n)\,\mathbf{q}=(q_1,q_2,\dots,q_n)\,공간 벡터가 된다.

예를 들어 평면 위의 맨해튼 거리가 (p_1,p_2)(q_1,q_2) 사이이면 | p_1 - q_1 | + | p_2 - q_2 |이다. 맨해튼 거리는 좌표계의 회전에 의존하지만, 좌표의 축을 반사하거나 평행이동을 하는 경우는 그렇지 않다. 맨해튼 거리는 SAS 합동 (두 개의 변과 그 사이의 각이 같은 두 개의 삼각형을 만들 수 있으나, 합동이 아니다.)인 경우를 제외하면 모든 힐베르트 공리계 (유클리드 기하학의 의식화)와 일치한다.

맨해튼 거리의 원은 중심 점에서 반지름 이라고 불리는 일정한 거리만큼 떨어져 있는 점들의 집합이다. 유클리드 기하학과 맨해튼 거리의 원은 모양이 다르다. 맨해튼 거리에서 원은 좌표의 축으로 45° 기울어진 정사각형이다. 모눈의 크기가 줄어들면 수많은 점들은 연속적인 정사각형의 모양을 만드는데, 유클리드 거리를 이용한 각 변이 길이가 √2r이면 이 원의 반지름은 r이다. 각 변의 길이를 맨해튼 거리로 측정한 값은 2r이 된다.

원의 반지름이자 체비셰프 거리 (Lp 거리)인 r은 정사각형 평면에 평행하며, 정사각형의 변의 길이인 2r은 좌표의 축에 평행하다. 평면의 체비셰프 거리는 거리의 회전과 축소된 평면의 맨해튼 거리와 같은 값이지만, L1과 L의 거리 사이의 같은 값은 보다 높은 차원에서 일반화되지 않고 있다.

체스에서의 측정[편집]

체스에서는 의 경우 체스판과 정사각형 사이의 거리를 맨해튼 거리로 측정하고, 체비셰프 거리를 이용하며, 비숍은 체스판을 45도로 순환하는 맨해튼 거리 (같은 색의 정사각형)를 이용한다. 즉, 비숍의 경우 거리를 측정하는 축은 체스판의 대각선 방향이다. 따라서 오직 킹만이 한번 움직일때 거리와 같은 수의 이동을 하고, 룩과 퀸, 비숍의 경우 일정한 거리를 이동하기 위해서는 1번 혹은 2번 움직여야 한다. (단, 비어 있는 체스판을 가정하고, 비숍의 경우 이동할 수 있는 모든 경우가 가능하다고 가정한다.)

각주[편집]

바깥 고리[편집]