Our aim in this programming exercise is to explore the implications of different search algorithms and heuristics in a nice, easily-vizualized route-finding domain. Specifically, your challenge is to implement a general search engine program capable of doing DFS, BFS, Best-first, and A*. As evident from book and lecture, this is really a single base algorithm that you can manipulate to produce the various search behaviors. The idea is that your program runs repeatedly, exploring a given map using each of these algorithms in turn. Of course, if everything is working correctly, all of the searches will find a desired route (assuming one exists)…but you will see that they havedramaticallydifferent search behaviors. We’ve discussed some of the pros/cons of these algorithms in lecture (completeness, time/space complexity, and optimality); the aim here will be to see what this REALLY MEANS in a hand-on scenario. Your program will print out the statistics for each search run as it completes that search. For the A* search, I will ask you to explore one informed heuristic, with top score requiring the exploration of two or more.
The search spaces for this problem will be maps, such as the one visualized on the right. Specifically, you will need to be able to load a “map” from a simple text file with very simple format, with each line of the file describing one edge in the graph:
(node1, node2, edgevalue, [x1,y1],[x2,y2])
To do the search, you technically only need the first three of these; the x-y positions of the two nodes are only needed if you want to actually lay out/visualize the search graphically.
For instance,here is the map file which corresponds to the image above. The map on the right is actually a snapshot of theDRDViztool in action: start and goal have been marked, and a search has been started and has explored several nodes.
Important note: We want our maps to simulate real life! Lookcarefullyat the map on the right and you will notice that the distances on the edges are NOT just straight-line-distance (SLD) between the nodes…reflecting the fact that in real life, the length of a road between two places is almost always longer than a “way the crow flies” SLD between the places! In other words, you can assume the following constraint: maps will always show distances between nodes, and these distances arevaguelyrepresentative of the physical distance between them, but will often be longer (never shorter) than a calculated straight-line-distance between node coordinates.