public SearchNode search ( QueueSearchState < O , T > initSearch , Collection < T > startStates , int maxSteps , int searchSteps ) throws SearchNotExhaustiveException { // Initialize the queue with the start states set up in search nodes if this has not already been done. // This will only be done on the first call to this method, as enqueueStartStates sets a flag when it is // done. Subsequent searches continue from where the previous search left off. Have to call reset on // the search method to really start the search again from the start states. Queue < SearchNode < O , T > > queue = initSearch . enqueueStartStates ( startStates ) ; // Get the goal predicate configured as part of the enqueueing start states process. UnaryPredicate < T > goalPredicate = initSearch . getGoalPredicate ( ) ; // Keep running until the queue becomes empty or a goal state is found. while ( ! queue . isEmpty ( ) ) { // Extract or peek at the head element from the queue. SearchNode < O , T > headNode = peekAtHead ? queue . peek ( ) : queue . remove ( ) ; // Expand the successors into the queue whether the current node is a goal state or not. // This prepares the queue for subsequent searches, ensuring that goal states do not block // subsequent goal states that exist beyond them. if ( ! headNode . isExpanded ( ) ) { headNode . expandSuccessors ( queue , reverseEnqueue ) ; } // Get the node to be goal checked, either the head node or the new top of queue, depending on the // peek at head flag. Again this is only a peek, the node is only to be removed if it is to be // goal checked. SearchNode < O , T > currentNode = peekAtHead ? queue . peek ( ) : headNode ; // Only goal check leaves, or nodes already expanded. (The expanded flag will be set on leaves anyway). if ( currentNode . isExpanded ( ) ) { // If required, remove the node to goal check from the queue. currentNode = peekAtHead ? queue . remove ( ) : headNode ; // Check if the current node is a goal state. if ( goalPredicate . evaluate ( currentNode . getState ( ) ) ) { return currentNode ; } } // Check if there is a maximum number of steps limit and increase the step count and check the limit if so. if ( maxSteps > 0 ) { searchSteps ++ ; // Update the search state with the number of steps taken so far. initSearch . setStepsTaken ( searchSteps ) ; if ( searchSteps >= maxSteps ) { // The maximum number of steps has been reached, however if the queue is now empty then the search // has just completed within the maximum. Check if the queue is empty and return null if so. if ( queue . isEmpty ( ) ) { return null ; } // Quit without a solution as the max number of steps has been reached but because there are still // more states in the queue then raise a search failure exception. else { throw new SearchNotExhaustiveException ( "Maximum number of steps reached." , null ) ; } } } } // No goal state was found so return null return null ; }
Search until a goal state is found or the maximum allowed number of steps is reached .