The A* algorithm for shortest path and applications
The A* algorithm for shortest path and applications
If a graph has many nodes, Dijkstra's algorithm for shortest path can be slow for practical (route planning) purposes. The algorithm also might make some uninformed choices: it expands any node that is closer to the origin than the destination, no matter if that node is `in the general direction of the destination' or not. When applied to a road map, this means that routes are examined by the algorithm for which one look at the map would tell you that they would never contribute to a fastest route to your destination. The A* algorithm can be viewed as a generalization of Dijkstra's algorithm that makes more informed choices, based on a (given, or computed) heuristic value h(n) for each node n that underestimates the distance from n to the destination (think for example of h(n) being the Euclidean distance from n to the destination if the nodes of the graph are points in the plane, or cities on a road map).
Goals of this bachelor final project:
*) Study literature on the algorithm A*, its properties and its running time, the conditions under which it finds an optimal solution
*) Find applications, e.g. path finding problems in a geographic or a gaming setting where the use of A* could enhance performance.
*) Implement the algorithm with respect to a suitable heuristic function, and apply it to such instances.
Report on the results and on the computation time.
*) Find improvements for the heuristic function in the chosen application. Compare several heuristic functions with respect to performance and/or speed.