SHARE
TWEET

Untitled

a guest May 22nd, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.File;
  2. import java.io.FileNotFoundException;
  3. import java.util.ArrayList;
  4. import java.util.Comparator;
  5. import java.util.PriorityQueue;
  6. import java.util.Scanner;
  7.  
  8.  
  9. class StateComparator implements Comparator<State> {
  10.  
  11.     enum Algorithm {
  12.         BestFirst, AStar
  13.     }
  14.  
  15.     private Algorithm algorithm;
  16.     private State solutionState;
  17.  
  18.     /**
  19.      * Create a new StateComparator which compares two different states given
  20.      * the wanted algorithm and solution state.
  21.      * @param algorithm BestFirst or AStar
  22.      * @param solutionState desired solution state
  23.      */
  24.     public StateComparator(Algorithm algorithm, State solutionState) {
  25.         this.algorithm = algorithm;
  26.         this.solutionState = solutionState;
  27.     }
  28.  
  29.     private int computeF(State state) {
  30.         int result = 0;
  31.         /* f(n) = g(n) + h(n) */
  32.         switch(algorithm) {
  33.         case BestFirst:
  34.             /* g(n) = 0 */
  35.             result = state.approximateDistance(solutionState);
  36.         case AStar:
  37.             /* g(n) = numarul de mutari din pozitia initiala */
  38.             result = state.getDistance() + state.approximateDistance(solutionState);
  39.         }
  40.         return result;
  41.     }
  42.  
  43.     @Override
  44.     public int compare(State arg0, State arg1) {
  45.         return computeF(arg0) - computeF(arg1);
  46.     }
  47. }
  48.  
  49. public class MainClass {
  50.  
  51.     static State initialState;
  52.     static State solutionState;
  53.  
  54.     public static void readData(String filename) {
  55.         int x, y;
  56.         int numRows, numCols;
  57.  
  58.         Scanner scanner;
  59.         try {
  60.             scanner = new Scanner(new File(filename));
  61.  
  62.             /* read map stats */
  63.             numRows = scanner.nextInt();
  64.             numCols = scanner.nextInt();
  65.             State.init(numRows, numCols);
  66.  
  67.             x = scanner.nextInt();
  68.             y = scanner.nextInt();
  69.             initialState = new State(x, y);
  70.  
  71.             x = scanner.nextInt();
  72.             y = scanner.nextInt();
  73.             solutionState = new State(x, y);
  74.  
  75.             /* read the map */
  76.             for(int i = 0; i < State.numRows; i++)
  77.                 for(int j = 0; j < State.numCols; j++)
  78.                     if(scanner.nextInt() == 1)
  79.                         State.matrix[i][j] = true;
  80.  
  81.             scanner.close();
  82.         } catch (FileNotFoundException e) {
  83.             // TODO Auto-generated catch block
  84.             e.printStackTrace();
  85.         }
  86.     }
  87.    
  88.     static Boolean visited(ArrayList<State> closed, State state) {
  89.         for (State newState : closed) {
  90.             if (state.equals(newState)) {
  91.                 return true;
  92.             }
  93.         }
  94.         return false;
  95.     }
  96.  
  97.     public static void main(String[] args) {
  98.         /* Citire harta, stare initiala si finala */
  99.         readData("Puzzle.in");
  100.  
  101.         Comparator<State> stateComparator = new StateComparator(StateComparator.Algorithm.AStar, solutionState);
  102.         PriorityQueue<State> open = new PriorityQueue<State>(1, stateComparator);
  103.        
  104.         /* Initial doar nodul de start este in curs de explorare */
  105.         open.add(initialState);
  106.  
  107.         /* Pentru nodurile care au fost deja expandate. */
  108.         ArrayList<State> closed = new ArrayList<State>();
  109.        
  110.  
  111.         /* TODO: A* */
  112.         int found = 0;
  113.         while (!open.isEmpty()) {
  114.             State state = open.poll();
  115.             closed.add(state);
  116.             ArrayList<State> expanded = state.expand();
  117.             for (State neighbour : expanded) {
  118.                 if (neighbour.equals(solutionState)) {
  119.                     found = 1;
  120.                     solutionState = neighbour;
  121.                     break;
  122.                 }
  123.                 if (visited(closed, neighbour) == false) {
  124.                     open.add(neighbour);
  125.                 }
  126.                 if (found == 1) {
  127.                     break;
  128.                 }
  129.             }
  130.  
  131.         }
  132.         solutionState.printPath();
  133.  
  134.     }
  135.  
  136. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top