탐욕 탐색 Greedy Search

Greedy Search

---

휴리스틱h(x) 가 가장 작은 노드부터 확장해 나가는 것이다.

이 휴리스틱 값은 우리가 입력 혹은 설정해주어야 하는 값이다.

Arad -> Bucharest 상황을 가정해보자.

우측 Red Box는 각 노드에서 Bucharest까지의 휴리스틱을 나열해놓은 것이다.

Arad에서 Bucharest까지의 휴리스틱은 366, Bucharest에서 Bucharest까지의 휴리스틱은 0.

다시 짚고 넘어가야 할 것은 휴리스틱은 real cost 즉, 실제 거리가 아닌 예상 거리이다.

Arad와 닿아있는 노드는 Zerind, Sibiu, Timlsoara 3가지. Rad Box를 참고하면

h(Zerind)=374

h(Sibiu)=253

h(Timlsoara)=329

이 3가지중 가장 작은 값을 가진 Sibiu를 다음 노드로 확장하게 되고 다시 Sibiu와 인접한 노드들의 h(x)를 비교하여 확장하는 방식으로 나아간다.

이렇게 도시까지 가는 Real Cost 실제거리를 고려하지 않기때문에 Optimal하다 할 수 없다.