Скрытая красота алгоритма A*

00:00 Вступление 01:38 Измените длины! 06:34 Что такое хороший потенциал? 12:31 Реализация 16:20 Бонус Видео Тома Сламы:    • Theseus and the Minotaur | Exploring State...   Наш Patreon:   / polylog   Github:
Блог:
Некоторые материалы по теме: -- Я не упомянул, что алгоритм Дейкстры предназначен для поиска кратчайшего пути от начальной вершины до всех остальных вершин графа. Он справляется с этой задачей очень хорошо, практически за линейное время, так что улучшать особо нечего. Именно в задаче поиска кратчайшего пути между двумя узлами алгоритм A* обычно превосходит алгоритм Дейкстры. -- Вот ссылка на другой пример алгоритма A*, запущенного из Сараево в восточную Италию. Видно, как алгоритм быстро достигает первого города, Тираны, но затем застревает из-за Адриатического моря. Поэтому он ищет вдоль её побережья, пока не находит Италию. После этого он уверенно проходит по Италии, пока не найдёт пункт назначения.
-- Если ваша эвристика не является последовательной, но, по крайней мере, допустимой, алгоритм A* всё равно вернёт правильный ответ, хотя его временная сложность может экспоненциально зависеть от размера сети. -- IDA* — популярный алгоритм, который относится к итеративному углубляющемуся поиску в глубину так же, как A* относится к поиску в ширину/поиску Дейкстры. -- Возможно, простейшим применением техники перевеса потенциалов является алгоритм Джонсона:
-- См. также эту запись в блоге Codeforces, в которой собраны некоторые примеры применения потенциалов в спортивном программировании.
-- Основная причина, по которой потенциалы часто так полезны, заключается в том, что они двойственны концепции расстояний в смысле двойственности линейного программирования. Задачи: -- Докажите, что эвристики из видео непротиворечивы. -- Докажите, что максимальная из двух непротиворечивых эвристик также непротиворечива. (Таким образом, если у вас есть две несравнимые эвристики, их следует объединить таким образом.) -- Докажите, что для любой непротиворечивой эвристики, которая непротиворечива, равна нулю для целевого состояния и в остальном неотрицательна, алгоритм A* всегда исследует меньше состояний, чем алгоритм Дейкстры. То есть, за исключением времени, затрачиваемого на вычисление эвристики, алгоритм A* никогда не уступает алгоритму Дейкстры в задаче поиска кратчайшего пути между двумя точками. Большое спасибо: Рихарду Хладику, Матею Конечному, Мартину Марешу, Яннику Маусу, Яну Петру, Войтеху Рожоню, Ханке Рожонёвой, Тому Сламе. Ссылки в видео: карты.google.com


Кредиты: Для создания этого видео мы использовали manim, библиотеку Python:
Цветовая палитра, которую мы используем, соляризована:
музыка: Thannoid группы Blue Dot Sessions:
музыка: Также расскажите о Заратустре из Штрауса из Wikimedia Commons. изображение свитка:
изображения городов взяты из Wikimedia Commons.