00:00 Intro
01:38 Change the lengths!
06:34 What is a good potential?
12:31 Implementation
16:20 Bonus
Tom Sláma's video: https://youtu.be/umszOeerdsU
Our Patreon: https://www.patreon.com/Polylog
Github: https://github.com/polylog-cs/Astar/tree/main
Blog: https://vasekrozhon.wordpress.com/2024/09/04/the-hidden-beauty-of-the-a-algorithm/
Some related stuff:
-- One thing I did not mention is that Dijkstra's algorithm is designed to solve the problem of finding the shortest path from the start node to all other nodes of the graph. It does this job very well, in almost linear time, so there is not much to improve there. It is the problem of finding the shortest path between two nodes where A* usually improves upon Dijkstra.
-- Here is a link to another example of A* run from Sarajevo to east Italy. You can see how the algorithm quickly reaches the first city, Tirana, but then it gets stuck because of the Adriatic sea. So it searches along its coastline until it finds Italy. After that it confidently runs through Italy until it finds the destination.
https://github.com/polylog-cs/Astar/blob/main/Explore.mp4
-- If your heuristic is not consistent, but at least admissible, A* will still return the correct answer, though its time complexity may be exponential in the network size.
-- IDA* is a popular algorithm that relates to iterative deepening depth first search the same way as A* relates to Dijkstra/breadth first search.
-- A perhaps simplest application of potential reweighting technique is the Johnson’s algorithm:
https://en.wikipedia.org/wiki/Johnson%27s_algorithm
-- See also this codeforces blog post that collects some applications of potentials in competitive programming.
https://codeforces.com/blog/entry/95823
-- The underlying reason why potentials are often so useful is that they are dual to the concept of distances in the sense of linear programming duality.
Problems:
-- Prove that heuristics from the video are consistent.
-- Prove that the maximum of two consistent heuristics is still consistent. (Thus, if you have two incomparable heuristics, you should combine them this way. )
-- Prove that for any heuristic that is consistent, equal to zero for the goal state and otherwise nonnegative, A* always explores less states than Dijkstra. That is, apart for the time spent on computing the heuristic, A* is never worse than Dijkstra in the problem of finding the shortest path between two points.
Big thanks to: Richard Hladik, Matěj Konečný, Martin Mareš, Yannic Maus, Jan Petr, Vojtěch Rozhoň, Hanka Rozhoňová, Tom Sláma
Links in the video:
maps.google.com
https://geojson.io/
https://public.opendatasoft.com/explore/dataset/europe-road/export/?refine.icc=BE
https://stackoverflow.com/questions/29470253/astar-explanation-of-name
Credits:
To make this video, we used manim, a Python library: https://docs.manim.community/en/stable/
The color palette we use is solarized: https://ethanschoonover.com/solarized/
music: Thannoid by Blue Dot Sessions: https://app.sessions.blue/browse/track/126782
music: Also sprach Zarathustra from Strauss from wikimedia commons
image of the scroll: https://www.pxfuel.com/en/desktop-wallpaper-aadkb
images of the cities are from wikimedia commons