algs.model.searchtree
Class AStarSearch
java.lang.Object
algs.model.searchtree.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
Constructor Summary |
AStarSearch(IScore sf)
Prepare an A* search using the given scoring function. |
Method Summary |
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 |
numMoves
public int numMoves
numOpen
public int numOpen
numClosed
public int numClosed
AStarSearch
public AStarSearch(IScore sf)
- Prepare an A* search using the given scoring function.
- Parameters:
sf
- static evaluation function
storageType
public void storageType(int type)
- Determine structure to use for storing CLOSED set.
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 stategoal
- the final board state
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.