AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 8

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

Authors

Alon Palombo,Roni Stern,Rami Puzis,Ariel Felner,Scott Kiesel,Wheeler Ruml

Ben Gurion University of the Negev,Ben Gurion University of the Negev,Ben Gurion University of the Negev,Ben Gurion University of the Negev,University of New Hampshire,University of New Hampshire


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 8

Volume

Issue:

Vol. 8 No. 1 (2015): Eighth Annual Symposium on Combinatorial Search

Track:

Full Papers

Downloads:

Download PDF

Abstract:

Snake in the Box (SIB) is the problem of finding the longest simple path along the edges of an n-dimensional cube, subject to certain constraints. SIB has important applications in coding theory and communications. State of the art algorithms for solving SIB apply uninformed search with symmetry breaking techniques. We formalize this problem as a search problem and propose several admissible heuristics to solve it. Using the proposed heuristics is shown to have a huge impact on the number of nodes expanded and, in some configurations, on runtime. These results encourage further research in using heuristic search to solve SIB, and to solve maximization problems more generally.

DOI:

10.1609/socs.v6i1.18357


SOCS

Vol. 8 No. 1 (2015): Eighth Annual Symposium on Combinatorial Search