맨해튼 거리 (수학)

맨해튼 거리(Manhattan distance, 曼哈頓距離)는 격자 기반 공간에서 두 점 간의 최단 경로 거리를 계산하는 방법 중 하나이다.

1 개요

맨해튼 거리는 두 점 사이를 수직 및 수평 방향으로만 이동하여 도달할 때의 총 이동 거리를 의미한다. 이름은 미국 뉴욕시의 맨해튼 지구의 격자형 도로망을 연상시켜 붙여졌다. 이 거리 척도는 특히 격자 기반 환경에서 경로 탐색, 로봇 이동, 컴퓨터 비전 등의 분야에서 널리 사용된다.

2 정의

두 점 (x₁, y₁)과 (x₂, y₂) 사이의 맨해튼 거리는 다음과 같이 정의된다.

• d = |x₁ - x₂| + |y₁ - y₂|

3차원 이상의 공간에서도 확장할 수 있으며, 이 경우 모든 차원의 절댓값 차이의 합으로 계산된다.

3 특징

• 이동은 오직 수직 또는 수평 방향으로만 가능하다.
• 대각선 이동은 허용되지 않는다.
• 유클리드 거리보다 단순한 계산을 필요로 한다.
• ℓ₁ 거리라고도 불린다.

4 응용

• A* 알고리즘에서 격자 지도상의 휴리스틱 함수로 사용된다.
• 로봇 경로 계획 및 자동화 시스템
• 데이터 분석 및 기계 학습에서 거리 기반 클러스터링
• 비디오 게임 AI의 경로 탐색

5 관련 거리 척도

• 유클리드 거리: 두 점 간의 직선 거리로, 피타고라스 정리를 이용하여 계산한다.
• 체비쇼프 거리: 수직, 수평, 대각선 모두 같은 비용으로 이동할 때의 거리 측정 방법이다.

6 같이 보기

• A* 알고리즘
• 유클리드 거리
• 체비쇼프 거리
• 휴리스틱 함수
• 경로 탐색 알고리즘

7 참고 문헌

• Steven Skiena, "The Algorithm Design Manual," Springer, 2008.