cc.mallet.util.search
Class AStar

java.lang.Object
  cc.mallet.util.search.AStar

All Implemented Interfaces:

java.util.Iterator<AStarNode>

public class AStar
extends java.lang.Object
implements java.util.Iterator<AStarNode>

Created by IntelliJ IDEA. User: pereira Date: Jun 19, 2005 Time: 1:38:28 PM A* search iterator over an underlying graph. The iterator returns search nodes for final states in order of increasing cost to reach them from the initial states, assuming that the heuristic cost-to-completion function is admissible. This very simple version assumes that we may revisit already visited states, because we want to generate all paths to final states in order of increasing cost.

Constructor Summary

AStar(AStarState[] initial, int expectedSize)
Create an A* search iterator starting from the given initial states.

Method Summary

boolean	hasNext()
AStarNode	next()
AStarNode	nextAnswer() Get the next search node for a final state.
void	remove()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AStar

public AStar(AStarState[] initial,
             int expectedSize)

Create an A* search iterator starting from the given initial states. The expected size parameter gives the size of the search queue. If this is too small, growing the queue costs more time. If this is too big, space is wasted.

Parameters:

initial - the set of initial states

expectedSize - the expected size of the search queue

Method Detail

hasNext

public boolean hasNext()

Specified by:

hasNext in interface java.util.Iterator<AStarNode>

next

public AStarNode next()

Specified by:

next in interface java.util.Iterator<AStarNode>

nextAnswer

public AStarNode nextAnswer()

Get the next search node for a final state.

Returns:

a final search node

remove

public void remove()

Specified by:

remove in interface java.util.Iterator<AStarNode>