3주차 휴리스틱 탐색 및 지역 탐색 (3-1 휴리스틱 탐색)

3주차 휴리스틱 탐색 및 지역 탐색 (3-1 휴리스틱 탐색)

3주차 휴리스틱 탐색 및 지역 탐색 (3-1 휴리스틱 탐색)

지난 시간에는 다른 정보가 전혀 없는 상태에서 탐색을 수행하는 방법에 대해 배웠는데요. (Uninformed search)

오늘은 부가적인 정보가 많은 경우에 그것을 어떻게 활용하여 탐색을 하는지를 배울 차례입니다. (Informed search)

휴리스틱을 사용하는 Informed search strategies는 평가함수를 정의합니다.

즉, 어떤 노드가 바람직한 노드인지 평가하고, 평가함수 값이 높은 노드부터 깊이 펼치는 것이죠.

1. Greedy best-first search

한 가지 기준을 정하여, 그것을 바탕으로 각 노드로 가는 경로별 함수 값을 구합니다.

그 후, 가장 효율적인 (평가함수 값이 높은) 노드부터 오픈하는 것입니다.

2. A* search : f(n) = g(n)+h(n)

g(n) : n까지 가는 데 드는 비용

h(n) : n부터 목표까지 가는 데 드는 추정 비용

f(n) : n을 통해 목표까지 가는 데에 드는 총 추정 비용

중요 : 이미 비용이 많이 소모된 노드는 더 이상 펼치지 않습니다.

* 지금까지 나온 추정 비용 중 최소값보다 더 큰 값은 펼치지 않음

좋은 휴리스틱 함수(Heuristic function)를 정의하고, 그 함수를 활용해서 목표를 찾는 노력엔 트레이드 오프 관계가 있다.

좋은 휴리스틱 함수가 있으면, 더 나은 솔루션을 찾을 수 있지만

좋은 함수를 찾거나 그것을 정의한다는 것 자체에 더 많은 노력이 필요함

3. Admissible Heuristics : h(n) ≤ h*(n)

휴리스틱 함수가 실제 비용보다 항상 적게 추정, 즉 실제 값보다 항상 작거나 같게 예측을 하는 경우

휴리스틱 함수가 Admissible 할 경우, A* 알고리즘이 최적의 솔루션을 줌

from http://data-learning-jjoshu.tistory.com/7 by ccl(A) rewrite - 2021-12-06 19:26:31