개요
빔 서치는 Best-First Search에서 기억 노드의 수를 제한하는 방법이다. Best-First Search는 최적의 해를 찾아가지만, 만약 다음 노드로 가는 해가 많이 존재한다면 그 해를 다 구해서 비교하고 평가하는 작업이 필요하다는 단점이 있다. 따라서 제약된 기억공간을 통해서 어느정도는 합리적인 답을 최대한 빠르게 탐색하는 방법이다.
구체적으로는 BFS Searc로 다음 상태의 해 집합을 구한다음, 해 집합을 Goal에 가까운 순서대로 정렬한다. 그 후 사전 설정된 수 만큼의 해 집합을 유지하고 나머지는 잘라낸다.
이때 처음 몇개의 해들이 하나의 지역 최대값으로 수렴하는 경우가 있는데, 이를 막고자 여러개의 랜덤한 노드를 선택하고 그중에 최적의 해를 선택하는 방식을 사용하기도 한다. 이를 Stochastic Local Beam Search라고 한다.