PESC/COPPE-UFRJ
Disciplina: Inteligência Artificial
Professora Inês Dutra
As Torres de Hanoi
Resolução por algoritmos de Busca
Daniel N. Epitácio Pereira
A Lenda das Torres
A Lenda das Torres
O Quebra-Cabeça
Edouard Lucas, 1883
Forma tradicional:


N discos
3 varas
Solução ótima:

2N-1 movimentos
Variações:


K varas
Liberdade de Objetivo
Problema de Busca
Objetivo estabelecido: N = 15

32.767 movimentos!
Operadores:
Pilhas de origem e de destino
 Podem ser inválidos ou infrutíferos

Estados:

Pilha em que se situa cada peça
Ramificação = 3 (*)
Métodos de Busca
A*

Heurística + Custo
Guloso (Greedy Search)

Heurística
Busca em Largura (ou de Custo Uniforme)

Custo
Operadores
Inválidos:
Se tem como pilha de origem uma pilha vazia
 Se levam uma peça para cima de outra menor

Infrutíferos

Movimentos nulos:
Operadores
Infrutíferos

Reversão:

Perda Imediata de
Otimalidade:
Ramificação:
No máximo 2
Heurística
Deve ser admissível
Deve ser uma estimativa inferior do número de
passos até a solução
 Caso contrário, a otimalidade não estará
garantida

Não deve ser muito subestimada
Ou a performance será prejudicada
 Heurísticas que se aproximam da distância real
à solução podem garantir complexidade subexponencial

Heurística
Baseada no número de peças na posição
correta.

Pode ser feita de forma admissível, mas então o
segundo critério fica prejudicado
Distâncias “relaxadas” à posição correta

Um pouco mais elaborada. Admissível, mas
ainda pouco eficiente
Heurística
Heurística
Por Estágios
Funciona um pouco melhor
 Distância do início de cada
estágio à solução é
conhecido

Estágios Recursivos

Ideal
Implementação
Em C++ (usando MingW32).
Faz uso de uma fila de prioridades (STL) de
configurações do jogo, com base na
heurística e no custo correspondente.
Cada uma dessas configurações aponta para
um nó. Os nós formam uma árvore baseada
em encadeamento.
Implementação
A configuração correspondente a cada nó já
expandido é removida da memória
Fila de Estados
Árvore de Nós
Resultados
Busca em Largura

Até 5 peças
Método Guloso

15 ou mais peças (sub-ótimo)
A*
15 ou mais peças (ótimo)
 15 peças com pouco mais do que 120.000 nós
expandidos.

Amostra e Referências
[1] Tower of Hanoi: Fascinating Facts (LHS):
http://www.lhs.berkeley.edu/Java/Tower/towerhistory.html
[2] Russel, S., Norvig, P. – Artificial Intelligence: A Modern Approach
[3] Rich, E., Knight, K. – Inteligência Artificial