Mantemos o mesmo exemplo utilizado nas procuras cegas:

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.

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.