[AI]3장 Heuristic Search Tech.

1. Generate-and-Test

 - 단순히 풀이법을 만들어 실험해보는 방식

 1) 해결 가능한 Solution을 생성한다. 

 2) Solution이 맞는지 Test한다.

 3) 해결되면 그만두고, 실패하면 다시 1번으로 돌아간다

2. Hill Climbing

 - 현재 노드에서 가장 evaluation function 결과가 좋은 노드로 이동해 나가다가 더이상 좋은 노드가 없거나 goal state에 도착시 멈춤.

 1) 현재 노드에서 갈 수 있는 노드들을 evaluation 한다.

 2) 그 중 가장 높은 evaluation 값을 가진 노드로 이동

    만약 가장 높은 evaluation도 현재 evaluation보다 작다면 움직이지 않는다.

 3) 현재 노드가 goal state인지 확인, goal state 라면 끝, 아니면 다시 1로

3. Steepest-Ascent Hill Climbing

 - 현재 노드에서 가장 가파르게 evaluation 값이 상승하는 노드로 이동한다.

 1) 현재 노드에서 갈 수 있는 노드들을 evaluation 한다.

 2) 그 중 가장 많이 증가한 evaluation 값을 가진 노드로 이동

    만약 가장 많이 증가한 evaluation도 현재 evaluation보다 작다면 움직이지 않는다.

 3) 현재 노드가 goal state인지 확인, goal state 라면 끝, 아니면 다시 1로

4. Best-first search

 - 현재 펼쳐진 노드( evaluation을 평가했던 노드 )들 중에서 가장 큰 노드로 이동한다.

 1) 현재 노드에서 갈 수 있는 노드들을 evaluation 한다.

 2) 현재 펼쳐진 노드 중 evaluation 값이 가장 높은 노드로 이동

    evaluation 값이 가장 높은 노드가 없다면 움직이지 않음

 3) 현재 노드가 goal state인지 확인, goal state 라면 끝, 아니면 다시 1로

5. A* Search

 - 현재 펼쳐진 노드 중 evaluation 값과 start state에서 현재 노드까지 이동하는데 필요한 비용을 더한 값이 가장 작은 노드로 이동한다.
    f(n) = g(n) + h(n)   (f(n) : 총 값, g(n) : 현재 노드까지 이동하는데 소요된 비용, h(n) : goal state 까지 소모된다고 예측되는 비용)

 1) 현재 노드에서 갈 수 있는 노드들을 evaluation 하고, 현재 노드까지 소요된 비용을 더한다.

 2) 현재 펼쳐진 노드 중 계산된 값이 가장 높은 노드로 이동

    계산된 값이 가장 높은 노드가 없다면 움직이지 않음

 3) 현재 노드가 goal state인지 확인, goal state 라면 끝, 아니면 다시 1로 

6. Heuristic function estimate

 - Heuristic function을 overestimate 하지 않는 이상 admissible하다고 본다.

 - 만약 underestimate 하다면 optimal하지만 시간이 오래걸린다.