체비쇼프 거리

체비쇼프 거리(Chebyshev distance, L∞ 거리)는 두 점의 좌표 차이 절댓값 가운데 가장 큰 값을 두 점 사이의 거리로 삼는 거리 척도이다.

개요

두 점이 각 좌표축에서 얼마나 떨어져 있는지를 구한 뒤 그중 최댓값만 취한다. 체스의 킹은 가로·세로·대각선으로 한 칸씩 같은 비용으로 움직이므로, 킹이 한 칸에서 다른 칸으로 가는 최소 이동 횟수가 곧 두 칸의 체비쇼프 거리이다. 그래서 '체스판 거리'라고도 부른다.

체비쇼프 거리는 민코프스키(Lm) 거리의 극한이다. 미국 국립표준기술연구소(NIST)의 알고리즘·자료구조 사전은 Lm 거리를 (|x1 - x2|^m + |y1 - y2|^m)^(1/m) 로 정의하고, m = 2 이면 유클리드 거리, m = 1 이면 맨해튼 거리, m 이 무한대이면 max(|x1 - x2|, |y1 - y2|) 인 L∞ 거리가 된다고 정리한다.

정의

n 차원의 두 점 u = (u1, …, un), v = (v1, …, vn) 사이의 체비쇼프 거리는 다음과 같다.

D(u, v) = max(|u1 - v1|, |u2 - v2|, …, |un - vn|)

SciPy 의 scipy.spatial.distance.chebyshev(u, v) 함수가 이 식으로 계산한다.

예를 들어 x1 = (1, 1), x2 = (5, 3) 이면

• 유클리드 거리 = √(4² + 2²) = √20 ≈ 4.47 (두 점을 잇는 대각선)
• 맨해튼 거리 = 4 + 2 = 6 (가로 4 와 세로 2 를 이은 꺾인 경로)
• 체비쇼프 거리 = max(4, 2) = 4 (차이가 더 큰 가로 방향 한 변)

그림으로 보면 대각선이 유클리드, 가로와 세로를 이은 ㄱ자 경로가 맨해튼, 두 변 가운데 긴 변 하나가 체비쇼프 거리이다. 언제나 체비쇼프 ≤ 유클리드 ≤ 맨해튼이 성립한다.

세 거리 비교

거리	노름	식(2차원)	같은 거리에 있는 점들의 모양
맨해튼 거리	L1	|dx| + |dy|	마름모
유클리드 거리	L2	√(dx² + dy²)	원
체비쇼프 거리	L∞	max(|dx|, |dy|)	축에 나란한 정사각형

쓰임

• 인공지능 강건성 평가 - 입력에 더하는 교란의 크기를 Lp 노름으로 잰다. L∞ 노름으로 ε 이내라는 말은 모든 화소(특징)를 각각 ε 이하만큼만 바꾼다는 뜻이고, 이미지 적대적 예제 연구에서 가장 많이 쓰는 제약이다. 두 입력의 거리가 일정 값 안이면 출력이 같아야 한다는 것이 강건성의 정의로 쓰인다 → 인공지능 강건성
• 경로 탐색 - 8방향 이동 비용이 같은 격자에서 A* 알고리즘의 휴리스틱으로 쓴다
• 창고·물류 - 가로축과 세로축 모터가 동시에 움직이는 크레인은 더 오래 걸리는 축의 이동 시간이 전체 시간이 된다

같이 보기

• 유클리드 거리
• 맨해튼 거리 (수학)
• 인공지능 강건성
• A* 알고리즘