개념
Manhattan Distance는 격자에서 두 위치 사이를 가로와 세로 방향 이동만으로 계산한 거리이다.
8-puzzle에서의 사용
8-Puzzle에서는 각 숫자 타일이 현재 위치에서 목표 위치까지 얼마나 이동해야 하는지 계산할 수 있다. 모든 타일의 맨해튼 거리를 더하면 현재 상태가 목표에 얼마나 가까운지 나타내는 휴리스틱이 된다.
A star와의 관계
A star 알고리즘은 을 사용한다. 여기서 에 맨해튼 거리를 넣으면 목표까지 남은 비용의 추정치로 사용할 수 있다.