TProcura
Biblioteca em C++ para testes paramétricos de algoritmos, e coleção de algoritmos de procura e otimização
Loading...
Searching...
No Matches
✏️ Puzzle 8, procura em profundidade iterativa

Mantém-se o problema Puzzle8, com os mesmos 3 movimentos de exemplo desde a posição inicial:

1 2 3
4 5 6
7 8  
esquerda
1 2 3
4 5 6
7   8
cima
1 2 3
4   6
7 5 8
direita
1 2 3
4 6  
7 5 8

 A procura em profundidade iterativa vai expandir primeiro os estados gerados à menos tempo, antes dos restantes, mas com um nível de profundidade incremental, primeiro 1, se falhar passa a 2, e assim por diante.

Geração Estado Nível Pai Expansão
1
1
2
3
4
6
 
7
5
8
1
0 1
2
1
2
 
4
6
3
7
5
8
0
1 4 limite
3
1
2
3
4
  6
7
5
8
0
1 3 limite
4
1
2
3
4
6
8
7
5
 
0
1 2 limite
5
1
2
3
4
6
 
7
5
8
2
0 5
6
1
2
 
4
6
3
7
5
8
1
5 12
7
1
2
3
4
  6
7
5
8
1
5 8
8
1
2
3
4
6
8
7
5
 
1
5 6
9
1
2
3
4
6
8
7
  5
0
8 7 limite
10
1
  3
4
2
6
7
5
8
0
7 11 limite
11
1
2
3
  4
6
7
5
8
0
7 10 limite
12
1
2
3
4
5
6
7
  8
0
7 9 limite
13
1
  2
4
6
3
7
5
8
0
6 13 limite
14
1
2
3
4
6
 
7
5
8
3
0 14
15
1
2
 
4
6
3
7
5
8
2
14  
16
1
2
3
4
  6
7
5
8
2
14 19
17
1
2
3
4
6
8
7
5
 
2
14 15
18
1
2
3
4
6
8
7
  5
1
17 16
19
1
2
3
4
  8
7
6
5
0
18 18 limite
20 
1
2
3
4
6
8
  7
5
0
18 17 limite
21
1
  3
4
2
6
7
5
8
1
16  
22 
1
2
3
  4
6
7
5
8
1
16  
23 
1
2
3
4
5
6
7
  8
1
16 20
24 
1
2
3
4
5
6
  7
8
0
23  
25 
1
2
3
4
5
6
7
8
 
0
23 21 Solução!

Ficheiro de Excel, passo a passo:

Nesta procura houve 25 estados gerados, e 21 estados expandidos. Foi encontrada a solução  que passa pelos estados 25, 23, 16, 14. O que está nesta tabela?

Basicamente o mesmo que na procura em profundidade primeiro, o exemplo é também o mesmo. Mas neste caso o primeiro estado começa com o nível 1. Ou seja, executa-se uma procura em profundidade a nível 1, tendo resultado nos estados de 1 a 4, não tendo sido encontrada nenhuma solução e estando todos os estados gerados expandidos. A procura falhou, pelo que na linha 5 gera-se novamente o estado inicial, mas desta vez com limite 2, um valor a mais relativamente à última procura. O resultado são os estados da linha 5 até à linha 13, sendo o resultado também negativo. Na linha 14 gera-se novamente o estado inicial mas com nível de profundidade a 3, resultando da linha 14 até à linha 25 na mesma procura que o exemplo anterior.

Este algoritmo não necessita de um valor para a profundidade, garantindo a descoberta de uma solução de menor comprimento.

 Ação: Execute este mesmo algoritmo para o seguinte estado inicial:
1 2 3
4   6
7 5 8
Geração Estado Nível Pai Expansão
1
1 2 3
4   6
7 5 8
1 0 1
2
1   3
4 2 6
7 5 8
0 1 5 limite
3
1 2 3
  4 6
7 5 8
0 1 4 limite
4
1 2 3
4 6  
7 5 8
0 1 3 limite
5
1 2 3
4 5 6
7   8
0 1 2 limite
6
1 2 3
4   6
7 5 8
2 0 6
7
1   3
4 2 6
7 5 8
1 6  
8
1 2 3
  4 6
7 5 8
1 6  
9
1 2 3
4 6  
7 5 8
1 6  
10
1 2 3
4 5 6
7   8
1 6 7
11
1 2 3
4 5 6
  7 8
0 10  
12
1 2 3
4 5 6
7 8  
0 10 8 Solução!

◀ Passo anterior Próximo passo ▶