The recursive best-first search (RBFS) algorithm is a simple recursive algorithm that attempts to mimic the operation of A-star search (i.e., the standard best-first search with an evaluation function that adds up the path cost and the heuristic), but using only linear space (instead of showing an exponential space complexity). The structure of RBFS is similar to that of recursive depth-first search (a tree-search version), but rather than continuing indefinitely down the current path, it uses an evaluation limit to keep track of the best alternative path available from any ancestor of the current node, see Figure 1.

Figure 1. RBFS applied on the graphical map of Germany, from Frankfurt to München.

RBFS is robust and optimal (if the heuristic is admissible), but it still suffers from excessive node regeneration due to its low memory profile, which entails a long processing time. Given enough time, though, it can solve problems that A-star cannot solve because it runs out of memory.

Figure 2. Recursive best-first search algorithm.

-- Recursive best-first search algorithm.
--
-- PRE:
-- problem - cost-weighted adjacency matrix (table).
-- start - starting node index (number).
-- finish - finishing node index (number).
-- heuristic - must be a heuristic at the node level (table).
--
-- POST:
-- solution - solution path (table). State set to zero if failure.
--
-- In this implementation, cost is a vector:
-- {path_cost, heuristic_cost}.

function recursive_best_first_search(problem, start, finish,
  heuristic)
  -- inits
  local node = {}
  node.state = start
  node.parent = {}
  node.cost = {0, heuristic[start]}
  return rbfs(problem, node, finish, heuristic, math.huge)
end

function rbfs(problem, node, finish, heuristic, flimit)
  if (node.state == finish) then
    return node
  else
    local successors = {}
    -- for each action in problem given state...
    for i = 1, #problem do
      if (problem[node.state][i] > 0) then
        if (i ~= node.state) then
          local child = {state = i}
          local path = {}
          for j = 1, #node.parent do
            table.insert(path, node.parent[j])
          end
          table.insert(path, node.state)
          child.parent = path
          child.cost = {node.cost[1] + problem[node.state][i],
            heuristic[i]}
          table.insert(successors, child)
        end
      end
    end
    if (#successors == 0) then
      return {state = 0}
    end
    while (true) do
      -- 1st and 2nd lowest fval in successors
      local best = successors[1]
      local alternative = best
      if (#successors > 1) then
        alternative = successors[2]
        if ((best.cost[1] + best.cost[2]) >
          (alternative.cost[1] + alternative.cost[2])) then
          best, alternative = alternative, best
        end
        for i = 3, #successors do
          -- check best
          if ((successors[i].cost[1] + successors[i].cost[2]) <
            (best.cost[1] + best.cost[2])) then
            alternative = best
            best = successors[i]
          elseif ((successors[i].cost[1] + successors[i].cost[2]) <
            (alternative.cost[1] + alternative.cost[2])) then
            alternative = successors[i]
          end
        end
      end
      local bestf = best.cost[1] + best.cost[2]
      local alternativef = alternative.cost[1] + alternative.cost[2]
      local result
      if (bestf < flimit) then
        result = rbfs(problem, best, finish, heuristic,
          math.min(flimit, alternativef))
      else
        node.cost[1] = best.cost[1]
        node.cost[2] = best.cost[2]
        return {state = 0}
      end
      if (result.state ~= 0) then
        return result
      end
    end
  end
end

Regarding its implementation, see Figure 2, the RBFS algorithm depicted in AIMA is somewhat puzzling and it does not take into account a scenario with one single successor. Note how the former code specifically tackles these issues so that the final algorithm behaves as expected.

With RBFS you made it to the end of chapter 3. Over the course of the former posts, you have reviewed some of the most practical search methods, which are able to solve many types of problems in AI like puzzles, robot navigation, or the famous travelling salesman problem. In addition, the language processing field is also in need of such search algorithms to solve problems in speech recognition, parsing, and machine translation. All these fancy applications will be targeted in due time. In the following posts, the idea of “classical” search you have seen so far will be generalised to cover a broader scope of state-spaces. Stay tuned!