Комментарии 27
А как этот алгоритм связан с алгоритмом обхода в ширину? Чем отличается?
Практически ничем не отличается, так как Волновой алгоритм относится к семейству алгоритмов основанных на методах поиска в ширину.
Волновой звучит круче! На ум сразу приходят волновая функция, тфкп, уравнение Шредингера и т.п.
Алгоритм обхода в ширину звучит как то проще и приземлённее. А вот если бы он назывался Алгоритм Сопряженно-Резонирующего Стохастического Осциллятора, то было бы совсем круто! Если когда ни будь придумаю какой ни будь алгоритм, обязательно так его и назову, и неважно, что он из себя будет представлять, под такое заковыристое название можно натянуть любую логику работы.
Это один в один обход в ширину. Разница лишь в том, что при обходе в ширину клетки, которые нужно обойти, ставятся в одну очередь, а тут они "разделены на эпохи". Те же яйца только в профиль
алгоритм совсем без оптимизации. Имхо он вообще не пытается найти кратчайший путь, а просто хоть какой-то, с приоритетом вверх, а потом влево.
Можно было бы поставить хотя бы один анализ на упреждение, шага вперед, получилось бы значительно лучше..
Нет, алгоритм находит кратчайший путь. Доказывается по индукции по длине пути. Потому что он сначала посетит все клетки на расстоянии 0 (одна начальная), потом все клетки на расстоянии 1, потом все на расстоянии 2 и т.д.
Я этот алгоритм знал под названием "Алгоритм Дейкстры".
Кстати, у этого алгоритма есть еще неочевидное крайне полезное для некоторых применений свойство: он очень легко натягивается на распределенный случай (когда каждая клетка содержит процессор, и нет "общей шины" и "общих часов" - все общаются только со своими соседями и не знают общей картины).
Ну уж нет, это вариация обхода в ширину. Алгоритм Дейкстры сложнее и работает дольше.
"Дейкстра" работает во взвешенных графах, а тут все переходы между клетками одного веса. Поэтому задача здесь проще и применять "Дейкстру" нет никакого смысла.
Работает не особо дольше, асимптотика у него та же, и константа тоже близкая, и зависящая только от способа хранения структуры данных в памяти.
Сложнее? Тоже не кажется так. Клетчатое поле со стенками - это частный случай графа. Вес всегда единица - ну так нет особой разницы, единицу прибавлять к "дальности" или вес ребра. Обход делается одинаково, тоже в ширину.
Та же асимптотика? Это вообще как?
У обхода в ширину асимптотика O(E), у Дейкстры — O(V²) или O(E log V) если делать её через приоритетную очередь. Применительно к лабиринту у нас V=N², E = 4N², поэтому обход в ширину работает за O(N²), в то время как Дейкстра — за O(N⁴) или за O(N² log N) если с очередью.
Это было во-первых. А во-вторых, тот код который написан в посте, соответствует обходу в ширину и не соответствует алгоритму Дейкстры.
Кажется, у меня проблема с названиями. У того, что я в своей голове называю алгоритмом Дейкстры, асимптотика O(N*N), так как мы гарантированно не будем осуществлять "выход из узла" больше чем M раз (где M - диаметр графа, и он гарантированно <= N), и будем делать это в худшем случае для N узлов (где N - количество узлов).
Ага, именно так — у Дейкстры асимптотика O(N*N). А у обхода в ширину — O(M), где M — число дуг/рёбер в графе.
Поскольку лабиринт — сильно разреженный граф (M = O(N)), в нём обход в ширину работает на порядок быстрее обычного алгоритма Дейкстры.
Понял! Действительно, эти алгоритмы не эквивалентны. При волновом алгоритме за счет поколений волн и, кстати, за счет одинакового веса ребер, обеспечивается гарантия отсутствия необходимости ходить по одному ребру более одного раза. Соответственно, и асимптотика лучше.
Но и полезные свойства по легкому натягиванию на распределенный случай тоже уходят, их не обеспечить, так как есть те самые поколения волн, а соответственно, нужны "общие часы" какого-то вида.
Вы не правы. Ассимтотики у волнового алгоритма (он же обход в ширину) и у дейкстры разные (для не полных графов, естественно). Дейкстра или в N раз медленнее или там надо использовать сильно более сложные структуры данных типа кучи.
Да, я уже понял свою ошибку. Дейкстра посещает узлы более чем по одному разу, эти алгоритмы неэквивалентны.
Насчет сложных структур данных: так вроде там нигде нет операций поиска? Что там можно улучшить кучей или другими структурами? Вроде бы обычного списка с исключением и вставкой по O(1) достаточно.
Поправка: как улучшить среднее время выполнения с помощью продвинутых структур данных - понятно, но худший случай выбором других структур данных вместо списков можно только ухудшить.
Дейкстра посещает узлы более чем по одному разу, эти алгоритмы неэквивалентны.
Нет, дейкстра тоже "посещает" узлы по одному разу. Вот только он каждый раз ищет, какой же следующий узел посетить — тот который имеет минимальную оценку расстояния. Именно эта операция и оптимизируется кучей. Правда тут вылезает проблема, что тогда надо и при обработке ребер из текущего узла обновлять струкуру данных. Поэтому для плотных графов дейскстра с кучей рабоатет даже медленнее тупого выбора минимума.
Опять я что-то либо не так понимаю, либо не так называю...
Дейкстра ведь приходит в каждый узел с разных направлений, и дальше из этого узла идет только когда метка узла изменилась? И выбор ребра с минимальным весом только позволяет улучшить среднее время, несколько уменьшив количество приходов в узлы, изменивших их метку? А так все равно для поиска кратчайшего пути придется посетить все достижимые вершины по всем входящим путям, просто после первого нахождения целевой вершины можно немного соптимизировать и больше не ходить путями, которые длиннее уже найденного.
Дейкстра ведь приходит в каждый узел с разных направлений, и дальше из этого узла идет только когда метка узла изменилась?
Нет. Дейкстра заходит в узел, обрабатывает ("релаксирует") все выходящие из него ребра. Выбирает следующий узел. Обход в ширину, кстати, работает точно так же. Заходит в узел, обрабатывает все исходящие ребра (и кладет в очередь еще непосещенные вершины), выбирает следующий узел.
Похоже, я что-то не то называю алгоритмом Дейкстры :)
В том, что у меня всю жизнь было в голове, он идет вширь и переписывает метки узлов, до которых добирается. Причем добирается до них разными путями - соседом нового узла может оказаться давно посещенный. Надо подумать, возможно, проход по пути в направлении сначала ближних узлов гарантирует непосещение второй раз. Никогда об этом не задумывался.
Спасибо за наводку, без пинка я бы так и не узнал бы, что тут еще есть о чем подумать.
Волновой алгоритм