Busca Heurística Limitada Pela Memória: RBFS

Busca Heurística Limitada Pela Memória:
RBFS ( Recursive Best First Search)
Marcos Rodovalho1
Universidade Federal de Uberlândia1 [e-mail] Abstract— The Best First search is a general search algorithm that always expands the node in the direction that has the lowest heuristic, believing a quick drive to the goal, however, is limited by its exponential memory requirement. This problem can be solved using a recursive method. The algorithm Recursive Best First Search (RBFS) is a linear-space search algorithm, it is a simple recursive algorithm that makes the search for the best choice using only a linear-space, he always expands its nodes in best first order, independent of the cost function f (g), expanding more nodes with less heuristic f (h). In general, RBFS reduces the space complexity of best-first search from exponential to linear.
Keywords – recursive best-first search, heuristic search, limited memory, RBFS, linear-space, javaff, search algorithm .
I. Introdução
A busca recursiva pelo melhor (RBFS) é um algoritmo de espaço linear que expande os nós na ordem do primeiro melhor, de acordo com a função heurística f(h). Sua estrutura é semelhante à de uma busca recursiva em profundidade, porém, ao invés do algoritmo ir expandindo os nós em profundidade de uma forma indefinida, ele vai controlando o valor da função f(h) guardando o melhor caminho alternativo. Se a heurística do nó atual for maior (ou pior), do que a do caminho alternativo, ele volta e vai atualizando a função f(h) para armazenar o próximo caminho alternativo.
Essa técnica de busca possui duas versões do algoritmo: a primeira versão, que é a forma simples do algoritmo, simples busca recursiva pelo melhor (SRBFS), e a segunda versão, que é a forma completa do algoritmo (RBFS). Esses algoritmos apareceram pela primeira vez em [Korf 1991a], seus principais resultados foram apresentados em [Korf 1991b] e sua versão completa foi apresentada em [Korf 1991c], incluindo as