Keys
Schema Diagrams
Relational Query Languages
Basic operator인 6개를 바탕으로 Additional Operations로 확장을 하게 됨.
지난 Search (DFS, BFS, UCS)의 최종 결론은, UCS가 좋긴 한데(Complete, Optimal) 방향성이 없기 때문에 필요 이상의 Fringe 숫자가 늘어나는 단점이 있다는 점이었음.
그러한 Search를 blind search의 한계라고 할 때, 어느정도 판단할 수 있는 기준을 가지고 search를 하는 informed search(=herustic search)에 대하여 알아봄.
heuristic
Greedy
A* algorithm
!!!
UCS: Orders by path cost, or backward cost g(n).
Greedy: Orders by goal proximity, or forward cost h(n).
A* Algorithm : Orders by the sum! g(n) + h(n)
A*는 언제 끝나야 하나?
단순히 Goal State가 Queue에 enqueue 되었다고 해서, 그 경로가 최단 경로는 아님.
Goal State가 dequeue 될 때가 최단경로임!
A*는 Optimal한가?
Yes. with some condition -> future estimation is optimistic.
만약, 어떤 future에 대한 cost를 너무 높게 측정한다면, 실제로 optimal했을 경로를 선택하지 못하는 문제가 발생할 수 있음.
그럼 마냥 optimistic(=admissible)한 heuristic이면 어떤가?
Still Optimal함. 다만 과하게 optimistic한 heuristic은 fringe의 수를 늘리면서 결과적으로 방향성 없는 UCS와 다를 바 없는 Search일 수 도 있음.
0 <= h(n) - Heuristic function <= h*(n) - Actual Cost.