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 largura

Agora analisamos a procura em largura, utilizando apenas 2 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
   

 A procura em largura vai expandir primeiro os estados gerados à mais tempo, antes dos restantes, portanto expande pela mesma ordem que são gerados os estados.

Geração Estado Nível Pai Expansão
1
1
2
3
4
  6
7
5
8
0
0 1
2
1
  3
4
2
6
7
5
8
1
1 2
3
1
2
3
  4
6
7
5
8
1
1 3
4
1
2
3
4
6
 
7
5
8
1
1 4
5
1
2
3
4
5
6
7
  8
1
1 5
6
  1
3
4
2
6
7
5
8
2 
2  
7
1
3
 
4
2
6
7
5
8
2 
2  
8
  2
3
1
4
6
7
5
8
2 
3  
9
1
2
3
7
4
6
  5
8
2 
3  
10 
1
2
 
4
6
3
7
5
8
2 
4  
11 
1
2
3
4
6
8
7
5
 
2 
4  
12
1
2
3
4
5
6
  7
8
2 
5  
13 Solução!
1
2
3
4
5
6
7
8
 
2 
5   

Ficheiro de Excel, passo a passo:

Neste caso houve 13 gerações e 5 expansões. O teste da solução final é feito na geração, dado que neste caso pode ser bastante compensador relativamente a realizar o teste na expansão. Na situação concreta, significaria que se teria de fazer 13 expansões em vez das 5 necessárias, embora o número de testes de solução final seja igual em ambos os casos.

Pode-se utilizar o campo do nível a subir em vez de descer, dado que o algoritmo não tem parâmetros, utilizando-se esse campo apenas para fins informativos.

O algoritmo apresenta uma pequena diferença de execução, expande o estado gerado à mais tempo, em vez de ser à menos tempo, mas apresenta uma grande diferença para o algoritmo de profundidade primeiro: o elevado número de estados gerados e não expandidos.

⚡ Ação: Refaça esta procura mas utilizando o mesmo estado de partida que nos exemplos anteriores:
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
0 0 1
2
1 2  
4 6 3
7 5 8
1 1 2
3
1 2 3
4   6
7 5 8
1 1 3
4
1 2 3
4 6 8
7 5  
1 1 4
5
1   2
4 6 3
7 5 8
2 2 5
6
1   3
4 2 6
7 5 8
2 3 6
7
1 2 3
  4 6
7 5 8
2 3 7
8
1 2 3
4 5 6
7   8
2 3 8
9
1 2 3
4 6 8
7   5
2 4  
10
  1 2
4 6 3
7 5 8
3 5  
11
1 6 2
4   3
7 5 8
3 5  
12
  1 3
4 2 6
7 5 8
3 6  
13
1 3  
4 2 6
7 5 8
3 6  
14
  2 3
1 4 6
7 5 8
3 7  
15
1 2 3
7 4 6
  5 8
3 7  
16
1 2 3
4 5 6
  7 8
3 8  
17 Solução!
1 2 3
4 5 6
7 8  
3 8  

◀ Passo anterior Próximo passo ▶