ai.search
Class SearchEngineForIntCostFn.SearchNodeForIntCostFn<S extends SearchStateForIntCostFn>

java.lang.Object
  ai.search.SearchEngineForIntCostFn.SearchNodeForIntCostFn<S>

Direct Known Subclasses:

MAStarSearcherForIntCostFn.MbSearchNode

Enclosing class:

SearchEngineForIntCostFn<S extends SearchStateForIntCostFn>

public static class SearchEngineForIntCostFn.SearchNodeForIntCostFn<S extends SearchStateForIntCostFn>
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 essential 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 int 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.SearchEngineForIntCostFn.SearchNodeForIntCostFn, ai.search.IntCostAction) 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:

IntCostAction, SearchStateForIntCostFn

Field Summary

protected IntCostAction	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 int	pathCost the accumulated path cost leading to this node
protected SearchEngineForIntCostFn.SearchNodeForIntCostFn<S>	predecessor the predecessor node of this node
protected S	state the search state contained in this node

Constructor Summary

SearchEngineForIntCostFn.SearchNodeForIntCostFn(S state, SearchEngineForIntCostFn.SearchNodeForIntCostFn<S> predecessor, IntCostAction action)
This constructor creates a new search node holding the given state.

Method Summary

void	adjustPredecessor(SearchEngineForIntCostFn.SearchNodeForIntCostFn<S> predecessor, IntCostAction 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.
IntCostAction	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.
int	getPathCost() This function returns the total cost of the path leading from the initial state to this node's state.
SearchEngineForIntCostFn.SearchNodeForIntCostFn<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 SearchStateForIntCostFn state

the search state contained in this node

predecessor

protected SearchEngineForIntCostFn.SearchNodeForIntCostFn<S extends SearchStateForIntCostFn> predecessor

the predecessor node of this node

action

protected IntCostAction 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 int pathCost

the accumulated path cost leading to this node

Constructor Detail

SearchEngineForIntCostFn.SearchNodeForIntCostFn

public SearchEngineForIntCostFn.SearchNodeForIntCostFn(S state,
                                                       SearchEngineForIntCostFn.SearchNodeForIntCostFn<S> predecessor,
                                                       IntCostAction 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 SearchStateForIntCostFn contained in this node

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

action - the IntCostAction 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 SearchStateForIntCostFn contained in this node

getPredecessor

public SearchEngineForIntCostFn.SearchNodeForIntCostFn<S> getPredecessor()

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

Returns:

the SearchNodeForIntCostFn that is the predecessor for this node

getAction

public IntCostAction getAction()

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

Returns:

the IntCostAction 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 int 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(SearchEngineForIntCostFn.SearchNodeForIntCostFn<S> predecessor,
                              IntCostAction 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 SearchNodeForIntCostFn that is the new predecessor for this node

action - the IntCostAction 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 SearchStateForIntCostFn

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