Package search

Class GraphSearcher<State,​Node extends SearchTreeNode<Node,​State>,​Frontier extends FrontierStructure<Node>>

java.lang.Object
search.GraphSearcher<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:
BreadthFirstSearcher, PriorityQueueSearcher
public class GraphSearcher<State,​Node extends SearchTreeNode<Node,​State>,​Frontier extends FrontierStructure<Node>>
extends Object
Topmost class encapsulating graph search. The search method implements the Graph-Search algorithm of Russell and Norvig (2nd ed., Figure 3.7, p. 77), with customizable behavior provided as constructor arguments.

  • Constructor Details

    • GraphSearcher

      public GraphSearcher​(Supplier<GoalChecker<Node>> goalCheckerFactory, Supplier<? extends Frontier> frontierFactory, Function<Frontier,​ExploredSet<Node>> exploredSetFactory, Function<State,​Node> initializer)
      The constructor parameters encode the particlar behavior which distinguishes different search algorithms.
      Parameters:
      goalCheckerFactory - The get method of this object must return a predicate on tree nodes used to tell if they are goal nodes.
      frontierFactory - The get method of this object returns a new, empty Frontier instance.
      exploredSetFactory - Structure used to manage adding elements to the frontier, in particular for avoiing duplication.
      initializer - Creates an initial tree node from a search space element.

  • Method Details

    • search

      public Node search​(State initial) throws SearchFailureException
      Executes a search beginning from a particular search space element.
      Parameters:
      initial - The starting element
      Returns:
      The tree node corresponding to a goal element of the search space which is returned from this search
      Throws:
      SearchFailureException - When the search does not lead to a goal state

    • solvable

      public boolean solvable​(State initial)
      Convenience method for when we care only about whether a solution exists, and not what it is.
      Parameters:
      initial - The starting element
      Returns:
      true if search(State) would return a final node with the same initial state, otherwise false

    • debugInitialNode

      public void debugInitialNode​(Node node)
      This method prints a debugging message about the initial tree node of a search.
      Parameters:
      node - The tree node in question.

    • debugFrontierRemoval

      public void debugFrontierRemoval​(Node node)
      This method prints a debugging message when a tree node is removed from the frontier for expansion.
      Parameters:
      node - The tree node in question.

    • debugExpansion

      public void debugExpansion​(Node node)
      This method prints a debugging message when a tree node is generated from another node extracted from the frontier for expansion.
      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.
      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 debugExpansion(Node) method.

    • debugFrontierNonaddition

      public void debugFrontierNonaddition​(Node node)
      This method prints a debugging message when a tree node is not added to the frontier.
      Parameters:
      node - The tree node in question

    • debugFrontierExhausted

      public void debugFrontierExhausted​(GoalChecker<Node> checker)
      This method prints a debugging message when the frontier is emptied (which is usually an error situation).
      Parameters:
      checker - The GoalChecker instance used in this search. This instance may be storing expanded nodes (to avoid revisiting them), and so may have additional information we wish to view. However the default implementation of this method in this parent class does not use this argument.

    • debugGoalFound

      public void debugGoalFound​(Node node)

    • debugFrontier

      public void debugFrontier​(Frontier f)
      Print debugging information about the frontier. By default, invokes debugDisplayFrontier.

    • getLastAddedToFrontier

      public long getLastAddedToFrontier()
      Returns the number of frontier nodes which were added to the last search.
      Returns:
      -1 if no search has been executed

    • getLastNotAddedToFrontier

      public long getLastNotAddedToFrontier()
      Returns the number of frontier nodes which were generated from an expanded node, but not added to the last search.
      Returns:
      -1 if no search has been executed

    • getLastExpandedFromFrontier

      public long getLastExpandedFromFrontier()
      Returns the number of frontier nodes which were expanded in the last search.
      Returns:
      -1 if no search has been executed

    • getLastUnexpandedInFrontier

      public long getLastUnexpandedInFrontier()
      Returns the number of frontier nodes which were expanded in the last search.
      Returns:
      -1 if no search has been executed

    • setDebug

      public void setDebug​(boolean debug)
      Controls whether execution of the search(State) method should print debugging messages.

    • getDebug

      public boolean getDebug()
      Returns whether execution of the search(State) method is printing debugging messages.