Description
In the language of your choosing (details located below), write a program which reads in the provided Graph files (see below). For both Graphs 1 & 2, run UCS or Dijkstra's Algorithm to find the minimum cost path from S->G (if it exists). Print out the number of explored vertices (size of the closed set), the size of the fringe (open set), the path (in the correct order S->G) and the optimal path cost. Next, run an A* Search using the provided heuristics. Print out the number of explored vertices (size of the closed set), the size of the fringe (open set), the path (in the correct order S->G) and the optimal path cost.
------------------------------------------------------------------------------------------------------------------------
Requirements
1: Read in OR hard-code the data from the files provided for both Part 1 & 2 including the labels, adjacency matrix, and heuristic values.
2: Run UCS or Dijkstra's Algorithm to find the optimal path from S->G (if it exists). Print out the optimal path in order from S->G and print out the cost of the path.
3: Print out the size of the fringe (the number of nodes still in the open set when the algorithm ends).
4: Print out the number of explored vertices (the number of nodes in the closed set when the algorithm ends).
5: Repeat steps 2-4 using the A* Algorithm.
------------------------------------------------------------------------------------------------------------------------
Suggestion:
You may use either UCS or Dijkstra's Algorithm for Part 2. Remember that UCS is the same as A* Search when all heuristic values are set to zero. You may use your A* Search function for both UCS and A*, just remember to set all heuristics to zero when using A* as UCS
------------------------------------------------------------------------------------------------------------------------
Hints:
Your code from PA #1 should be very helpful for reading in graph data into an Adjacency Matrix. You're encouraged to re-use this code if possible. (I will provide the file)
The path and path cost should be equal for UCS/Dijkstra's and A*. Only the size of the fringe and number of explored nodes can potentially be different
Heuristics should be stored as a 1D array similar to how we stored vertex names. Each index of the heuristics array corresponds to the node of the same index
- Think of the heuristics array and the labels array as parallel arrays!
Remember- heuristics are an estimate of the optimal path cost from the given node to the target
The values for hScore are known when your search begins. They never change!
The values for gScore are the actual path cost from the source to the given node. gScore is identical to the dist array from Dijkstra's and UCS
The values for fScore are hScore[i] + gScore[i] for any given node i
When relaxing the edge weights (i.e. a better path has been found), remember that if you update gScore for a node, you must also update its fScore!
------------------------------------------------------------------------------------------------------------------------
Code you can use:
Java
If you use a flat directory structure (i.e. not using packages), then please only provide your .java files. Your .class files, .jar files, and any Eclipse, NetBeans, BlueJ, etc. folders and metadata are not necessary. If you are using packages, then make sure your directories are correctly formatted in your compressed file.
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
C/C++
Any IDE files and metadata are unnecessary. Please only include .c, .cpp, and .h files. I will use GCC v4.9.2 (32 bit) on Windows OR Microsoft Visual C++ 2019 to compile the code, so if you use compiler-specific features that are not compatible, please include a .exe file as well.
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
C#
All Visual Studio files are unnecessary. Please only include .cs files. If you're using a preview branch of the .NET framework beyond 5.0, please include a .exe file as well.
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
Python
Any IDE files and metadata are unnecessary. Please only include .py files. I will use Python 3.3.0 to run the code. Note that Python versions are notoriously incompatible- so if you're using a 2.x distribution, please include an .exe file along with your code or let me know beforehand.