IDA* Search Applet Example
Explanation:
This applet is attempting to solve a "slidey-puzzle" type problem where at each step one coloured block may swap places with the empty (black) square, in an attempt to re-arrange the slidey pieces from a random mess [1] to a final image [2].
What can be seen in the applet is the current tree of all the nodes currently visited ( *note these are not all saved in the IDA* algorithm ), and the centered node [highlighted in red] is the current node the algorithm is looking at ( this node and all its direct predecessors to the root node will be in memory of the algorithm ).
To pause the applet click on it, to unpause, click on it again.
The code for the IDA* algorithm part of this applet is included below: (all the source can be found here
private StateNode IDAStar( StateNode sn ){
/* sn is the start node in the problem */
int fLimit; /* current f-Cost Limit */
fLimit = fCost( sn );
while(true){
SolutionLimitPair slp = DFSContour( sn, fLimit );
fLimit = slp.getNewF();
if( slp.getSolution() != null ){
return slp.getSolution();
}
if( fLimit == INFINITY ){
return null;
}
}
}
private SolutionLimitPair DFSContour( StateNode sn, int fLimit ){
/* flimit is current f-Cost limit */
int nextF = INFINITY;
/* nextF is the fCost Limit for the next contour, initially INFINITY */
if( fCost( sn ) > fLimit ){
return new SolutionLimitPair( null, fCost( sn ) ) ;
};
if( goalTest( sn ) ){
return new SolutionLimitPair( sn, fLimit );
}
Vector successors = sn.getSuccessors();
Iterator i = successors.iterator();
while( i.hasNext() ){
StateNode s = (StateNode) i.next();
SolutionLimitPair slp = DFSContour( s, fLimit );
if( slp.getSolution() != null ){
return slp;
}
nextF = min( nextF, slp.getNewF() );
}
return new SolutionLimitPair( null, nextF );
}
Image 1: an initial random "mess" at the start of the slidey puzzle
Image 2: the target for the end of the slidey puzzle