Euler tour beam search

Правка en1, от 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.

Теги beam search, heuristics, optimization

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Rafbill 2023-12-13 22:37:56 644 Initial revision (published)