O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico

The Hiker Dice was a game recently proposed in a software designed by Mara Kuzmich and Leonardo Goldbarg. In the game a dice is responsible for building a trail on an n x m board. As the dice waits upon a cell on the board, it prints the side that touches the surface. The game shows the Hamiltonian Path Problem Simple Maximum Hiker Dice (Hidi-CHS) in trays Compact Nth , this problem is then characterized by looking for a Hamiltonian Path that maximize the sum of marked sides on the board. The research now related, models the problem through Graphs, and proposes two classes of solution algorithms. The first class, belonging to the exact algorithms, is formed by a backtracking algorithm planed with a return through logical rules and limiting the best found solution. The second class of algorithms is composed by metaheuristics type Evolutionary Computing, Local Ramdomized search and GRASP (Greed Randomized Adaptative Search). Three specific operators for the algorithms were created as follows: restructuring, recombination with two solutions and random greedy constructive.The exact algorithm was teste on 4x4 to 8x8 boards exhausting the possibility of higher computational treatment of cases due to the explosion in processing time. The heuristics algorithms were tested on 5x5 to 14x14 boards. According to the applied methodology for evaluation, the results acheived by the heuristics algorithms suggests a better performance for the GRASP algorithm

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

O Hiker Dice foi um jogo proposto recentemente em um software projetado por Mara Kuzmich e Leonardo Goldbarg. No jogo um dado é responsável pela construção de uma trilha sobre um tabuleiro n x m. O dado ao visitar uma célula do tabuleiro imprime (marca) a face que entra em contato com a superfície. O jogo apresenta o Problema do Caminho Hamiltoniano Simples Máximo Hiker Dice (CHS-HiDi) em Tabuleiros Compactos de ordem N , esse problema é então caracterizado por buscar um caminho hamiltoniano que maximize a soma dos faces do dado marcados no tabuleiro. A pesquisa presentemente relatada, modela o problema através de Grafos, e propõe duas classes de algoritmos de solução. A primeira classe, pertencente aos algoritmos exatos, é constituída por um algoritmo em backtracking aparelhado com um retorno realizado através de regras lógicas e limite da melhor solução encontrada. A segunda classe de algoritmos é constituída por metaheurísticas do tipo Computação Evolucionária, Busca Local Aleatorizada e GRASP (Greed Randomized Adaptative Search). Para os algoritmos foram criados três operadores específicos da seguinte forma: de reestruturação, de recombinação com duas soluções e construtivo guloso aleatório. O algoritmo exato foi testado em tabuleiros 4x4 a 8x8 esgotando a possibilidade de tratamento computacional dos casos maiores em virtude da explosão em tempo de processamento. Os algoritmos heurísticos foram testados nos tabuleiros 5x5 até 14x14. Segundo a metodologia de avaliação utilizada, os resultados encontrados pelos algoritmos heurísticos sugere um melhor potencial de desempenho para o algoritmo GRASP