GRH – Genetic Rush Hour: Uma heuristica genética na solução de problemas Pspace-completo

Abstract

Este artigo descreve uma solução para resolver o quebra-cabeça Rush Hour utilizando um algoritmo genético. Este quebra-cabeça é um problema do tipo Pspace-completo. Na teoria da complexidade computacional, PSPACE é o conjunto de todos os problemas de decisão que podem ser resolvidos por uma máquina de Turing usando uma quantidade polinomial de espaço, e é dito PSPACE-completo se pertence á classe de complexidade PSPACE e todos os problemas em PSPACE podem ser reduzidos a ele em tempo polinomial. A heurística implantada para solucionar o problema individualiza os indivíduos da população do algoritmo genético a partir dos movimentos possíveis no quebra-cabeça. A heurística será discutida em detalhes no que diz respeito ao seu efeito sobre a população, cálculo de aptidão, mutação e operadores de crossover.