A técnica 'Simulated Annealing' aplicada aos problemas de Percurso do Cavalo e Dama Pacíficas

Abstract

Um grande desafio para a área de Algoritmos é o conjunto de problemas que formam a classe NP-Completo. Trata-se de inúmeros problemas de grande importância teórica e prática, para os quais não são conhecidas soluções computacionais eficientes. Várias técnicas têm sido desenvolvidas para tentar contornar a intratabilidade desses problemas. Dentre elas, uma das primeiras foi o Simulated Annealing. Este trabalho explica e ilustra a técnica, aplicando-a a dois problemas clássicos, ambos relacionados a um tabuleiro de xadrez: o Percurso do Cavalo e Damas Pacíficas. O objetivo é muito mais didático do que o de buscar soluçõoes eficientes para os problemas, uma vez que essas soluções já existem.