SHARE
TWEET

Untitled

a guest Mar 20th, 2017 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package hw3.puzzle;
  2.  
  3. import  edu.princeton.cs.algs4.MinPQ;
  4. import java.util.HashSet;
  5. import java.util.LinkedList;
  6.  
  7. public class Solver {
  8.     private int moves;
  9.     private LinkedList<WorldState> solution = new LinkedList<>();
  10.     private HashSet<WorldState> worldStateSet;
  11.     /*
  12.     Constructor which solves the puzzle, computing
  13.                  everything necessary for moves() and solution() to
  14.                  not have to solve the problem again. Solves the
  15.                  puzzle using the A* algorithm. Assumes a solution exists.
  16.      */
  17.  
  18.     public Solver(WorldState initial) {
  19.         worldStateSet = new HashSet<>();
  20.         Iterable<WorldState> neighbors;
  21.         SearchNode currNode = new SearchNode(initial);
  22.         MinPQ<SearchNode> queue = new MinPQ<>();
  23.         queue.insert(currNode);
  24.         queue.delMin();
  25.  
  26.         while (!currNode.getWorldState().isGoal()) {
  27.             neighbors = currNode.getWorldState().neighbors();
  28.             for (WorldState i: neighbors) {
  29.                 if (!worldStateSet.contains(i)) {
  30.                     queue.insert(new SearchNode(i, moves() + 1, currNode));
  31.                     worldStateSet.add(currNode.getWorldState());
  32.                 }
  33.             }
  34.             currNode = queue.delMin();
  35.         }
  36.  
  37.         while (currNode != null) {
  38.             solution.addFirst(currNode.getWorldState());
  39.             currNode = currNode.getPrevNode();
  40.         }
  41.     }
  42.  
  43.     /*
  44.     Returns the minimum number of moves to solve the puzzle starting
  45.                  at the initial WorldState.
  46.      */
  47.     public int moves() {
  48.         return solution.size();
  49.     }
  50.  
  51.     /*
  52.     Returns a sequence of WorldStates from the initial WorldState
  53.     to the solution.
  54.     */
  55.     public Iterable<WorldState> solution() {
  56.         return solution;
  57.     }
  58.  
  59.     public class SearchNode implements Comparable<SearchNode> {
  60.         private WorldState worldState;
  61.         private int numMoves;
  62.         private SearchNode prevNode;
  63.  
  64.         public SearchNode() {
  65.             worldState = null;
  66.             numMoves = 0;
  67.             prevNode = null;
  68.         }
  69.  
  70.         public SearchNode(WorldState word) {
  71.             this.worldState = word;
  72.             numMoves = 0;
  73.             prevNode = null;
  74.         }
  75.  
  76.         public SearchNode(WorldState word, int numMoves, SearchNode prevNode) {
  77.             this.worldState = word;
  78.             this.numMoves = numMoves;
  79.             this.prevNode = prevNode;
  80.         }
  81.  
  82.         public WorldState getWorldState() {
  83.             return worldState;
  84.         }
  85.  
  86.         public int getMoves() {
  87.             return numMoves;
  88.         }
  89.  
  90.         public SearchNode getPrevNode() {
  91.             return prevNode;
  92.         }
  93.  
  94.         public int compareTo(SearchNode n2) {
  95.             if ((getWorldState().estimatedDistanceToGoal() + getMoves()) >
  96.                     n2.getWorldState().estimatedDistanceToGoal() + n2.getMoves()) {
  97.                 return 1;
  98.             } else if(getWorldState().estimatedDistanceToGoal() < n2.getWorldState().estimatedDistanceToGoal()){
  99.                 return -1;
  100.             } else {
  101.                 return 0;
  102.             }
  103.         }
  104.  
  105.     }
  106. }
RAW Paste Data
Top