From CSULA CS Wiki
< Courses‎ | CS 460‎ | Fall 2006‎ | Search
Revision as of 15:36, 24 October 2006 by WikiAdmin (Talk | contribs)

Jump to: navigation, search

<java> package searchExample;

import java.util.AbstractList; import java.util.ArrayList; import java.util.TreeSet;

public class Searcher {

 public ExtendableState search(SearchType searchType, 
                               ExtendableState startState, 
                               ExtendableState goalState, 
                               boolean verbose) {
   if (startState.equals(goalState)) return startState;
   // These are the states currently on the "frontier," i.e., the current leaves 
   // of the current tree. We have to examine their successors (children) if any.
   AbstractList<ExtendableState> frontier = new ArrayList<ExtendableState>();
   frontier.add(startState);
   // These are the states which have ever been on the frontier, i.e., the current
   // leaves plus all current interior nodes of the current tree.
   // Since we have seen them once, don't want to look at them again.
   TreeSet<ExtendableState> seenStates = new TreeSet<ExtendableState>();
   seenStates.add(startState);
   if (verbose) {
     System.out.println("Start state: " + startState);
     System.out.println("Using " + searchType + " search.");
     System.out.println("Frontier lists");
   }
   while (!frontier.isEmpty()) {
     if (verbose) System.out.println(frontier);
     ExtendableState currentState = frontier.get(0);
     // This is a successor of CurrentState. Add it to the frontier.
     ExtendableState nextState = currentState.next();
     if (verbose) System.out.println("  " + currentState + " --> " + nextState + ".");
     if (nextState.equals(goalState)) {
       if (verbose) System.out.println("\tReached goal.");
       return nextState;
     }
     if (!currentState.hasNext()) {
       // We have seen all the successors of currentState.
       // Remove it from the frontier.
       frontier.remove(0);
       if (verbose) {
         System.out.println("\tNo more children of " + currentState +
         ". Removing it from the frontier list.");
         //System.out.println(frontier);
       }
     }
     if (seenStates.contains(nextState)) {
       if (verbose) System.out.println("\tHave already seen " + nextState + 
       ". Ignoring it.");
     } else {
       seenStates.add(nextState);
       // Let the searchType determime where to add nextState in the frontier list.
       searchType.addState(frontier, nextState, verbose);
     }
   }
   // No more frontier states, and we didn't reach the goal.
   return null;
 }
 public int printPathTo(ExtendableState state) {
   ExtendableState predecessor = state.getPredecessor();
   // If this is the first state (on first line). 
   //   Print the state but don't terminate line.
   //   Return the length of the first state as an indent for subsequent lines.
   if (predecessor == null) {
     System.out.println("Path from start state to goal.");
     String stateString = state.toString();
     System.out.print(stateString);
     return stateString.length();
   }
   // If this is not the first state, print the first (and other previous) states.
   // Capture the indent length.
   int indent = printPathTo(predecessor);
   // If this is not the second state (on the first line) we are printing an entirely
   // new line. 
   //  Print indent number of spaces. 
   // On the other hand, if this is the second state (which is on the first line), 
   // don't print the extra spaces.
   if (predecessor.getPredecessor() != null) System.out.print(spaces(indent));
   // In either case, print " --> ", the state, and "\n". 
   // Return the indent for subsequent lines.
   System.out.println(" --> " + state.toString());
   return indent;
 }
 private String spaces(int indent) {
   StringBuffer spaces = new StringBuffer();
   for (int i = 0; i < indent; i++) spaces.append(' ');
   return spaces.toString();
 }

} </java>