빔 탐색

빔 탐색(Beam search)은 컴퓨터 과학에서 제한된 집합에서 가장 유망한 노드를 확장하여 그래프를 탐색하는 경험적 검색 알고리즘이다. 빔 탐색은 메모리 요구 사항을 줄이는 최상 우선 탐색을 최적화한 것이다. 최상 우선 탐색은 선택한 휴리스틱에 따라 모든 부분 솔루션(상태)의 순서를 지정하는 그래프 검색이다. 그러나 빔 탐색에서는 미리 정해진 개수의 최적 부분해만 후보로 유지된다. 따라서 탐욕 알고리즘이다. 무제한의 후보 집합으로 구현된 빔 탐색은 퇴각 알고리즘이 된다.

"빔 탐색"이라는 용어는 1977년 카네기 멜런 대학교의 라즈 레디가 만들어냈다.