lojix/search/src/main/com/thesett/aima/search/util/backtracking/BacktrackingAlgorithm.java
public SearchNode<O, T> 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 goalPredicate = initSearch.getGoalPredicate();

        // Backtrack the most recent goal state, if one has been established.
        if (mostRecentGoalNode != null)
        {
            backtrack(mostRecentGoalNode);

            // Clear the most recent goal, now that it has been backtracked if required.
            mostRecentGoalNode = null;
        }

        // 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 headNode = queue.remove();

            // Apply the current nodes operator to establish its shared state.
            Reversable reversableState = (ReTraversable) headNode.getState();
            reversableState.applyOperator();

            // 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.
            headNode.unexaminedSuccessorCount = headNode.expandSuccessors(queue, reverseEnqueue);

            // As the head node is about to be goal tested, reduce the unexamined successor count of its predecessor.
            if (headNode.getParent() != null)
            {
                headNode.getParent().unexaminedSuccessorCount--;
            }

            // Check if the current node is a goal state.
            if (goalPredicate.evaluate(headNode.getState()))
            {
                // Remember this goal node so that subsequent searches remember to backtrack over it.
                mostRecentGoalNode = headNode;

                return headNode;
            }

            // Backtrack over all fully exhausted nodes from the current position, as required.
            backtrack(headNode);

            // 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;
    }
public SearchNode<O, T> 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 goalPredicate = initSearch.getGoalPredicate();

        // Backtrack the most recent goal state, if one has been established.
        if (mostRecentGoalNode != null)
        {
            backtrack(mostRecentGoalNode);

            // Clear the most recent goal, now that it has been backtracked if required.
            mostRecentGoalNode = null;
        }

        // 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 headNode = queue.remove();

            // Apply the current nodes operator to establish its shared state.
            Reversable reversableState = (ReTraversable) headNode.getState();
            reversableState.applyOperator();

            // 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.
            headNode.unexaminedSuccessorCount = headNode.expandSuccessors(queue, reverseEnqueue);

            // As the head node is about to be goal tested, reduce the unexamined successor count of its predecessor.
            if (headNode.getParent() != null)
            {
                headNode.getParent().unexaminedSuccessorCount--;
            }

            // Check if the current node is a goal state.
            if (goalPredicate.evaluate(headNode.getState()))
            {
                // Remember this goal node so that subsequent searches remember to backtrack over it.
                mostRecentGoalNode = headNode;

                return headNode;
            }

            // Backtrack over all fully exhausted nodes from the current position, as required.
            backtrack(headNode);

            // 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;
    }
public SearchNode < O , T > 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 goalPredicate = initSearch . getGoalPredicate ( ) ; // Backtrack the most recent goal state, if one has been established. if ( mostRecentGoalNode != null ) { backtrack ( mostRecentGoalNode ) ; // Clear the most recent goal, now that it has been backtracked if required. mostRecentGoalNode = null ; } // 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 headNode = queue . remove ( ) ; // Apply the current nodes operator to establish its shared state. Reversable reversableState = ( ReTraversable ) headNode . getState ( ) ; reversableState . applyOperator ( ) ; // 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. headNode . unexaminedSuccessorCount = headNode . expandSuccessors ( queue , reverseEnqueue ) ; // As the head node is about to be goal tested, reduce the unexamined successor count of its predecessor. if ( headNode . getParent ( ) != null ) { headNode . getParent ( ) . unexaminedSuccessorCount -- ; } // Check if the current node is a goal state. if ( goalPredicate . evaluate ( headNode . getState ( ) ) ) { // Remember this goal node so that subsequent searches remember to backtrack over it. mostRecentGoalNode = headNode ; return headNode ; } // Backtrack over all fully exhausted nodes from the current position, as required. backtrack ( headNode ) ; // 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 ; }
{@inheritDoc}
{