ai.search
Class SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S extends SearchStateForDoubleCostFn>

java.lang.Object
  ai.search.SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S>

Enclosing class:

SearchEngineForDoubleCostFn<S extends SearchStateForDoubleCostFn>

protected static class SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S extends SearchStateForDoubleCostFn>
extends java.lang.Object

A search node is a data structure created by a search engine to keep track of the portion of the search space explored so far. Each search node contains a single search state and is linked to one other search node, its predecessor in the search tree. Search nodes consist of five essetial components:

• the search state: this is the state that is represented by this search node in the network of nodes representing the search tree explored so far
• the predecessor: this is a link to another search node, namely the node that is the direct predecessor of this node; for the initial node the value of this field will be null
• the action: this is the action that, performed in the state contained in the predecessor node, will result in the state contained in this node; for the initial node the value of this field will be null
• the depth: this integer gives the depth of this node in the search tree which is 0 for the node containing the initial state and the depth of the predecessor node plus 1 for all other nodes
• the path cost: this double represents the accumulated cost of all the actions along the path from the node containing the initial state to this node

Usually a search engine will generate more and more search nodes while it explores a search space. If the search space is a graph, search nodes cannot store all the predecessors to a given node; there is only one field for one predecessor. In this case the predecessor that is kept should usually be the one on the shortest path to this node. Should a search engine later discover a shorter path to a node through a different predecessor than is initially stored with a node, then it can use the function adjustPredecessor(ai.search.SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn, ai.search.DoubleCostAction) to change the predecessor of a node. This function updates all fields of the search node as required.

Finally, for debugging purposes this class also keeps track of the number of instances that have been created, or, how often a constructor of this class has been called. This number can be accessed at any time through the function getInstanceCount().

See Also:

DoubleCostAction, SearchStateForDoubleCostFn

Field Summary

protected DoubleCostAction	action the action that resulted in the state contained in this node
protected int	depth the depth of this node in the search space
protected double	pathCost the accumulated path cost leading to this node
protected SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S>	predecessor the predecessor node of this node
protected S	state the search state contained in this node

Constructor Summary

SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn(S state, SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S> predecessor, DoubleCostAction action)
This constructor creates a new search node holding the given state.

Method Summary

void	adjustPredecessor(SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S> predecessor, DoubleCostAction action) This function can be used to adjust the predecessor for this node.
protected java.lang.Object	clone() This class does not support cloning and an exception will be thrown if this method is called.
boolean	equals(java.lang.Object obj) Two search nodes are considered equal if and only if they are identical.
DoubleCostAction	getAction() This function returns the action that leads from the predecessor to the state contained in this node.
int	getDepth() This function returns the depth of this node in the search tree.
static long	getInstanceCount() This function returns the number of instances that have been created of this class.
double	getPathCost() This function returns the total cost of the path leading from the initial state to this node's state.
SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S>	getPredecessor() This function returns the predecessor node linked to by this node.
S	getState() This function returns the state contained in and represented by this search node.
int	hashCode() This function computes the hash code of this search node which is the hash code of the search state contained in this node.
java.lang.String	toString() This function returns a printable representation of this node which is the sequence number followed by the string printed for the search state contained in this node.

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

state

protected S extends SearchStateForDoubleCostFn state

the search state contained in this node

predecessor

protected SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S extends SearchStateForDoubleCostFn> predecessor

the predecessor node of this node

action

protected DoubleCostAction action

the action that resulted in the state contained in this node

depth

protected int depth

the depth of this node in the search space

pathCost

protected double pathCost

the accumulated path cost leading to this node

Constructor Detail

SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn

public SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn(S state,
                                                             SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S> predecessor,
                                                             DoubleCostAction action)

This constructor creates a new search node holding the given state. Predecessor node and action are set to the given values. The given state must not be null, but predecessor and action may be null for the initial state. Depth and path cost to this node are automatically computed from the predecessor's corresponding values.

Parameters:

state - the SearchStateForDoubleCostFn contained in this node

predecessor - the SearchNodeForDoubleCostFn that is the direct predecessor for this node (null for the initial state)

action - the DoubleCostAction leading from the predecessor to this node's search state (null for the initial state)

Method Detail

clone

protected java.lang.Object clone()
                          throws java.lang.CloneNotSupportedException

This class does not support cloning and an exception will be thrown if this method is called.

Overrides:

clone in class java.lang.Object

Returns:

nothing

Throws:

java.lang.CloneNotSupportedException - will be thrown

getState

public S getState()

This function returns the state contained in and represented by this search node.

Returns:

the SearchStateForDoubleCostFn contained in this node

getPredecessor

public SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S> getPredecessor()

This function returns the predecessor node linked to by this node.

Returns:

the SearchNodeForDoubleCostFn that is the predecessor for this node

getAction

public DoubleCostAction getAction()

This function returns the action that leads from the predecessor to the state contained in this node.

Returns:

the DoubleCostAction that leads from the predecessor to this state

getDepth

public int getDepth()

This function returns the depth of this node in the search tree.

Returns:

the depth of this node

getPathCost

public double getPathCost()

This function returns the total cost of the path leading from the initial state to this node's state.

Returns:

the total cost of the path leading to this node

adjustPredecessor

public void adjustPredecessor(SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S> predecessor,
                              DoubleCostAction action)

This function can be used to adjust the predecessor for this node. This can be useful when a newly generated state turns out to be identical to the previously generated state contained in this node, only the path to the new state may be shorter. The depth of the node as well as the path cost are automatically recomputed.

Parameters:

predecessor - the SearchNodeForDoubleCostFn that is the new predecessor for this node

action - the DoubleCostAction leading from the new predecessor to this state

equals

public boolean equals(java.lang.Object obj)

Two search nodes are considered equal if and only if they are identical. Technically, this is the case if (this == obj).

Overrides:

equals in class java.lang.Object

Parameters:

obj - the Object this is compared to

Returns:

true if and only if the given Object is the same as this one

hashCode

public int hashCode()

This function computes the hash code of this search node which is the hash code of the search state contained in this node.

Overrides:

hashCode in class java.lang.Object

Returns:

the hash code of the contained SearchStateForDoubleCostFn

toString

public java.lang.String toString()

This function returns a printable representation of this node which is the sequence number followed by the string printed for the search state contained in this node.

Overrides:

toString in class java.lang.Object

Returns:

the id and String for the state contained in this node

getInstanceCount

public static long getInstanceCount()

This function returns the number of instances that have been created of this class. It does not deduct instances that have been removed from memory through garbage collection.

Returns:

the instance count for this class