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, A-star

Aumentamos agora o exemplo, com mais 3 movimentos, de forma a obter um problema mais complicado:

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
cima
1 2  
4 6 3
7 5 8
esquerda
1   2
4 6 3
7 5 8
baixo
1 6 2
4   3
7 5 8

A procura A* (AStar) vai expandir primeiro os estados mais promissores antes dos menos promissores, independentemente do nível em que estão. Para cada estado contará não só o valor da função heurística, como no método melhor primeiro, mas também o custo desde o estado inicial, de forma a ter uma estimativa global. Ao contrário do melhor primeiro, o AStar vai escolher de entre todos os estados gerados mas não expandidos o melhor (e não apenas entre os últimos que tivessem o mesmo pai), daí a necessidade de incorporar o custo, enquanto que no melhor primeiro não é necessário no caso de se assumir o custo unitário de passagem de um estado para ou outro.

Pode-se fazer um paralelo deste algoritmo com a procura em largura, mas em vez de expandir o estado mais antigo, vai expandir o estado mais promissor, de entre todos os disponíveis. De forma a manter o nome das colunas entre algoritmos informados, o nível é utilizado para o custo, pelo que AStar vai expandir o que tiver menor heurística+nível.

Geração

Estado

Heurística

Nível

Pai

Expansão
1
1
6
2 
4
  3
7
5
8
6
0
0 1
2
1
  2 
4
6
3
7
5
8
5
1
1 2
3
1
6
2 
  4
3
7
5
8
7
1
1  
4 
1
6
2 
4
3
 
7
5
8
7
1
1  
5 
1
6
2 
4
5
3
7
  8
5
1
1 3
6 
  1
2 
4
6
3
7
5
8
6
2
2  
7 
1
2 
 
4
6
3
7
5
8
4
2
2 4
8 
1
6
2 
4
5
3
  7
8
6
2
5  
9 
1
6
2 
4
5
3
7
8
 
4
2
5 5
10 
1
2 
3
4
6
 
7
5
8
3
3
7 6
11
1
6
2 
4
5
 
7
8
3
5
3
9  
12
1
2 
3
4
  6
7
5
8
2
4
10 7
13
1
2 
3
4
6
8
7
5
 
4
4
10  
14
1
  3
4
2 
6
7
5
8
3
5
12  
15
1
2 
3
  4
6
7
5
8
3
5
12  
16
1
2 
3
4
5
6
7
  8
1
5
12 8
17
1
2 
3
4
5
6
  7
8
2
6
16  
18
1
2 
3
4
5
6
7
8
 
0 Solução!
6
16  

Ficheiro de Excel, passo a passo:

Neste exemplo maior, o AStar obtém a solução com 18 gerações/avaliações e 8 expansões, considerando que o teste de estado objetivo é realizado na função heurística ao avaliar o estado.

É nítido neste exemplo que houve expansões que não levaram a nada, como o estado 5, e eventualmente um ser humano não a escolheria, no entanto a informação heurística não permitiu qualquer distinção entre este estado e o estado 2, por exemplo. Com uma heurística mais evoluída poder-se-ia concluir que esse estado nunca poderia chegar à solução objetivo no número de movimentos igual à distância de Manhattan, e aumentar o valor da função heurística, mas pode bem acontecer que o benefício não compense o tempo gasto a calcular uma heurística mais complexa. Repare-se que só houve 2 expansões que eram desnecessárias, em 8 expansões realizadas, portanto a heurística para um problema desta dificuldade é bastante adequada.

⚡ Ação: Sem resolver novamente o problema, utilizando os estados gerados pelo AStar, indique qual a ordem dos estados que o algoritmo melhor primeiro iria expandir, e parando quando o algoritmo melhor primeiro for expandir um estado que o AStar não expandiu (incluindo esse estado). Em caso de empate, o melhor primeiro escolhe o último estado gerado, enquanto que o AStar escolhe o primeiro.

Resposta: 1,5,9,11

O melhor primeiro iria para um caminho que não leva a lado nenhum, e poderia mesmo entrar em ciclo. Para ultrapassar este problema, tem que se colocar um limite de profundidade, e/ou não gerar estados já gerados.

◀ Passo anterior Próximo passo ▶