Crowdly
Add to Chrome
Puzzle8, procura melhor primeiro Mantemos o mesmo exemplo utilizado nas procu...
✅ The verified answer to this question is available below. Our community-reviewed solutions help you understand the material better.
Puzzle8, procura melhor primeiro
Mantemos o mesmo exemplo utilizado nas procuras cegas:
| esquerda
|
| cima
|
| direita
|
|
A procura melhor primeiro vai expandir primeiro os estados gerados há menos tempo, antes dos restantes, mas de entre os estados com o mesmo pai, expande primeiro os que tiverem um valor heurístico menor, dado serem esses os mais promissores. Portanto tem que se calcular o valor da função heurística, que devolverá uma estimativa para a distância até um estado objetivo. Para este problema podemos ter a distância de Manhattan, que é a distância na horizontal e vertical de cada número até à sua posição final.
Este algoritmo pode ser basicamente idêntico à procura em profundidade cega, mas alterando a ordem de expansão, o que leva a que possa ser também colocado um limite. Neste caso vamos utilizar o limite 10, significando que não deve explorar soluções com mais de 10 passos.
Geração | Estado | Heurística | Nível | Pai | Expansão | |||||||||
| 1
|
| 3
| 10
| 0
| 1
| |||||||||
| 2
|
| 4
| 9
| 1
|
| |||||||||
| 3
|
| 2
| 9
| 1
| 2
| |||||||||
| 4
|
| 4
| 9
| 1
|
| |||||||||
| 5
|
| 3
| 8
| 3
|
| |||||||||
| 6
|
| 3
| 8
| 3
|
| |||||||||
| 7
|
| 1
| 8
| 3
| 3
| |||||||||
| 8
|
| 2
| 7
| 7
|
| |||||||||
| 9
|
| 0 Solução!
| 7
| 7
|
|
Ficheiro de Excel, passo a passo:
Considerando que o teste de estado objetivo se faz na função heurística, já que é suposto devolver 0 no caso de ser um estado objetivo, a procura leva 3 expansões, tendo sido gerados e avaliados 9 estados.
Após a expansão do estado 1, foram gerados e avaliados 3 estados, dos quais optou-se por expandir o estado 3 já que desses é o que possui o menor valor heurístico, portanto poderá estar mais perto de um estado objetivo. Resultante da expansão do estado 3, foram gerados 3 estados, tendo sido nesse caso o estado 7 o de menor valor, e assim por diante. Não foi preciso voltar atrás neste exemplo; o algoritmo foi direto à solução a três passos. Se por exemplo tivesse atingido o limite, teria de voltar para trás, escolhendo sempre para expandir, de entre os últimos estados gerados mas não expandidos com o mesmo pai (e no mesmo nível), o que tiver menor valor heurístico.
Se a heurística for muito boa, este algoritmo segue a direito sem problemas. No entanto, por vezes a utilização de uma boa heurística tem custos computacionais incomportáveis. Mais: nas procuras informadas, é normalmente mais pesada a função heurística, sendo portanto mais relevante o número de avaliações, podendo no entanto trocar com a geração de sucessores, no caso de se optar por uma heurística leve.
Ação: Considere que o estado de partida era o estado 4 da resolução acima. Execute este algoritmo e indique o número dos estados expandidos por ordem de expansão, separados por vírgulas sem espaços.