Euler tour beam search

Revision en1, by Rafbill, 2023-12-13 22:37:56

Hello !

Last year I invented an alternative implementation of beam search, which I call Euler tour beam search (it relies on Euler tours of subtrees of the search tree). I've since started using it in optimization contests (Atcoder heuristic contests, Topcoder marathon matches and some others). It often achieves better performance than typical implementations, and more importantly enables the use of beam search for problems with large state representations.

I have written some explanations here.

Tags beam search, heuristics, optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Rafbill 2023-12-13 22:37:56 644 Initial revision (published)