Análise da Solução do Problema do Caminho Hamiltoniano Através de Redução para Problema da Satisfazibilidade Booleana

Abstract

O problema do caminho hamiltoniano e o problema da satisfazibilidade booleana são problemas NP-completos clássicos. Tais problemas são de grande importância para a teoria da computação. Este trabalho tem como objetivo investigar a solução do problema do caminho hamil- toniano através de redução para o problema da satisfazibilidade booleana. As reduções apresentadas no trabalho foram implementadas para que as fórmulas resultantes fossem submetidas a aplicações de determinação de satisfazibilidade. Essas aplicações e os algoritmos em que se baseiam também são detalhadas no texto. O desempenho das reduções e das aplicações é analisado através de testes com grafos gerados aleatoriamente e com grafos do problema do passeio do cavalo. O desempenho de um método direto de determinação de caminhos hamiltonianos também é comparado com os resultados obtidos. Essa comparação demonstra que, apesar de interessante do ponto de vista teórico, a técnica implementada é inferior em desempenho a métodos diretos de determinação de caminhos hamiltonianos.