| | | 1 | | using MoreStructures.PriorityQueues; |
| | | 2 | | |
| | | 3 | | namespace MoreStructures.Graphs.ShortestDistance; |
| | | 4 | | |
| | | 5 | | /// <summary> |
| | | 6 | | /// A <see cref="IShortestDistanceFinder"/> implementation based on the A* algorithm, which is a refinement of |
| | | 7 | | /// the Dijkstra's algorithm, introducing a goal-oriented heuristic, driving the search in the direction of the end |
| | | 8 | | /// vertex. |
| | | 9 | | /// </summary> |
| | | 10 | | /// <remarks> |
| | | 11 | | /// <para id="requirements"> |
| | | 12 | | /// <inheritdoc cref="DijkstraShortestDistanceFinder" path="/remarks/para[@id='requirements']"/> |
| | | 13 | | /// </para> |
| | | 14 | | /// <para id="algorithm"> |
| | | 15 | | /// ALGORITHM |
| | | 16 | | /// <br/> |
| | | 17 | | /// - The algorithm is described in <see cref="DijkstraShortestDistanceFinder"/>, with the only difference that |
| | | 18 | | /// edge distances are modified, based on a heuristic defined as a potential function. |
| | | 19 | | /// <br/> |
| | | 20 | | /// - New edge distance is defined as follow: given the potential function P, for each edge (u, v) in the graph, |
| | | 21 | | /// <c>d'(u, v) = d(u, v) + P(v) - P(u)</c>. |
| | | 22 | | /// <br/> |
| | | 23 | | /// - If P is defined correctly, P(u) and P(v) are good approximations of the distance of u and v from the end |
| | | 24 | | /// vertex e. |
| | | 25 | | /// <br/> |
| | | 26 | | /// - If so, <c>P(v) - P(u)</c> will be negative if moving from u to v gets us closer to e and positive if it |
| | | 27 | | /// gets us farther from it. |
| | | 28 | | /// <br/> |
| | | 29 | | /// - For this reason, given two vertices v' and v'' connected from u via <c>e' = (u, v')</c> and |
| | | 30 | | /// <c>e'' = (u, v'')</c>, and such that <c>d(e') = d(e'')</c>, if <c>P(v') < P(v'')</c> then |
| | | 31 | | /// <c>d'(e') < d''(e')</c>, so the algorithm will prefer e' over e'' during the exploration, as it seems to |
| | | 32 | | /// be closer to e. |
| | | 33 | | /// <br/> |
| | | 34 | | /// - Because the algorithm stops when e is processed, if the algorithm visits e earlier than later, the algorithm |
| | | 35 | | /// will find the shortest path from s to e ealier than later. |
| | | 36 | | /// </para> |
| | | 37 | | /// <para id="complexity"> |
| | | 38 | | /// COMPLEXITY |
| | | 39 | | /// <br/> |
| | | 40 | | /// - The complexity heavily depends on the accuracy of the potential function. |
| | | 41 | | /// <br/> |
| | | 42 | | /// - A good model of the average performance of the algorithm is very complicated to derive, since the heuristic |
| | | 43 | | /// can drive the exploration much quicker or slower towards the end vertex, depending on how the function is |
| | | 44 | | /// defined. |
| | | 45 | | /// <br/> |
| | | 46 | | /// - In general, potential functions which are closer to the actual shortest distance to the end vertex yield |
| | | 47 | | /// better results. The farther they move from the ideal, the less optimized the exploration of the graph |
| | | 48 | | /// becomes. |
| | | 49 | | /// <br/> |
| | | 50 | | /// - Worst case remains as in <see cref="DijkstraShortestDistanceFinder"/>, where all vertices of the graph have |
| | | 51 | | /// to be explored, for a path from the start to the end to be found (or prove there is no path, since start and |
| | | 52 | | /// end lie in two different connected components). |
| | | 53 | | /// <br/> |
| | | 54 | | /// - Best case is when P is the shortest distance to e, in which case only the vertices of a shortest path from |
| | | 55 | | /// s to e are visited (which is tipically a small fraction of the vertices of the graph, especially if the graph |
| | | 56 | | /// is large). That is the bare minimum to find the shortest path from s to e. |
| | | 57 | | /// <br/> |
| | | 58 | | /// - Average case can even be worse than normal Dijkstra, if P is misleading, i.e. if it drives the exploration |
| | | 59 | | /// away from e, rather than reducing the cost of edges which drives the exploration closer to e. |
| | | 60 | | /// <br/> |
| | | 61 | | /// - However, with a well defined P, close enough to the actual shortest distance, Time Complexity is between |
| | | 62 | | /// O(e + v * log(v)) and O(h), where h is the highest number of edges of a shortest path from s to e. |
| | | 63 | | /// <br/> |
| | | 64 | | /// - Space Complexity is also between O(h) and O(v). |
| | | 65 | | /// </para> |
| | | 66 | | /// </remarks> |
| | | 67 | | public class AStarShortestDistanceFinder : PotentialBasedShortestDistanceFinder |
| | | 68 | | { |
| | | 69 | | /// <inheritdoc cref="AStarShortestDistanceFinder"/> |
| | | 70 | | /// <param name="priorityQueueBuilder"> |
| | | 71 | | /// A builder of a <see cref="IUpdatablePriorityQueue{T}"/> of <see cref="int"/> values, used by the algorithm to |
| | | 72 | | /// store edges with priority from the closest to the start, to the farthest. |
| | | 73 | | /// </param> |
| | | 74 | | public AStarShortestDistanceFinder(Func<IUpdatablePriorityQueue<int>> priorityQueueBuilder) |
| | 30 | 75 | | : base(new DijkstraShortestDistanceFinder(priorityQueueBuilder)) |
| | 30 | 76 | | { |
| | 30 | 77 | | } |
| | | 78 | | } |