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[2] := infinity
WHILE (F[I] <= B and F[I] < infinity)
F[I] := RBFS(NI, F[I], MIN(B, F[2]))
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 $\endgroup$ – greybeard Dec 10 '16 at 9:58