컴퓨터 과학에서의 탐색 알고리즘
- 문제를 입력해서 그 문제에 대한 해 solution을 얻는 알고리즘
- 대부분의 문제 해결알고리즘들이 탐색 알고리즘
탐색 공간 search space, 상태공간 state space
- 문제를 푸는 가능한 해를 모두 모아둔 집합
탐색 일고리즘
1. 무정보 탐색 uninformed search
- 문제의 독특한 성질을 고려하지 않은 알고리즘으로 탐색 공간을 가장 단순하고 직관적인 방법으로 탐색.
- 쉽게 구현 가능, 똑같은 구현 방식을 추상화하여 넓은 문제 범위들에 사용 가능
-> 대부분의 상태공간이 매우 커짐. 무정보 탐색은 탐색 공간이 작은 경우에만 합리적인 시간 소요
=> 탐색 시간을 빠르게 하기 위해 정보 탐색을 주로 사용
2. 리스트 탐색 list search
- 가장 기본적인 탐색 알고리즘
- 키에 의해 집합의 한 요소를 찾음
- linear search, binary search, self-balancing binary search tree
3. 트리 탐색 tree search
- 탐색 기술의 핵심으로 트리 노드를 검색
- 너비 우선 탐색 breadth first search : 레벨 별로 탐색하거나
- 깊이 우선 탐색 depth first search : 리프 노드에 도달하고나서 백트래킹
* 그래프 이론의 많은 문제들이 트리 알고리즘의 확장으로 해결 가능
=> 다익스트라 알고리즘, 크루스칼 알고리즘, 최근접 이웃 알고리즘, 프림 알고리즘
정보 탐색 informed search, 휴리스틱 탐색 heuristic search
- 그 문제의 독특한 휴리스틱이 가이드로 사용됨
- 좋은 휴리스틱은 정보 탐색을 드라마틱하게 하여 무정보 탐색보다 능가하는 성능을 냄
- 대부분 정보 탐색 알고리즘은 트리에서 사용
-> 최상 우선 탐색 best-first search, A* 알고리즘