맨하튼/택시 거리(Manhattan/Taxi Distance)란?

안녕하세요. 오늘은 A* 알고리즘에서 사용되는 기본적인 휴리스틱 알고리즘 중 하나인 맨하튼 거리 혹은 택시 거리에 대해서 공부하려고 합니다.

맨하튼 거리

맨하튼 거리는 두 점 간의 거리를 연결 상태(엣지)를 고려하여 측정하는 것입니다.

예를 들어볼까요?
2차원 좌표 평면계에서 (0, 0)부터 (1, 1)까지의 맨하튼 거리는 2입니다.
 
(0, 0)에서 (1, 1)로 갈 수 있는 최단 경로는 다음과 같기 때문입니다.

• (0, 0)  -> (1, 0)  -> (1, 1)
• (0, 0)  -> (0, 1)  -> (1, 1)

 

연결 상태?

여기서 맨하튼 거리를 (|x1-x2|, |y1-y2|)라고 하지 않고,
굳이 엣지라는 용어가 들어간 이유를 설명드리겠습니다.
 
위에서 예시로 들었던 2차원 좌표 평면계는 사실 모든 노드가 weight 1의 엣지로 4개의 노드와 연결된 그래프라고 생각할 수 있습니다.

위에서 말한 2차원 좌표 평면계는 사실 그래프였다...!

 
이렇게 생각하면 맨하튼 거리를 설명할 때 체스판을 예시로 드는 것도 이해하기 쉬워집니다.
 
룩의 맨하튼 거리는 같은 수직선, 수평선 상에 위치하고 있는 노드끼리는 모두 길이 1의 엣지로 이어진 그래프에서의 최단 경로와 동일합니다.
그려보면 다음 그래프와 같은 형태를 띄게 됩니다.

룩의 그래프, 8x8을 전부 그리는 것은 너무 힘들어서 이 정도만 그렸습니다 ㅜ

 
비숍의 맨하튼 거리는 같은 대각선 상에 위치하고 있는 노드끼리는 모두 길이 1의 엣지로 이어진 그래프에서의 최단 경로와 동일합니다.
 
 
 
다음에도 Pathfinding 알고리즘을 공부하면서 흥미로운 휴리스틱 함수가 있다면 정리하도록 하겠습니다.