GRH – Genetic Rush Hour: Uma heuristica genética na solução de problemas Pspace-completo
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...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Portugués |
| Publicado: |
2012
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/23589 |
| Aporte de: |
| Sumario: | 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. |
|---|