보 스택 검색

Beam stack search

빔 스택[1] 검색은 시간순 역추적(즉 깊이 우선 검색)과 빔 검색을 결합한 검색 알고리즘으로 깊이 우선 빔 [2]검색과 유사합니다.두 검색 알고리즘 모두 빔 검색과 같이 우수하지만 차선의 솔루션을 신속하게 찾은 후 최적의 솔루션으로 수렴될 때까지 백트래킹하여 개선된 솔루션을 계속 찾는 알고리즘입니다.

실행

빔 스택 검색은 빔 스택을 데이터 구조로 사용하여 시간순 백트래킹을 빔 검색과 통합하고 분할 및 정복 알고리즘 기술과 결합할 수 있으므로 빔 스택 검색이 분할 및 정복됩니다.

대체 수단

BULB(제한 불일치 역추적[2])를 사용한 빔 검색은 제한된 불일치 검색과 빔 검색을 결합하여 비연대적 역추적을 수행하는 검색 알고리즘으로, 종종 빔 스택 검색 및 깊이 우선 빔 검색에 의해 수행된 시간적 역추적보다 성능이 우수합니다.

레퍼런스

  1. ^ Zhou, Rong; Hansen, Eric (2005). "Beam-Stack Search: Integrating Backtracking with Beam Search". CiteSeerX 10.1.1.71.4147. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  2. ^ a b 퍼시, 데이비드코닉 스벤"제한 불일치 빔 검색", 2005."Archived copy" (PDF). Retrieved 2007-12-22.