빔 검색

그래프 및 트리쉬 알고리즘
α–β A* B* 역추적 빔 벨먼-포드 베스트 퍼스트 양방향 보르슈프카 분기 & 바운드 BFS 대영 박물관 D* DFS 디크스트라 에드먼즈 플로이드-워셜 프린지 검색 힐 클라이밍 IDA* 반복적 심화 존슨 점프 포인트 크루스칼 사전 BFS LPA* 프라이머리 SMA*
목록
그래프 알고리즘 검색 알고리즘 그래프 알고리즘 목록
관련 항목
동적 프로그래밍 그래프 통과 나무횡단 검색 게임 그래프 컬러링
v t

컴퓨터 과학에서 빔 검색은 제한된 집합에서 가장 유망한 노드를 확장하여 그래프를 탐색하는 경험적 발견 알고리즘이다. 빔 검색은 메모리 요구 사항을 줄이는 베스트 퍼스트 검색을 최적화한 것이다. 가장 먼저 검색하는 것은 일부 경험적 접근법에 따라 모든 부분 해결책(상태)을 주문하는 그래프 검색이다. 그러나 빔 검색에서는 미리 정해진 수의 가장 좋은 부분적 해결책만 후보로 유지된다.^[1] 따라서 탐욕스러운 알고리즘이다.

'빔 검색'이라는 용어는 1977년 카네기멜론 대학의 라지 레디가 만들었다.^[2]

세부 사항

빔 검색은 폭 우선 검색을 사용하여 검색 트리를 만든다. 나무의 각 레벨에서, 그것은 현재 레벨에서 주의 모든 후계자를 생성하며, 그것들을 경험적 비용의 증가 순서에 따라 분류한다.^[3] 단, 각 레벨(빔 폭이라고 함)에서 가장 좋은 상태의 사전 결정된 수인 $\beta {\displaystyle }$ ${\displaystyle \beta$}만 저장한다. 오직 그 주들만 다음에 확장된다. 빔 폭이 클수록 가지치기되는 상태가 적다. 무한 빔 너비에서는 상태를 가지런히 하지 않으며 빔 검색이 너비 우선 검색과 동일하다. 빔 너비는 검색을 수행하는 데 필요한 메모리를 제한한다. 목표 상태가 잠재적으로 제거될 수 있기 때문에 빔 검색은 완전성을 희생시킨다(알고리즘이 존재하는 경우 솔루션으로 종료된다는 보장). 빔 검색은 최적 상태가 아니다(즉, 최선의 해결책을 찾을 것이라는 보장이 없다). ^[4]

사용하다

빔 검색은 전체 검색 트리를 저장하기에 메모리의 양이 충분하지 않은 대형 시스템에서 추적성을 유지하기 위해 가장 자주 사용된다.^[5] 예를 들어, 그것은 많은 기계 번역 시스템에서 사용되어 왔다.^[6] (지금의 기술 상태는 주로 신경 기계 번역에 기반한 방법을 사용한다.) 최고의 번역을 선택하기 위해 각 파트를 처리하고, 여러 가지 다양한 번역 방법이 등장한다. 문장 구조에 따른 최상급 번역은 보관하고 나머지는 폐기한다. 그런 다음 번역자는 주어진 기준에 따라 번역을 평가하여 목표를 가장 잘 지키는 번역을 선택한다. 빔 검색을 처음 사용한 것은 1976년 CMU 하피 음성 인식 시스템이었다.^[7]

변형

빔 검색은 깊이 우선 검색과 결합해^[8] 빔 스택 검색과 깊이 우선 검색이 이뤄지고,^[5] 한정된 불일치 검색으로 ^[9]BULB(제한된 불일치 역추적^[5])를 이용한 빔 검색이 이뤄졌다. 결과 검색 알고리즘은 빔 검색과 같이 양호하지만 부최적 솔루션을 신속하게 찾은 다음 최적의 솔루션으로 수렴하기 전까지 개선된 솔루션을 계속 찾아내는 알고리즘이다.

지역 검색의 맥락에서, 우리는 검색 지역 빔은 무작위로 생성된 주β{\beta\displaystyle}을 선택한 다음 시작할 때까지 목표에 도달한 탐색 트리의 각 단계별로, 그것은 항상 공개하는 현행의 모든 후임자 중β{\beta\displaystyle} 새로운 주가 감안한 특정 알고리즘이라고 부릅니다.[10][11]

로컬 빔 검색은 종종 로컬 최대값에 도달하므로 공통 해결책은 다음 $\beta {\displaystyle }$ ${\displaystyle \beta }$ 상태를$$ 무작위로 선택하는 것이며, 이러한 상태는 주의 경험적 접근성 평가에 따라 달라진다. 이런 종류의 검색을 확률형 빔 검색이라고 한다.^[12]

다른 변형으로는 유연한 빔 검색과 복구 빔 검색이 있다.^[11]

참조