Package search

A generic implementation of several of the graph search algorithms discussed in Russell and Norvig. The heart of this implementation is class GraphSearcher, which implements the GraphSearch algorithm of Russell and Norvig in its general form. The specific behaviors of the frontier, the explored set, checking for goal nodes, etc. are provided through the generic type arguments, and through the behaviors passed as constructor arguments. However the GraphSearcher class is a bit abstract, and so there are specialized versions of it for common algorithms and purposes.

• The AStarSearcher class fixes the operation of the search frontier for the A* algorithm.

  This class has two further specializations: AStarSearcher.SimpleNodes with minimal search tree nodes containing only the underlying state and its cost, and AStarSearcher.PathNodes with nodes also each containing a backlink to its parent.

• The BreadthFirstSearcher class fixes the operation of the search frontier for the breadth-first search algorithm.

Interface Summary

Interface	Description
ExploredSet<Node>	Methods required to track the nodes which we have already either added to the frontier, or removed from the frontier for exploration.
FrontierCheckingStructure<Node>	Subclass of frontier representations which support checking membership of a node in the frontier.
FrontierStructure<Node>	Methods required of a representation of a search tree frontier.
GoalChecker<Node>	Methods required of objects which check that a tree node corresponds to a search goal.
KnowsOwnCost	Additional interface implemented by search tree nodes which are aware of their own cost.
SearchTreeNode<Self extends SearchTreeNode<Self,State>,State>	Methods required of a search tree node.
SearchTreePathNode<This extends SearchTreePathNode<This,S>,S>	Type of search tree nodes which form a path of nodes, each expanded from its parent which is next in the path.

Class Summary

Class	Description
AStarFrontierSearcher<State,Node extends SearchTreeNode<Node,State> & KnowsOwnCost,Frontier extends Frontiers.PriorityQueue<Node>>	Extension of PriorityQueueSearcher with A*'s prioritization formula f(n) = g(n)+h(n), still leaving the exact structure of the frontier as a configurable option.
AStarFrontierSearcher.PathNodes<State,Frontier extends Frontiers.PriorityQueue<Nodes.SimpleTreePathCostNode<State>>>	A specialization of AStarFrontierSearcher to use a minimal implementation of hierarchical search tree nodes (with a state, accumulated cost, and pointer to a parent tree node), with the frontier implementation still exposed as a type parameter.
AStarFrontierSearcher.SimpleNodes<State,Frontier extends Frontiers.PriorityQueue<Nodes.SimpleTreeCostNode<State>>>	A specialization of AStarFrontierSearcher to use a minimal implementation of unrelated search tree nodes (with a state and accumulated cost only), with the frontier implementation still exposed as a type parameter.
AStarSearcher<State,Node extends SearchTreeNode<Node,State> & KnowsOwnCost>	Extension of AStarFrontierSearcher to fix the frontier structure with a minimal priority queue implementation.
AStarSearcher.PathNodes<State>	A specialization of AStarSearcher to use a minimal implementation of hierarchical search tree nodes (with a state, accumulated cost, and pointer to a parent tree node), with the frontier implementation still exposed as a type parameter.
AStarSearcher.SimpleNodes<State>	A specialization of AStarSearcher to use a minimal implementation of unrelated search tree nodes (with a state and accumulated cost only), with the frontier implementation still exposed as a type parameter.
BreadthFirstSearcher<State,Node extends SearchTreeNode<Node,State>>	Specialization of the generic GraphSearcher to use a queue for its frontier, and thus erform breadth-first search.
ExploredSets	Three sample implementations of ways to track nodes which we have already either added to the frontier, or removed from the frontier for exploration.
Frontiers	Standard implementations of structures representing a frontier.
Frontiers.DebuggablePriorityQueue<S,N extends SearchTreeNode<N,S>>
Frontiers.DebuggingFrontier<Node>	Abstract class adding debugging hooks to the basic frontier.
Frontiers.PriorityQueue<Node>	A frontier as a priority queue, for e.g.
Frontiers.Queue<Node>	A queue as a priority queue, for e.g.
Frontiers.StateKeyedPriorityQueue<S,N extends SearchTreeNode<N,S>>
GoalCheckers	Sample implementations of checkers that a tree node corresponds to a search goal.
GraphSearcher<State,Node extends SearchTreeNode<Node,State>,Frontier extends FrontierStructure<Node>>	Topmost class encapsulating graph search.
Nodes	Sample implementations of search tree nodes.
Nodes.CostAndStep<S>	Helper class for search tree node expansion bundling a node and its associated cost.
Nodes.SimpleTreeCostNode<S>	Implementation of search tree nodes with a notion of cost.
Nodes.SimpleTreeNode<S>	Simple implementation of search tree nodes, expecting that the Exp type argument of the Nodes.SimpleCoreTreeNode will be just the search state type.
Nodes.SimpleTreePathCostNode<S>	Implementation of search tree nodes which have a notion of cost, and which contain links to their parent node.
Nodes.SimpleTreePathNode<S>	Implementation of search tree nodes which retain a link to their parent.
PriorityQueueSearcher<State,Node extends SearchTreeNode<Node,State>,Frontier extends Frontiers.PriorityQueue<Node>>	Specialization of the generic GraphSearcher to use a priority queue structure for its frontier.

Exception Summary

Exception	Description
FrontierEmptyException	Thrown when a frontier structure is empty.
SearchFailureException	Thrown from search algorithms when they find no solution.