Problema_8-Puzzle

Prévia do material em texto

Introdução 
No presente trabalho abordaremos a resolução do problema 8-puzzle, através do algoritmos de busca A*, que consiste encontrar a solução baseada no caminho mais curto. 
Será feita uma descrição dos procedimentos utilizados teoricamente e de forma prática através de um programa desenvolvido em Java. 
 
 
 
 
 
 
 
Objectivos 
 
Objectivo Geral: 
· Estudar o problema 8-puzzle. 
 
Objectivos específicos: 
· Analisar as possibilidades de busca; 
· Descrever a aplicação dos estados; 
· Perceber o modelo de transição de busca. 

 
 
 
 
 
 
 
 
 
Formulação do Problema 
O problema consiste em resolver um puzzle (8-puzzle): o algoritmo tem de descobrir a sequência de operações que permite passar do estado inicial até ao estado final, quando o Puzzle está ordenado de forma crescente, onde as regras do jogo são bastante simples, a peça vazia é a única que pode movimentar-se. 
Tipo de Agente 
Um Agente só possui sentido baseado nos seus objectivos e na sua capacidade de atingi-los. Para resolução do problema 8-puzzle, o tipo de agente nesse caso é o agente baseados em objetivos porque basear-se na descrição do estado atual e também precisa de alguma espécie de informação sobre os objetos que descrevam a situação desejável (estado final ou goal).( Russel e Norvig, 2004) 
Existem diversas formas de resolver o problema, usando os métodos: de busca à cega ou de busca com informação. 
Para problema em causa optou se pelo método de busca com informação usando o algoritmo de A*, onde o algoritmo busca expandir o nó com menor valor Custo (Caminho) na fronteira do espaço de estados, utilizando a heurística Custo (Caminho) = Custo (Quantidade de Movimentos) + Custo (Caminho Restante) (f(n) = g(n) + h(n)), o que permite uma simplificação, eliminando caminhos redundantes. 
Estados 
Estado inicial 	 	 	 	Estado Final (Goal) 
	
	1 
	2 
	3 
	8 
	6 
	4 
	7 
	5 
	 
	 
	
	1 
	2 
	3 
	8 
	 
	4 
	7 
	6 
	5 
 
Modelo de transição 
 
	1 
	2 
	3 
	8 
	6 
	4 
	7 
	5 
	 
 
 (0) 
 
 
	1 
	2 
	3 
	8 
	 6 
	4 
	7 
	 
	5 
	1 
	2 
	3 
	8 
	6 
	 
	7 
	5 
	4 
 (1) 	(2) 
 
 
 	 
	1 
	2 
	3 
	8 
	6 
	4 
	 
	7 
	5 
	1 
	2 
	3 
	(4) 
	1 
	2 
	3 
	8 
	 
	4 
	
	8 
	6 
	4 
	7 
	6 
	5 
	
	7 
	5 
	 
	(3) 	(5) 
 
 
	F(n) 
	G(n) 
	H(n) 
	Heurística 
	1 
	1 
	1 
	2 
	2 
	1 
	3 
	4 
	3 
	1 
	2 
	3 
	4 
	1 
	0 
	1 
	5 
	1 
	2 
	3 
Acções 
As acções que se podem aplicar aos estados, em geral, e que conduzem à sua alteração designam-se frequentemente por Operadores ou Operações. As operações do 8-puzzle são as seguintes: 
· Mover o espaço em branco para baixo; 
· Mover o espaço em branco para cima; 
· Mover o espaço em branco para a direita; 
· Mover o espaço em branco para a esquerda. 
À partir de um dos estados é onde podemos aplicar uma dessas acções. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Conclusão 
Após várias pesquisas na tentativa de resolver do problema 8-puzzle, foi possível desenvolver métodos que facilitaram a manipulação dos estados a partir do estado inicial até o objectivo (estado goal). 
Recorreu se ao método de busca com informação, nomeadamente o algoritmo A*, que consiste em fazer expansão dos nos até ao no final denominado goal. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Referências Bibliográficas 
RUSSELL, Stuart, NORVIG, Peter, Inteligência Artificial, Elservier Editora Ltda, Tradução da Terceira Edição, Brazil-RJ, 2013. 
BOTELHO, Luís Miguel, Inteligência Artificial, Apontamentos para as aulas - Algoritmos de procura, 2017. 
JUNIOR, Nelson F., GUIMARÃES, Frederico G., Problema 8-Puzzle: Análise da solução usando Algoritmos Genéticos e Backtracking.