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

function RBFS (problem,node,f-limit) returns sol & f-cost
if GOAL-TEST (problem, STATE (node)) then return node
succ= EXPAND (node, problem)
if succ is empty then return failure
for-each s in succ do
f [s]= max (g(s)+ h(s), f[node])
repeat
best= the lowest f-value node in succ
if f[best]> f-limit then return failure, f[best]
alternative= the second-lowest f-value among succ
result,f[best]= RBFS (problem, best, min(f-limit,altern
if result<> failure then return result

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

<?php

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

include('puzzle.php');

class PuzzleHeap extends SplMinHeap {

    public function compare(Puzzle $a, Puzzle $b) {
        return ($b->path_cost + $b->val) - ($a->val + $a->path_cost);
    }

}

function recursive_best_first_search(Puzzle $current_state, $bound, &$steps) {
    if ($current_state->goalTest() == TRUE) {
        return $current_state;
    }
    $steps++;

    $nodeQue = new PuzzleHeap();

    $moves = $current_state->possibleMoves();
    foreach ($moves as $move) {
        $nodeQue->insert($move);
    }
    $alt = 1000;
    if ($nodeQue->count() == 0) {
        return $alt;
    }

    $nodeQue->rewind();
    while ($nodeQue->valid()) {

        $best = $nodeQue->extract();
        if (($best->val + $best->path_cost) > $bound) {
            return ($best->val + $best->path_cost);
        }
        if ($nodeQue->count() >= 1) {
            $alt = $nodeQue->current()->val + $nodeQue->current()->path_cost;
        } else {
            $alt = 1000;
        }
        $min = $bound;
        if ($alt < $bound) {
            $min = $alt;
        }
        $retval = recursive_best_first_search($best, $min, $steps);
        if (is_int($retval)) {
            $best->val = $retval - $best->path_cost;
            $nodeQue->insert($best);
        } else {
            return $retval;
        }
    }
}

$start_time = microtime(true);

$initial_pos = array(
    array(4, 1, 2),
    array(8, 5, 7),
    array(0, 3, 6)
);

$goal_pos = array(
    array(0, 1, 2),
    array(3, 4, 5),
    array(6, 7, 8)
);

$initial_state = new Puzzle();
$initial_state->setInitial($initial_pos);
$initial_state->setGoalpos($goal_pos);

$steps = 1;
$result = recursive_best_first_search($initial_state, 1000, $steps);
if ($result != FALSE) {
    print "Solution found by evaluating $steps nodes <br>";
    $result->printSequence();
} else {
    print "Solution not found at $max_depth , evaluating $steps nodes";
}
print ("<br>Maximum Memory used " . memory_get_peak_usage());
print ("<br>Current Memory used" . memory_get_usage());
$end_time = microtime(true);
$time_exec = $end_time - $start_time;
print("<br>Execution time used =" . $time_exec);