From CSULA CS Wiki
< Courses‎ | CS 460‎ | Fall 2006‎ | Search
Jump to: navigation, search

Code

<java> package search;

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

public class Searcher {

 protected ExtendableState startState;
 protected SearchType searchType;
 
 private long startTime = System.currentTimeMillis();
 private long duration;
 private int statesSeen = 1, deadends = 0;


 // 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.
 protected AbstractList<ExtendableState> frontier;
 
 // 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, we don't want to look at them again.
 protected TreeSet<ExtendableState> seenStates;

 public Searcher(ExtendableState strtState) {
   startState = strtState;
 }
 
 public ExtendableState search(SearchType search, boolean verbose) {
   ExtendableState shortCircuit = setup(search, verbose);
   if (frontier == null) return shortCircuit;
   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();
     statesSeen++;
     if (verbose) System.out.println("  " + currentState + " --> " + nextState + ".");
     if (nextState.satisfiesGoal()) {
       if (verbose) {
         System.out.println("\tReached goal.");
         printStatistics(1);
       }
       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);
       }
     }
     // contains() uses the definition of compareTo() required by ExtendableState.
     if (seenStates.contains(nextState)) {
       if (verbose) {
         System.out.println("\tHave already seen " + nextState + 
         ". Ignoring it.");
       }
     } else if (!nextState.hasNext()) {
       deadends++;
       if (verbose) {
         System.out.println("\t" + nextState + " has no successors. Ignoring it.");
       }
     } else {
       seenStates.add(nextState);
       // Let the searchType determime where to add nextState in the frontier list.
       searchType.addState(frontier, nextState, verbose);
     }
   }
   // Didn't reach the goalState and nothing left to try.
   if (verbose) {
     System.out.println("No path found from " + startState + " which satisfies the goal.");
     printStatistics(0);
   }
   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. So 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. 
   System.out.println(" --> " + state.toString());
   // Return the indent for subsequent lines.
   return indent;
 }

 private void printStatistics(int finalState) {
   duration = System.currentTimeMillis() - startTime;
   System.out.println("\nTotal states seen: " + statesSeen);
   System.out.println("Distinct states seen: " + (seenStates.size() + deadends + finalState));
   System.out.println("Dead ends: " + deadends);
   System.out.println("Time: " + duration + " ms.");
 }
 /** Set up the problem. If the start state satisfies the goal either before
  *  or after propagation don't create the frontier list. Similaly if the
  *  start state doesn't have a successor.
  *  This will cause the searcher to abort.
  */
 private ExtendableState setup(SearchType search, boolean verbose) {
   if (verbose) {
     System.out.println("Start state: \n" + startState);
   }
   if (startState.satisfiesGoal()) {
     if (verbose) System.out.println("The start state satisfies the goal.");
     return startState;
   }
   /* boolean canPropagate = */ startState.propagate();
   if (verbose) {
     System.out.println("State state after propagation: \n" + startState);
   }
   if (!startState.isValid()) {
     if (verbose) {
       System.out.println("The propagated start state is not " +
                          "consistent with the constraints.\nNo solution.");
     }
     return null;
   }
   if (startState.satisfiesGoal()) {
     if (verbose) {
       System.out.println("The propagated start state satisfies the goal.");
     }      
     return startState;
   }
   if (!startState.hasNext()) {
     if (verbose) {
       System.out.println("\t" + startState + " has no successors. No solution.");
     }
     return null;
   }
   
   this.searchType = search;
   frontier = new ArrayList<ExtendableState>();
   frontier.add(startState);
   
   seenStates = new TreeSet<ExtendableState>();
   seenStates.add(startState);
   
   if (verbose) {
     System.out.println("Search type: " + searchType);
     System.out.println("\nFrontier lists:");
   }
   
   return null;
 }

 private String spaces(int indent) {
   StringBuffer spaces = new StringBuffer();
   for (int i = 0; i < indent; i++) spaces.append(' ');
   return spaces.toString();
 }

} </java>