Embed Size (px)
DESCRIPTION
JOGO DOS OITO. A* e IDA*. O JOGO. Configuração inicial: escolhida pelo usuário. Configuração final:. A ESTRUTURA. estado. custo = nível. Operador {CIMA, BAIXO, ESQUERDA, DIREITA, SEMPAI}. h = Manhattan distance. f = custo + h. pai. ESTRATÉGIAS. - PowerPoint PPT Presentation
Citation preview
JOGO DOS OITO
A* e IDA*
O JOGO
Configuração inicial: escolhida pelo usuário
Configuração final:
1 2 38 47 6 5
2 1 58 47 6 3
custo = nível
h = Manhattan distance
f = custo + h
estado
Operador {CIMA, BAIXO,ESQUERDA, DIREITA,SEMPAI}
pai
A ESTRUTURA
ESTRATÉGIAS
A*: Expande o nó no caminho da solução de menor custo. É completa e ótima desde que a heurística utilizada seja admissível e monotônica. Maior problema é a complexidade espacial.
IDA*: modifica a A* para diminuir o espaço ocupado em memória, transformando numa busca iterativa em profundidade. É completa e ótima.
IMPLEMENTAÇÃO - A*
2 8 35 6 4 1 7
2 8 5 6 34 1 7
2 8 35 6 74 1
2 85 6 34 1 7
pai
2 8 35 6 4 1 7
estado
custo = 0h = 15f = 15
custo = 1h = 16f = 17
custo = 1h = 16f = 17
custo = 2h = 15f = 17
2 8 35 64 1 7
custo = 1h = 16f = 17
custo = 2h = 17f = 19
IMPLEMENTAÇÃO - A*
2 8 35 6 4 1 7
2 8 5 6 34 1 7
2 8 35 6 74 1
2 85 6 34 1 7
pai
2 8 35 6 4 1 7
estado
custo = 0h = 15f = 15
custo = 1h = 16f = 17
custo = 1h = 16f = 17
custo = 2h = 15f = 17
2 8 35 64 1 7
custo = 1h = 16f = 17
IMPLEMENTAÇÃO - IDA*
2 8 35 6 4 1 7
2 8 5 6 34 1 7
2 8 35 6 74 1
pai
estado
custo = 0h = 15f = 15
custo = 1h = 16f = 17
custo = 1h = 16f = 17
2 8 35 64 1 7
custo = 1h = 16f = 17
IMPLEMENTAÇÃO - IDA*
2 8 35 6 4 1 7
2 8 5 6 34 1 7
2 8 35 6 74 1
2 85 6 34 1 7
pai
2 8 35 6 4 1 7
estado
custo = 0h = 15f = 15
custo = 1h = 16f = 17
custo = 1h = 16f = 17
custo = 2h = 15f = 17
2 8 5 6 34 1 7
2 8 35 6 74 1
2 8 35 64 1 7
custo = 1h = 16f = 17
custo = 2h = 17f = 19
2 8 35 64 1 7
custo = 3h = 16f = 19
custo = 3h = 16f = 19
custo = 3h = 16f = 19
EXECUÇÃO
RESULTADOS
Configuração A* IDA* A* IDA* A* IDA* A* IDA*1 Nível - 8 Nivel - 8 21 21 < 1 s < 1 s 640 By 640 By2 Nível - 11 Nivel - 11 33 29 < 1 s < 1 s 1 Kb 928 By3 Nível - 16 Nivel - 16 45 41 < 1 s < 1 s ~1,4 Kb ~1,3 Kb4 Nível - 16 Nivel - 16 4306 347 1 s < 1 s ~13,8 Kb ~1,5 Kb5 Nível - 21 Nivel - 21 5107 4403 2,02 m 1 s ~163,4 Kb ~2,0 Kb
6Não encontrada em 10000 nós gerados
Estouro de pilha
> 10000 > 10000 > 4 m > 9 m > 320 Kb -
7 Nível - 17 Nivel - 17 165 85 < 1 s < 1 s ~5,2 Kb ~1,6 Kb
8Não encontrada em 10000 nós gerados
Nivel - 25 > 10000 15185 > 4 m 1 s > 320 Kb ~2,4 Kb
9 Nível - 22 Nivel - 22 5696 5031 2,37 m 1 s ~182,3 Kb ~2,1 Kb
10Não encontrada em 10000 nós gerados
Nível - 28 > 10000 10651675 > 4 m 9,5 m > 320 Kb ~2,7 Kb
Solução Nós gerados Tempo Memória **
**Nos casos em que esta estimativa para o espaço ocupado pelo IDA* é maior do que a quantidade de nós gerada, o espaço é calculado pela quantidade de nós gerada.
