Advertisement
Published in:
2012 | OriginalPaper | Chapter
Monte-Carlo Search for Snakes and Coils
Author : David Kinny
Published in: Multi-disciplinary Trends in Artificial Intelligence
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The “Snake-In-The-Box” problem is a hard combinatorial search problem, first described more than 50 years ago, which consists in finding longest induced paths in hypercube graphs. Solutions to the problem have diverse and some quite surprising practical applications, but optimal solutions are known only for problems of small dimension, as the search space grows super-exponentially in the hypercube dimension. Incomplete search algorithms based on Evolutionary Computation techniques have been considered the state-of-the-art for finding near-optimal solutions, and have until recently held most significant records. This study presents the latest results of a new technique, based on Monte-Carlo search, which finds significantly improved solutions compared to prior techniques, is considerably faster, and, unlike EC techniques, requires no tuning.