Solving 8 puzzle problem using recursive best first search ( RBFS)

Recursive best first first search combines best first search and recursive depth first search. When the children of a node are generated they are arranged in the order by an heuristic value. The best child is selected for expansion. If the best child has a value that’s greater than the parent then the child nodes are not selected for expansion and the heuristic value of best child is assigned to its parent. Again the best first search is executed at the parent level.

Recursive best first search remembers the last node that fail to give result and it will be re expanded whenever it’s necessary. The RBFS algorithm uses less memory , but generates the same nodes repeatedly.

Here is the algorithm for recursive best first search

If you want to read more about RBFS refer here

Best-first Search for Bounded-depth Trees – blfs-socs11.pdf unh.edu
Recursive Best-First Search Example gettysburg.edu
informed-search-II.pdf upenn.edu
Here is the PHP implementation of recursive best first search to solve 8 puzzle problem

Baca Juga  Perbandingan SQL dan NoSQL