作者: Ariel Felner , Rami Puzis , Wheeler Ruml , Roni Stern , Scott Kiesel
DOI:
关键词: Incremental heuristic search 、 Coding theory 、 Maximization 、 Snake-in-the-box 、 Longest path problem 、 Mathematical optimization 、 Search problem 、 Cube 、 Heuristics 、 Mathematics
摘要: Snake in the Box (SIB) is problem of finding longest simple path along edges an n -dimensional cube, subject to certain constraints. SIB has important applications coding theory and communications. State art algorithms for solving apply uninformed search with symmetry breaking techniques. We formalize this as a propose several admissible heuristics solve it. Using proposed shown have huge impact on number nodes expanded and, some configurations, runtime. These results encourage further research using heuristic SIB, maximization problems more generally.