asadsasdas

Resolução de 8-Puzzle com A* em LISP
Léo Willian Kölln
13 de Agosto de 2006

Curso de Ciências da Computação
Programação Funcional - INE5363

INE - Departamento de Informática e Estatística
CTC - Centro Tecnológico
UFSC - Universidade Federal de Santa Catarina
1

1

O Algoritmo A*

Em Ciências da Computação, A* (pronunciado "A Estrela") é um algoritmo de procura em grafos que encontra um caminho de um dado nó inicial até outro nó de objetivo (ou algum teste de sucesso). Ele emprega a "heuristica de estimativa"que classica cada nó por uma estimativa da melhor rota atravez de tal nó. Ele visita os nós na ordem desta estimativa heuristica. O algoritmo A* também é um exemplo de procura pelo primeiro melhor resultado.
O algoritmo foi primeiramente denido em 1968 por Peter Hart, Nils Nilsson e Bertram Raphael. Em seu artigo ele foi chamado algoritmo A.

2

8-Puzzle
O 8-puzzle é tipo de "quebra-cabeças N", ou "N-Puzzle".

É um quebra-cabeça de movimento que consiste em uma grade de quadrados numerados onde um deles é vazio, ou não existe, com algo escrito sobre ele.
O quebra-cabeça começa embaralhado. Se a grade é 3x3, o quebra-cabeça é chamado de "8-puzzle"ou "9-puzzle". Se a grade for 4x4 será "15-puzzle"ou
"16-puzzle", e assim por diante. O objetivo do quebra-cabeça é desembaralhar as peças fazendo apenas movimentos de "deslizar"quadrados para o espaço em branco, fazendo com que apareça outro espaço em branco na posição da peça que foi movimentada.
O "n-puzzle"é um problema clássico de modelagem de algoritmos heurísticos.
Geralmente as heurísticas usadas para este problema incluem contar o número das peças faltantes e então encontrar a soma das Distâncias Manhattam entre cada bloco e sua posição ideal (o objetivo). Note que alguns casos são admissíveis, por exemplo, nunca sobre-estimam o numero de movimentos restantes, o que garante otimização para certos algoritmos de procura, como o A*.
Algumas posições iniciais do