맹목 탐색

개념

맹목 탐색은 목표에 가까운지 알려주는 특별한 정보 없이, 미리 정한 순서에 따라 상태 공간을 탐색하는 방법이다. Blind search라고도 한다.

대표 알고리즘

대표적인 맹목 탐색에는 깊이 우선 탐색과 너비 우선 탐색이 있다. 깊이 우선 탐색은 한 경로를 끝까지 파고들고, 너비 우선 탐색은 같은 깊이의 노드를 모두 살핀 뒤 다음 깊이로 내려간다.

장점과 한계

맹목 탐색은 단순하고 일반적이다. 하지만 문제의 특성을 사용하지 않기 때문에 상태 공간이 크면 매우 비효율적이다. 이 한계를 줄이기 위해 휴리스틱 탐색이 사용된다.

깊이 $d$까지 모든 노드를 확인하면 생성되는 노드 수는 분기 수 $b$에 대해 다음처럼 증가한다.

$$N(d)=\sum _{i=0}^d{b}^i=\frac{b^{d+1}-1}{b-1}$$