Busca Heurística Limitada Pela Memória:
RBFS ( Recursive Best First Search)
Marcos Rodovalho1
Universidade Federal de Uberlândia1 marcos.rodovalho91@gmail.com 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