O Problema Snake-In-The-Box: Origem, Desafios e Técnicas de Solução
Autores
|
7500 |
330,3049,3246
|
|
|
7501 |
330,3049,3246
|
|
|
7502 |
330,3049,3246
|
Informações:
Publicações do PESC
Este trabalho tem como objetivo apresentar o problema Snake-in-the-Box, abreviadamente problema SIB, que consiste na busca pelos maiores caminhos induzidos abertos (resp. fechados), comumente denominados snakes (resp. coils), em grafos da família dos hipercubos. A abordagem visa tornar o tema acessível tanto para iniciantes quanto para especialistas, utilizando uma linguagem clara e explicando os conceitos e pré-requisitos necessários. São introduzidos os fundamentos do problema SIB, incluindo sua origem em 1958, sua evolução, principais aplicações práticas e os métodos para representar, validar e buscar snakes em hipercubos de dimensão d.
Inicialmente, são apresentados limitantes inferiores e superiores para cada dimensão dos hipercubos, com base em métodos matemáticos e conceitos da teoria dos grafos. Em seguida, discutem-se os algoritmos de busca que foram adaptados, aperfeiçoados e implementados em programas computacionais, permitindo a identificação de snakes cada vez maiores. Alguns desses caminhos são comprovadamente máximos absolutos, enquanto outros representam os maiores conhecidos até o momento.
O trabalho também analisa uma ampla base de publicações, incluindo artigos técnicos, dissertações e teses divulgados desde 1958. Esses estudos são examinados para abordar tanto os fundamentos matemáticos que definem tanto os limitantes quanto os diferentes algoritmos empregados para explorar o problema SIB.
Adicionalmente, foi implementado um algoritmo customizado do tipo Stochastic Beam Search, um dos vários métodos de busca utilizados por pesquisadores para obter as maiores snakes. Essa implementação oferece aos leitores uma abordagem prática que lhes permite avaliar a complexidade envolvida no problema SIB.
This work aims to present the Snake-in-the-Box problem, abbreviated as SIB problem, which consists of searching for the longest induced open (resp. closed) paths, commonly referred to as snakes (resp. coils), in graphs from the family of the hypercubes. The approach aims to make the topic accessible to both beginners and experts, using clear language and explaining the necessary concepts and prerequisites. The fundamentals of the SIB problem are introduced, including its origin in 1958, its evolution, main practical applications, and methods for representing, validating, and searching for snakes in hypercubes of dimension d.
Initially, lower and upper bounds for each dimension of hypercubes are presented, based on mathematical methods and concepts from graph theory. Next, the search algorithms that have been adapted, refined, and implemented in computer programs are discussed, enabling the identification of increasingly larger snakes. Some of these paths are proven to be absolute maxima, while others represent the longest known paths to date.
The work also analyzes a broad range of publications, including technical papers, dissertations, and theses published since 1958. These studies are examined to address both the mathematical foundations that define the bounds and the different algorithms used to explore the SIB problem.
Additionally, a custom Stochastic Beam Search algorithm was implemented, one of the various search methods used by researchers to find the longest snakes. This implementation provides readers with a practical approach, enabling them to assess the complexity involved in the SIB problem.