Algorithm
Development Kit 1.0

algs.model.searchtree.debug
Class AStarSearch

java.lang.Object
  extended by algs.model.searchtree.debug.AStarSearch
All Implemented Interfaces:
ISearch

public class AStarSearch
extends java.lang.Object
implements ISearch

Given an initial state and a target goal state, expand successors, always choosing to expand the node in the OPEN list whose evaluation is the smallest. Ties are broken randomly, except when one of the tied nodes is a goal node.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Field Summary
 int numClosed
           
 int numMoves
           
 int numOpen
           
 
Constructor Summary
AStarSearch(IScore sf)
          Prepare an A* search using the given scoring function.
 
Method Summary
 IDebugSearch debug(IDebugSearch debugger)
          Set the debugger to use when searching (or null to turn off).
 Solution search(INode initial, INode goal)
          Initiate the search for the target state.
 void storageType(int type)
          Determine structure to use for storing CLOSED set.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

numMoves

public int numMoves

numOpen

public int numOpen

numClosed

public int numClosed
Constructor Detail

AStarSearch

public AStarSearch(IScore sf)
Prepare an A* search using the given scoring function.

Parameters:
sf - static evaluation function
Method Detail

storageType

public void storageType(int type)
Determine structure to use for storing CLOSED set.


debug

public IDebugSearch debug(IDebugSearch debugger)
Set the debugger to use when searching (or null to turn off).


search

public Solution search(INode initial,
                       INode goal)
Initiate the search for the target state. Store with each INode object a Transition (Move m, INode prev) so we can retrace steps to the original solution.

Specified by:
search in interface ISearch
Parameters:
initial - the initial board state
goal - the final board state

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.