Скрытая красота алгоритма A*
00:00 Вступление 01:38 Измените длины! 06:34 Что такое хороший потенциал? 12:31 Реализация 16:20 Бонус Видео Тома Сламы: • Theseus and the Minotaur | Exploring State... Наш Patreon: / polylog Github: https://github.com/polylog-cs/Astar/t...
Блог: https://vasekrozhon.wordpress.com/202...
Некоторые материалы по теме: -- Я не упомянул, что алгоритм Дейкстры предназначен для поиска кратчайшего пути от начальной вершины до всех остальных вершин графа. Он справляется с этой задачей очень хорошо, практически за линейное время, так что улучшать особо нечего. Именно в задаче поиска кратчайшего пути между двумя узлами алгоритм A* обычно превосходит алгоритм Дейкстры. -- Вот ссылка на другой пример алгоритма A*, запущенного из Сараево в восточную Италию. Видно, как алгоритм быстро достигает первого города, Тираны, но затем застревает из-за Адриатического моря. Поэтому он ищет вдоль её побережья, пока не находит Италию. После этого он уверенно проходит по Италии, пока не найдёт пункт назначения. https://github.com/polylog-cs/Astar/b...
-- Если ваша эвристика не является последовательной, но, по крайней мере, допустимой, алгоритм A* всё равно вернёт правильный ответ, хотя его временная сложность может экспоненциально зависеть от размера сети. -- IDA* — популярный алгоритм, который относится к итеративному углубляющемуся поиску в глубину так же, как A* относится к поиску в ширину/поиску Дейкстры. -- Возможно, простейшим применением техники перевеса потенциалов является алгоритм Джонсона: https://en.wikipedia.org/wiki/Johnson...
-- См. также эту запись в блоге Codeforces, в которой собраны некоторые примеры применения потенциалов в спортивном программировании. https://codeforces.com/blog/entry/95823
-- Основная причина, по которой потенциалы часто так полезны, заключается в том, что они двойственны концепции расстояний в смысле двойственности линейного программирования. Задачи: -- Докажите, что эвристики из видео непротиворечивы. -- Докажите, что максимальная из двух непротиворечивых эвристик также непротиворечива. (Таким образом, если у вас есть две несравнимые эвристики, их следует объединить таким образом.) -- Докажите, что для любой непротиворечивой эвристики, которая непротиворечива, равна нулю для целевого состояния и в остальном неотрицательна, алгоритм A* всегда исследует меньше состояний, чем алгоритм Дейкстры. То есть, за исключением времени, затрачиваемого на вычисление эвристики, алгоритм A* никогда не уступает алгоритму Дейкстры в задаче поиска кратчайшего пути между двумя точками. Большое спасибо: Рихарду Хладику, Матею Конечному, Мартину Марешу, Яннику Маусу, Яну Петру, Войтеху Рожоню, Ханке Рожонёвой, Тому Сламе. Ссылки в видео: карты.google.com https://geojson.io/
https://public.opendatasoft.com/explo...
https://stackoverflow.com/questions/2...
Кредиты: Для создания этого видео мы использовали manim, библиотеку Python: https://docs.manim.community/en/stable/
Цветовая палитра, которую мы используем, соляризована: https://ethanschoonover.com/solarized/
музыка: Thannoid группы Blue Dot Sessions: https://app.sessions.blue/browse/trac...
музыка: Также расскажите о Заратустре из Штрауса из Wikimedia Commons. изображение свитка: https://www.pxfuel.com/en/desktop-wal...
изображения городов взяты из Wikimedia Commons.
