휴리스틱(Heuristics)에 대하여

Heuristics

---

간단하게는 A노드에서 B노드까지 가는 예상 거리를 휴리스틱이라 할 수 있다.

이 휴리스틱은 실제값보다 작거나 같아야(h<=real) 제대로 된 기능을 하게되는데 그 이유는 추후에 나올 것이다.

실제거리값보다 적은 휴리스틱(예상거리)를 측정하기 위해 맨하탄 거리(Manhattan distance) 혹은 유클리디안 거리(Euclidean distance)를 쓴다. 물론 상황에 따라 다른 것을 쓰기도 한다.

Manhattan, Euclidean distance

---

맨하탄거리는 미국 맨하탄의 도로를 생각하면 된다. 맨하탄은 로버트 모지스가 기능과 기술을 찬미하는 르코르뷔지에게서 영향을 받아 철저한 도시계획에 의거하여 세워진 도시이기에 위 이미지와 같이 도시의 구역과 도로가 형성되었다. 맨하탄내에서 건물을 뚫지 않고 도로를 이용하여 A 지점에서 B 지점으로 가는 방법은 Red Blue Yellow Line 3가지이며 3가지 모두 길이가 같다. 

유클리디안 거리는 Green Line이다. 건물을 무시하고 A 지점에서 B 지점까지의 직선 거리를 잰다.

아래는 1807년에 작성된 맨해튼의 1811년 위원회 계획의 최종판. 1811년에 채택(출처-위키백과)