RBFS

Pesquisa recursiva melhor-primeiro (Recursive Best-First Search).

Para cada nó n, o algoritmo não guarda o valor da função de avaliação f(n), mas sim o menor valor f(x), sendo x uma folha descendente do nó n.

• Sempre que um nó é expandido, os custos armazenados nos ascendentes são actualizados.

Funciona como pesquisa em profundidade com retrocesso.

• Quando a folha m com menor custo f(m) não é filha do último nó expandido n, então o algoritmo retrocede até ao ascendente comum de m e n.

Exemplo