Package search

Class AStarFrontierSearcher<State,Node extends SearchTreeNode<Node,State> & KnowsOwnCost,Frontier extends Frontiers.PriorityQueue<Node>>

java.lang.Object

search.GraphSearcher<State,Node,Frontier>

search.PriorityQueueSearcher<State,Node,Frontier>

search.AStarFrontierSearcher<State,Node,Frontier>

Type Parameters:

State - Type representing elements of the search space.

Node - Type representing nodes in the search tree. Each node typically contains a reference to a State element.

Frontier - Type representing the (entire) search frontier (open set).

Direct Known Subclasses:

AStarFrontierSearcher.PathNodes, AStarFrontierSearcher.SimpleNodes, AStarSearcher

public class AStarFrontierSearcher<State,Node extends SearchTreeNode<Node,State> & KnowsOwnCost,Frontier extends Frontiers.PriorityQueue<Node>>
extends PriorityQueueSearcher<State,Node,Frontier>

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.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	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.
static class	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.

Constructor Summary

Constructors

Constructor	Description
AStarFrontierSearcher(Predicate<Node> goalTest, Function<Node,Double> heuristic, Function<Comparator<Node>,Supplier<? extends Frontier>> frontierMetafactory, Function<Frontier,ExploredSet<Node>> exploredSetFactory, Function<State,Node> initializer)	Primary constructor for this class; other constructor relay to this one.
AStarFrontierSearcher(Predicate<Node> goalTest, Function<Node,Double> heuristic, Function<Comparator<Node>,Supplier<? extends Frontier>> frontierMetafactory, Function<State,Node> initializer)	Constructor for this class which does not maintain an explored set.

Method Summary

Modifier and Type	Method	Description
void	debugFrontierAddition(Node node)	This method prints a debugging message when a tree node is added to the frontier.
void	debugFrontierRemoval(Node node)	This method prints a debugging message when a tree node is removed from the frontier for expansion.

Methods inherited from class search.GraphSearcher

debugExpansion, debugFrontier, debugFrontierExhausted, debugFrontierNonaddition, debugGoalFound, debugInitialNode, getDebug, getLastAddedToFrontier, getLastExpandedFromFrontier, getLastNotAddedToFrontier, getLastUnexpandedInFrontier, search, setDebug, solvable

Methods inherited from class java.lang.Object

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

Constructor Details

AStarFrontierSearcher

public AStarFrontierSearcher(Predicate<Node> goalTest, Function<Node,Double> heuristic, Function<Comparator<Node>,Supplier<? extends Frontier>> frontierMetafactory, Function<State,Node> initializer)

Constructor for this class which does not maintain an explored set.

Parameters:

goalTest - A boolean-returning function checking whether a tree node contains a goal state.

heuristic - Heuristic function for this search application.

frontierMetafactory - This function maps a Comparator for tree nodes to a Supplier of new, empty Frontier instances.

initializer - Creates an initial tree node from a search space element. Passed as-is to the primary constructor for this class, and thence to the parent constructor.

AStarFrontierSearcher

public AStarFrontierSearcher(Predicate<Node> goalTest, Function<Node,Double> heuristic, Function<Comparator<Node>,Supplier<? extends Frontier>> frontierMetafactory, Function<Frontier,ExploredSet<Node>> exploredSetFactory, Function<State,Node> initializer)

Primary constructor for this class; other constructor relay to this one. This constructor encodes A*'s f(n) = g(n)+h(n) formula into the Comparator behind the underlying priority queue.

Parameters:

goalTest - A boolean-returning function checking whether a tree node contains a goal state.

heuristic - Heuristic function for this search application.

frontierMetafactory - This function maps a Comparator for tree nodes to a Supplier of new, empty Frontier instances.

exploredSetFactory - Structure used to manage adding elements to the frontier, in particular for avoiing duplication. Passed as-is to the primary constructor for this class, and thence to the parent constructor.

initializer - Creates an initial tree node from a search space element. Passed as-is to the primary constructor for this class, and thence to the parent constructor.

Method Details

debugFrontierRemoval

public void debugFrontierRemoval(Node node)

This method prints a debugging message when a tree node is removed from the frontier for expansion.

Overrides:

debugFrontierRemoval in class GraphSearcher<State,Node extends SearchTreeNode<Node,State> & KnowsOwnCost,Frontier extends Frontiers.PriorityQueue<Node>>

Parameters:

node - The tree node in question.

debugFrontierAddition

public void debugFrontierAddition(Node node)

This method prints a debugging message when a tree node is added to the frontier.

Overrides:

debugFrontierAddition in class GraphSearcher<State,Node extends SearchTreeNode<Node,State> & KnowsOwnCost,Frontier extends Frontiers.PriorityQueue<Node>>

Parameters:

node - The tree node in question. The default message printed in the version of this method defined in this class does not actually use this argument, since the tree node is already printed in the default version of the GraphSearcher.debugExpansion(Node) method.