Search algorithm 정리

소개글

"Search algorithm 정리"에 대한 내용입니다.

목차

1. Performance Measure에 관해서
2. Uninformed search strategy
3. Informed search
4. Local search
5. Online Search Agent와 알려지지 않은 environement에서의 search 방법
6. Adversarial Search
7. Learning Heuristic: 강화학습, MCTS
8. 알파고 제로 논문에서의 MCTS
9. 최종 비교/대조

본문내용

1. Performance Measure에 관해서
Search strategy에 대하여 언급하기 전에 각 전략들에 대한 성능을 평가하기 위한 척도가 필요할 것이다. 척도에는 4가지가 존재하는데, completeness, optimality, time complexity, space complexity가 있다.
Completeness란, solution이 존재한다면, 알고리즘이 과연 solution을 잘 찾아낼 수 있는가에 대한 것이다. Optimality란, solution 중에서도 optimal한 solution을 찾고 있는가에 대한 것이다. Time complexity란, 그 solution을 빨리 찾아낼 수 있냐에 대한 것이고, Space complexity는 탐색을 위한 메모리가 얼마나 필요하냐에 대한 척도가 된다.
이중 complexity는 3가지, node에 해당하는 최대의 successor의 갯수인 branching factor, 가장 얕은 goal의 depth, state space에서 path의 가장 긴 길이에 영향을 받는다.
Cost를 계산하는 방법 또한 search cost와 total cost로 나뉜다. Search cost는 탐색을 하기 위한 비용을 일컫는다. Total cost는 탐색뿐만아니라 path 자체의 cost 또한 고려한 비용이다.

2. Uninformed search strategy
Uninformed search는 문제의 정의로부터 받은 state의 정보 외에 추가적인 정보를 받지 않는 전략을 말한다. 즉 현재 상태에서 목표까지 가기위한 step의 개수, 즉 path의 비용을 모른 상태에서의 전략을 말한다. 말그대로 ‘blind’한 search 방법인 것이다. 단 목표인 상태와 목표가 아닌 상태에 대한 구분은 가능하다. 이와 반대로 informed search는 어떤 상태가 potential이 있는지를 알 수 있다.

참고 자료

없음