빔 탐색

1. 개요

빔 탐색은 너비 우선 탐색을 기반으로 하는 탐색 알고리즘으로, 탐색 트리의 각 레벨에서 휴리스틱 비용이 가장 좋은 미리 결정된 수의 상태만 유지하고 확장한다. 빔 폭이라고 불리는 이 숫자는 탐색에 필요한 메모리를 제한하며, 빔 폭이 클수록 더 많은 상태가 유지되고, 빔 폭이 1이면 언덕 오르기 알고리즘과 유사해진다. 빔 탐색은 완전성을 희생하며 최적의 해를 보장하지 않지만, 대규모 시스템에서 실용성을 유지하기 위해 사용되며, 기계 번역 시스템 등에서 활용된다. 빔 스택 탐색, 깊이 우선 빔 탐색, 지역 빔 탐색, 확률적 빔 탐색 등 다양한 변형이 존재한다.

더 읽어볼만한 페이지

• 검색 알고리즘 - 유전 알고리즘
  유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.
• 검색 알고리즘 - 역색인
  역색인은 단어와 해당 단어가 포함된 문서 간의 관계를 나타내는 자료 구조이며, 검색 엔진의 쿼리 속도를 최적화하는 데 사용된다.