Комментарии 2
Объяснять алгоритм Дейкстры на примере лабиринта — очень плохая идея. На лабиринте хорошо изучать волновой алгоритм — в котором все расстояния между смежными узлами (соседними клетками) идентичны.
Собственно, это и произошло с автором: он крайне многословно и запутанно пытается объяснить именно волновой алгоритм, а не алгоритм Дейкстры. Зачем-то привлекая для этого Python-код.
К алгоритму Дейкстры в статье относятся: предложение «Получаем из списка открытых узлов тот узел, от которого нас отделяет наименьшее расстояние» и кусочек предложения «мы использовали бы для open_list не вектор, а очередь с приоритетами». Остальное — включая приведённые отрывки Python-кода — относится к волновому алгоритму.
N.B. Очевидно, статья рассчитана исключительно на пользователей Python, никогда не учившихся в ВУЗах, обучающих программистов (в которых алгоритмом Дейкстры решают задачи на занятиях математикой — не написанием программ, а ручкой на бумаге), но при этом настолько хорошо знающих алгоритмы, что они в состоянии сами понять, зачем к как нужно использовать очередь с приоритетами.
P.S. Алгоритм Дейкстры проще объяснять на карте дорог разной длины, соединяющих несколько городов. А для полного и понятного объяснения алгоритма достаточно нескольких картинок — без единой строчки кода. Как это сделано, например, в Википедии — статья в которой, посвящённая алгоритму Дейкстры, намного короче и несравнимо понятнее обсуждаемого творения.
Собственно, это и произошло с автором: он крайне многословно и запутанно пытается объяснить именно волновой алгоритм, а не алгоритм Дейкстры. Зачем-то привлекая для этого Python-код.
К алгоритму Дейкстры в статье относятся: предложение «Получаем из списка открытых узлов тот узел, от которого нас отделяет наименьшее расстояние» и кусочек предложения «мы использовали бы для open_list не вектор, а очередь с приоритетами». Остальное — включая приведённые отрывки Python-кода — относится к волновому алгоритму.
N.B. Очевидно, статья рассчитана исключительно на пользователей Python, никогда не учившихся в ВУЗах, обучающих программистов (в которых алгоритмом Дейкстры решают задачи на занятиях математикой — не написанием программ, а ручкой на бумаге), но при этом настолько хорошо знающих алгоритмы, что они в состоянии сами понять, зачем к как нужно использовать очередь с приоритетами.
P.S. Алгоритм Дейкстры проще объяснять на карте дорог разной длины, соединяющих несколько городов. А для полного и понятного объяснения алгоритма достаточно нескольких картинок — без единой строчки кода. Как это сделано, например, в Википедии — статья в которой, посвящённая алгоритму Дейкстры, намного короче и несравнимо понятнее обсуждаемого творения.
А Дейкстры то в статье и нет (хорошо бы на кучах его увидеть), для такой задачки и BFS зайдёт. Лучше Кормена почитать )
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Простейший вариант поиска пути: объяснение на Python