Project II (A*)  -A* algorithm with two different heuristics SOLUTION

 You are required to implement A* algorithm with two different heuristics, as described in the  book, to solve the 15-puzzle problems.  
Implementation Requirements: (1) Language can be either JAVA or C++ (JAVA preferred). You are required to upload both the source code and the executable file. For the executable file, it should be able to run from the command line with the following format (take BFS as an example):   “bfs” is the name of the executable code; “input.txt” is the input file; “output.txt” is the output file. In other words, the code has two parameters: one is the location of the input file and the other is the location of the output file.  
z Input format: It contains only 4 lines and each line corresponds to one line in the puzzle. And the blank is represented as “X”. For example, the puzzle in Fig 1 is represented as: 1 2 5 X 6 3 8 7 10 11 12 13 15 4 14 9   
Fig 1 puzzle example  
z Output format: It contains multiple lines and one action per line. For example, it can be: right left left right up down 
 Examples of the input file and output file are the same as the previous project.  
(2) You are required to implement A* algorithm without checking the repeated states.  
Submission Requirements: (1) Submitted through blackboard. (2) Pack your files into one file with the file name as: yourname.tar. For example, “Xiaoxiao Shi.tar” (3) The following files should be included in the package: (a) Source code, packed in one file with the name “source.tar” (b) Executable code, with the name “astar1” and “astar2” (c) A report file which compares the running time and memory used in different situations (You are required to design the test examples by yourself). For example:  
Steps  A*1 (time sec)  A*2 (time sec)  A*1(memory)  A*2(memory)  2  0  0  455  755  4  16  0  455  4552  6  62  0  455  4554  8  79  0  455  4550  10  953  0  455  4550  12  11312  0  455  45511  13  64422  15  455  45532  14  133844  15  455  45563  15  290750  16  455  4555554  20  333333  Out of memory  455  Out of memory  
Evaluation: Scoring will be based on three parts: (1) Can give the correct solutions; that is, pass some test examples (will not release before deadline, don’t ask the TA for the testing examples) 50% (2) Can implement the heuristic functions correctly 20% (3) Report 30%  
Note: any executable file that cannot read the input file correctly or generate the output file correctly will get 0 score in the first part. Duplicate and near duplicate codes (checked by software) will all assign 0 score in the whole project!   
Tips: How to output running time and memory used in JAVA (you have to search how to output running time and memory used in C++ by yourself if you want): 1. Running time: long a = System.currentTimeMillis(); BFS bfs = new BFS();; long b =System.currentTimeMillis(); System.out.println("Time in millisecond:"); System.out.println(b-a);  
2. Memory used: In your class, e.g., BFS, you have to define a function called usedMemory() and invoke the function after finishing your algorithm:  
public Class BFS{ private static final Runtime s_runtime = Runtime.getRuntime (); private static long usedMemory ()  {             return s_runtime.totalMemory () - s_runtime.freeMemory ();      }             public static void main(String [] args){      BFS bfs = new BFS();      ……      System.out.ptintln(usedMemory()); } }   
Powered by