[Algorithm/자료구조] 체계적인 탐색(systematic search)

상태 공간 트리(state space tree search)를 체계적으로 탐색한다. 

 

<상태 공간 트리_state space tree search>

- 문제 해결 과정의 중간 상태들을 모두 Node로 구현해놓은 트리이다.
- 상태 공간 트리의 Leaf Node는 해당 문제의 해(Solution)에 해당된다.
- Optimum(최적해)는 Leaf Node 어딘가에 위치해 있고, 이를 효율적으로 찾아내는 것이 이 포스트의 주요 이슈이다.

 

참고 : https://dad-rock.tistory.com/689

 

퇴각 검색법 (baccktracking)
- 순환(recursion), 스택(stack)
- DFS(깊이 우선 탐색)과 유사한 방식

 

분기와 한정(branch-and-bound)
-힙(heap)등 우선순위 큐(priority queue)
-BFS(너비우선탐색)과 유사한 방식- 큐 대신 우선순위 큐 사용