4
$\begingroup$

How does IDA* compare to recursive best first search (RBFS), in terms of (a) the number of nodes expanded, and (b) space complexity?

Both algorithms are intended to be memory-efficient heuristic search algorithms. From my understanding, RBFS just updates the $F(n)$ value for the parent node for which the current execution was stopped in comparison to IDA*, so it avoids redundant computation to a certain extent, but I'm not sure what exactly this means for the number of nodes expanded or its space complexity.

My main motive of this question was to identify all possible reasons that led to development of RBFS (which can be considered as a successor of IDA*).

$\endgroup$
  • $\begingroup$ Thank you for the edit. I'm afraid that asking us to enumerate all differences (or all key differences) might possibly be too broad, so I have edited the question to focus on the specific two metrics you listed. (Identifying all possible reasons is likely too broad, too.) Anyway: What research have you done? Where have you looked, and what information have you found so far? $\endgroup$ – D.W. Aug 20 '15 at 23:31
4
$\begingroup$

Let me please start by succintly summarizing the behaviour of RBFS. For a thorough explanation of the algorithm refer to the original journal paper: Richard Korf. Linear-space best-first search. Artificial Intelligence, 62 (41--78), 1993. In fact, RBFS is much more than "just updating the $F(n)$ value for the parent for which the current execution was stopped". RBFS stores the so-called stored $f$-value of each node $n$ as $F(n)$. An invariant of the algorithm is that the stored $f$-value is the minimum static $f$-value (ie., the usual $f(n)=g(n)+h(n)$) among all leave nodes generated in a tree rooted at $n$. From here, $F(n)\geq f(n)$ for all nodes $n$ given that costs are monotonic. Initially, when a node is expanded for the first time $F(n)=f(n)$. Later on, when backtracking after examining its descendants, its $F$-value (ie., the stored $f$-value) is accordingly updated.

So, if nodes beneath node $n$ are examined, up to what point are they developed? Another parameter used in RBFS is an upper bound $B$ which is initially set to $+\infty$. Do not read $B$ as a global upper bound! Indeed, every time a node is selected for expansion, $B$ is updated to the minimum between the current value of $B$ and the second-best $F$-value. So here you are a second invariant of RBFS: every time a node is selected for expansion, it has an $f$-value which is less or equal than the second best $f$-value in the whole search tree. This is true: first, because $B$ is updated using the second-best $F$-value which amounts to compare it with all the descendants of its siblings; second, the other component used is $B$ itself which was, in turn, computed in the same way by its ancestors. Finally, remember that after every expansion, nodes are sorted in increasing order of their $F$-value.

As a result, RBFS expands nodes in the same order of A*! So far, I do not see it as a successor of IDA*, but instead, as a new member of the large family of best-first search algorithms. Note that in the preceding statement I solely refer to the new expansions. There will be often in between an arbitrarily large number of re-expansions.

For a more didactical explanation of the algorithm refer to the paper Ariel Felner. The Collapse Macro in Best-First Search Algorithms and and Iterative Variant of RBFS. Symposium on Combinatorial Search (SoCS 2015), 28--34. Israel, 2015. During his dissertation Ariel openly said that this is an algorithm poorly understood in general and there was agreement. Conclusion: read this paper also if you are interested in understanding RBFS (I do sincerely doubt that my review suffices for a good understanding of the algorithm).

Regarding your questions:

  1. Note that in the first paragraph I expliclty refered to backtracking ie, RBFS is implemented as a depth-first search algorithm. So far, its memory requirements are $O(bd)$ where $b$ is the branching factor and $d$ is the depth where the solution lies.
  2. Assuming that the expansion of every node is the dominant operation and that it takes the same amount of time in spite of the node been expanded, then the number of expansions directly relates to the time complexity. Korf proved that, in the general case, the time complexity is (as one would expect) $O(bˆd)$ where $b$ is the asymptotic branching factor. Also, the best and worst case analysis are analyzed by Korf in the original paper.

As you mentioned the relationship with IDA* let me also remark that Korf proved that RBFS expands less nodes (in total, considering also re-expansions) than IDA* in the average-case in case of monotonic costs. If costs do not grow monotonically then these algorithms cannot be compared as they traverse entirely different search trees. Since IDA* is known to be asymptotically optimal, then RBFS is asymptotically optimal as well.

Hope this helps,

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.