Solving the Snake in the Box Problem with Heuristic Search: First Results

作者: Ariel Felner , Rami Puzis , Wheeler Ruml , Roni Stern , Scott Kiesel

DOI:

关键词: Incremental heuristic searchCoding theoryMaximizationSnake-in-the-boxLongest path problemMathematical optimizationSearch problemCubeHeuristicsMathematics

摘要: 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.

参考文章(1)
Peter Hart, Nils Nilsson, Bertram Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths IEEE Transactions on Systems Science and Cybernetics. ,vol. 4, pp. 100- 107 ,(1968) , 10.1109/TSSC.1968.300136