맨해튼 거리 (수학) 편집하기

맨해튼 거리(Manhattan distance, 曼哈頓距離)는 격자 기반 공간에서 두 점 간의 최단 경로 거리를 계산하는 방법 중 하나이다.
==개요==
맨해튼 거리는 두 점 사이를 수직 및 수평 방향으로만 이동하여 도달할 때의 총 이동 거리를 의미한다. 이름은 미국 뉴욕시의 맨해튼 지구의 격자형 도로망을 연상시켜 붙여졌다. 이 거리 척도는 특히 격자 기반 환경에서 경로 탐색, 로봇 이동, 컴퓨터 비전 등의 분야에서 널리 사용된다.
==정의==
두 점 (x₁, y₁)과 (x₂, y₂) 사이의 맨해튼 거리는 다음과 같이 정의된다.
*d = |x₁ - x₂| + |y₁ - y₂|
3차원 이상의 공간에서도 확장할 수 있으며, 이 경우 모든 차원의 절댓값 차이의 합으로 계산된다.
==특징==
*이동은 오직 수직 또는 수평 방향으로만 가능하다.
*대각선 이동은 허용되지 않는다.
*유클리드 거리보다 단순한 계산을 필요로 한다.
*ℓ₁ 거리라고도 불린다.
==응용==
*A* 알고리즘에서 격자 지도상의 휴리스틱 함수로 사용된다.
*로봇 경로 계획 및 자동화 시스템
*데이터 분석 및 기계 학습에서 거리 기반 클러스터링
*비디오 게임 AI의 경로 탐색
==관련 거리 척도==
*유클리드 거리: 두 점 간의 직선 거리로, 피타고라스 정리를 이용하여 계산한다.
*체비쇼프 거리: 수직, 수평, 대각선 모두 같은 비용으로 이동할 때의 거리 측정 방법이다.
==같이 보기==
*[[A* 알고리즘]]
*[[유클리드 거리]]
*[[체비쇼프 거리]]
*[[휴리스틱 함수]]
*[[경로 탐색 알고리즘]]
==참고 문헌==
*Steven Skiena, "The Algorithm Design Manual," Springer, 2008.
==각주==
[[분류:그래프 이론]]
[[분류:수학]]