Trouble implementing back-tracking in RBFS

I'm trying to implement an rbfs search algorithm for the 15 puzzle (pseudo code below).

link to the paper where i found the pseudo code: https://www.aaai.org/ocs/index.php/SOCS/SOCS15/paper/viewFile/10911/10632

I do not understand what line 11 is suppose to do. Any clue appreciated

Also, it start with a bound, and in the recursive call, use (min, B, f(n2))

Does this mean that you start with infinity in the first call to rbfs as the bound? And so, the bound can only decrease, and never increase ?

    RBFS(n, B)
1. if n is a goal
2. solution ← n; exit()
3. C ← expand(n)
4. if C is empty, return ∞
5. for each child ni in C
6.   if f(n) < F(n) then F(ni) ← max(F(n), f(ni))
7.   else F(ni) ← f(ni)
8. (n1, n2) ← bestF(C)
9. while (F(n1) ≤ B and F(n1) < ∞)
10.  F(n1) ← RBFS(n1, min(B, F(n2)))
11.  (n1, n2) ← bestF(C)
12. return F(n1)


And here is another pseudo-code implementation

RBFS (node: N, value: F(N), bound: B) IF f(N)>B, return f(N)
IF N is a goal, EXIT algorithm
IF N has no children, RETURN infinity
FOR each child Ni of N,
IF f(N)<F(N) THEN F[i] := MAX(F(N),f(Ni))
ELSE F[i] := f(Ni)
sort Ni and F[i] in increasing order of F[i]
IF only one child, F := infinity
WHILE (F[I] <= B and F[I] < infinity)
F[I] := RBFS(NI, F[I], MIN(B, F))
insert N1 and F[I] in sorted order
return F[I]


What I don't understand here is this : insert N1 and f[I] in sorted order

Does this mean that rbfs does not maintain an open list (since it uses the recursion stack) but it does keep a closed list?

• Any clue appreciated same as line 8, probably – greybeard Dec 10 '16 at 9:58
• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Dec 10 '16 at 14:35