[인공지능] 경험적 탐색(Informed search)기법 비교

경험적 탐색 기법은 상태 공간에 대한 정보를 이용함으로써 탐색 효율을 높일 수 있다.

h(n)이라는 휴리스틱 함수를 사용하는데,
h(n)은 특정 상태로부터 목표 상태까지의 비용이고 실제로는 추정치를 사용한다
따라서 최적해를 보장하지는 않는다

다음 예제에 대해서도 방법을 함께 비교해볼 것이다!

1. 언덕 오르기 (Hill-Climbing)

- h(n)을 평가함수로 사용
- 현재 노드에서 h(n)이 좋은 이웃 방향으로 탐색하는 up hill 방식
- OPEN에서 현재 노드의 후계 노드만을 정렬한다 (local-optima의 원인)
- 해가 하나 뿐인 uni-modal problem에 적합
- multi-modal이나 combinatorial problem에서는 local-optima에 빠질 수 있다는 문제가 있다

2. 최상 우선 탐색 (Best-first search / Greedy)

- h(n)을 평가함수로 사용
- 지금까지 본 노드들 중 h(n)이 가장 좋은 노드를 탐색하는 방식 (Greedy)
- OPEN에서 현재 노드의 후계 노드 뿐 아니라 모든 노드를 정렬한다
- 균일 비용 탐색과 비슷하고 시작노드부터 현재노드까지의 비용 g(n)대신 h(n)을 사용한다는 점에서 차이가 있다
- 모든 노드를 저장해두고 정렬 해야하기 때문에 메모리 비용과 정렬 비용이 많이 든다

3. 빔 서치 (Beam search)

- h(n)을 평가함수로 사용
- OPEN에서 기억될 노드의 수를 사전에 제한하기 때문에 메모리 효율이나 정렬 비용이 덜 든다
- 기억될 노드를 결정할 때 h(n)이 가장 좋은 노드를 선택하고, 선택된 노드가 단말노드일 경우 차상위 노드에게 기회를 준다

4. A* 서치 (A* search)

- f(n) = g(n) + h(n) 을 평가함수로 사용
- h(n)에 더해 g(n)이라는 정보도 함께 사용하기 때문에 최소 비용을 보장한다
- 균일 비용 탐색과 비슷하고 시작노드부터 현재노드까지의 비용 g(n)대신 f(n)을 사용한다는 점에서 차이가 있다

여태 봤던 모든 노드들을 관리하는 최상우선탐색과 A*알고리즘은 보이는 바와 같이 메모리 관리 비용이 더 든다
A*의 경우에는 h(n)과 g(n)을 모두 고려하여 불필요한 노드를 보지 않아도 되고 최적해도 보장해주지만
연산 속도가 느릴 수 있을 것 같다

따라서 실제로 많이 쓰이는 탐색 기법은 언덕 오르기와 빔 서치라고 한다

A* Search 와 균일비용탐색을 비교해보면,
균일비용탐색보다 A*가 조금 덜 걸렸고, OPEN에서 고려해야 하는 노드의 수도 더 적었다
A*는 f(n)을 사용하기 때문에 걸러지는 노드가 더 정확한 기준에 의해 이루어지기 때문인 것 같다
따라서 A*서치가 균일비용탐색보다 더 빠르다고는 할 수 없다
연산할 게 더 많기 때문에 더 느린 속도를 낼 수도 있다

또 A* Search와 최상우선탐색을 비교해보면,
최상우선탐색에서 찾은 해는 a-b-d-g이고 비용이 10만큼 들었다
A* Search에서 찾은 해는 a-c-e-f-g이고 비용이 8만큼 들었다
Depth가 낮다고 무조건 좋은 해는 아니며, A*를 통해 찾은 해의 퀄리티가 여기에선 더 좋다

---

다음 예제는 8-퍼즐이다

• h(n)은 목표 상태의 퍼즐과 다른 퍼즐의 개수이고, 빈칸도 포함하여 count한다
• g(n)은 퍼즐을 이동하는 데 소모된 비용으로 여기에서는 depth를 의미한다