небольшая последовательность
Недавно я читал книгу "Иллюстрированный алгоритм", и меня очень тронула глава "Алгоритм Дикстры".
Алгоритм Дейкстры — очень известный алгоритм, который10 лучших алгоритмов, изменивших миродин дляРешите проблему [Кратчайший путь из одного источника] [Расширение прав и возможностей] [Направленный ациклический граф].
Без этого алгоритма Интернет, безусловно, не был бы таким эффективным, как сегодня. Пока проблема может быть представлена моделью «графа», этот алгоритм можно использовать для нахождения кратчайшего расстояния между двумя узлами в «графе». Стабильность алгоритма Дейкстры по-прежнему незаменима.
Примечание: алгоритм Дейкстры.Оригинальная копияработает только для поиска кратчайшего пути между двумя вершинами, позже более распространенныйВариантыЗафиксируйте вершину как исходный узел и найдите кратчайший путь от этой вершины ко всем остальным узлам в графе, создав дерево кратчайших путей (дерево — это граф без циклов). В этой статье речь пойдет о последнем.
определение
Если вам трудно понять смысл предложения с жирной красной меткой в преамбуле? Давайте разберем их по одному, и вы все поймете. При желании пропустите этот раздел, если вы знакомы с понятиями.
Что на картинке
- Рисунок【узел】и【боковая сторона] используется для имитации связи между разными вещами.
Изображение 1-1
Мы обнаружили, что слишком многие из наших реальных сценариев связаны со структурой графов. Ассоциация между людьми, ассоциация между местами и местами, различные топологические карты и т.д. Примеры конкретных сценариев будут приведены позже.
Что такое ориентированный ациклический граф
Почему направлено?
Рис. 1.1 — неориентированный граф, а рис. 1.2 — ориентированный граф, разница в том, что последний обозначает направление связи между точками.
Рисунок 1-2
Что такое ациклический?
Ориентированный граф называется ориентированным ациклическим графом, если он начинается из любой вершины и не может вернуться в эту точку через несколько ребер.
- Q&A
В: Является ли рисунок 1-2 направленным ациклическим?
A: Нет, потому что A возвращается к A после прохождения C.
Рисунок 1-3
Так является ли рисунок 1-3 направленным ациклическим?
A: Да, чтобы узнать больше наen.wikipedia.org/wiki/Направленный-ациклический-граф.
Что такое расширение прав и возможностей
«Вес» здесь означает «вес», а «взвешивание» означает присвоение веса ребрам графа.
Рисунок 1-4
Например, на рис. 1-4 требуется 10 шагов, чтобы перейти от точки 1 к точке 2, и 100 шагов, чтобы перейти от точки 1 к точке 5, где 10 и 100 — «весовые значения».
Специальное примечание: алгоритм Дейкстры имеет неотрицательные веса ребер.
Каков кратчайший путь из одного источника
Кратчайший путь заключается в вычислении кратчайшего (минимального веса) пути между двумя заданными узлами.Если начальная точка определена, он называется кратчайшим путем с одним источником.
Существует множество реальных приложений кратчайших путей: многие карты предоставляют возможности навигации и используют алгоритм кратчайшего пути или его варианты. Когда мы просматриваем чей-то профиль на многих социальных платформах, платформа покажет, сколько у вас общих друзей, и перечислит отношения между вами, что также основано на этом алгоритме.
Теперь вернемся к этому определению:
Алгоритм Дейкстры используется дляРешите проблему [Кратчайший путь из одного источника] [Расширение прав и возможностей] [Направленный ациклический граф].
Ты понимаешь? Просто придерживайтесь трех ключевых слов: «расширение возможностей», «ориентированный ациклический граф» и «кратчайший путь из одного источника». Грубо говоря, этот алгоритм используется для нахождения кратчайшего расстояния между двумя точками.
выполнить
Итак, дело в том, как реализован алгоритм Дейкстры?
Возвращаясь к книге "Algorithm Illustrated", мы можем увидеть наиболее наглядный пример.
картинка 2-1
На рис. 2-1, каков кратчайший путь от начальной до конечной точки?
Если вы используете поиск в ширину (BFS), вы получите ответ 7 (конкретная реализация, не указанная), но это, очевидно, не оптимальное решение. Мы можем распознать человеческим глазом, что правильный ответ должен быть 6, то есть из начальной точки - в точку Б - в точку А - в конечную точку.
Если вы используете компьютер, как рассчитывается правильный ответ? Это наш герой-Алгоритм Дейкстры.
четыре шага
Алгоритм Дейкстры состоит из 4 шагов:
- Найдите самый «дешевый» узел, тот, до которого можно добраться за кратчайшее время.
- Стоимость обновления соседей этого узла, последствия которой описаны позже.
- Повторяйте этот процесс, пока не сделаете это для каждого узла графа.
- Рассчитать конечный путь.
- Шаг 1: Найдите «самый дешевый» узел
Давайте сначала рассмотрим первый шаг. Вы начинаете с начальной точки. Есть два пути на выбор. Требуется 6 шагов, чтобы перейти к A, и 2 шага, чтобы перейти к B. Независимо от других узлов, точка B является самым дешевым узлом. Запишите следующий набор, что очень важно.
Рисунок 2-2
Рисунок 2-3
- Шаг 2: Рассчитайте время, необходимое для путешествия к каждому соседу через узел B.
Требуется 5 шагов от начальной точки, чтобы пройти через точку B до точки A, и 7 шагов от начальной точки, чтобы пройти через точку B до конечной точки. В предыдущем наборе требуется 6 шагов от начальной точки до точки A, а конечная точка положительная бесконечность. Теперь мы имеемлучшее решение, тебе нужновозобновитьРезультатом этого набора затрат является рисунок 2-4.
Рисунок 2-3
Рисунок 2-4
- Шаг 3: Повторите! ! !
Как повторить? Мы сделали операцию обновления на основе точки B, нам нужно сделать аналогичную операцию для остальных узлов. В таблице на рис. 2-4, за исключением точки B, точка A имеет наименьшие накладные расходы, поэтому нам нужно работать с точкой A. - "Стоимость обновления всех соседей узла A."
Требуется 1 шаг, чтобы начальная точка прошла через точку A в конечную точку, 5 + 1 = 6, что меньше требуемого значения 7 для стоимости конечной точки на рисунке 2-4, мы должнывозобновитьНакладной сбор.
Рисунок 2-5
Мы использовали алгоритм Дейкстры для каждого узла (нет необходимости делать это для конечных точек),Таким образом, рисунок 2-5 представляет собой окончательный набор затрат и окончательное оптимальное решение. От начала до конца всего за 6 шагов!
- четвертый шаг?
Внимательные друзья могли узнать, а как насчет четырех согласованных шагов? Почему есть только три шага выше? Здесь автор оставляет «схему», ведь в приведенном выше примере вычисляется только значение минимальной стоимости, а не получается конечный путь достижения минимальной стоимости, то есть отсутствует процесс возврата.
Как рассчитать конечный путь? Здесь автор приводит другой пример, и этот пример немного сложнее. Однако Бенгуа считает:Суть алгоритма Дейкстры лежит во втором и третьем шагах (обновление массива стоимости)., четвертым шагом для получения определенного пути является добавление отношения родитель-потомок для поиска с возвратом.
Рисунок 2-6
Как показано на рис. 2-6, спросите: каков кратчайший путь от партитуры до фортепиано?
Ответ: партитуры - пластинки - ударные - фортепиано, знаете ли вы конкретный процесс обновления коллекций накладных? Я думаю, что кто-то из опрошенных должен был задать этот вопрос.выучить больше
Краткое описание этой дыни: Начиная с точки [Партитура], рядом с двумя точками [Запись] и [Афиша], поместите их наНакладной массив, значения соответственно равны 0 и 5. 0 меньше 5, поэтому на основе [афиши] выполните второй шаг, получите [музыкальную партитуру] через [афишу], чтобы достичь значений соседних точек, а это [гитара] 30 и [Ударная установка] 35, на данный момент в массиве оверхеда четыре значения:
| название | накладные расходы |
|---|---|
| плакат | 0 (соседние значения были пройдены) |
| записывать | 5 |
| Гитара | 30 |
| ударная установка | 35 |
| ... | ... |
5
| название | накладные расходы |
|---|---|
| плакат | 0 (соседние значения были пройдены) |
| записывать | 5 (соседние значения были пройдены) |
| Гитара | 20 |
| ударная установка | 25 |
| ... | ... |
Продолжайте движение, 20
| название | накладные расходы |
|---|---|
| плакат | 0 (соседние значения были пройдены) |
| записывать | 5 (соседние значения были пройдены) |
| Гитара | 20 (пройдены соседние значения) |
| ударная установка | 25 (пройдены соседние значения) |
| пианино | 35 (конечная точка, переход не требуется) |
Если вы можете легко пройти через это, у вас не будет проблем с алгоритмическим мышлением~
На самом деле кратчайший путь — это не обязательно физическое расстояние, но его также можно преобразовать в другие показатели, такие как деньги, время и так далее. Абстрагируя сцены из жизни в такие алгоритмические задачи, моей маме больше не нужно беспокоиться о том, что я иду в обход~
Дийкстра! Крупный рогатый скот!
Дань уважения автору этого алгоритма — Эдсгеру Вайбе Дейкстре, получившему премию Тьюринга в 1972 году.
код
Алгоритмические идеи важны, но РАЗГОВОР ДЕШЕВО!! реализован в ру здесь. Также нашел реализацию JS -Поиск кратчайшего пути в Javascript: алгоритм ДейкстрыВыкопайте яму и переведите, когда у вас будет время. /(ㄒоㄒ)/~~
node = find_lowest_cost_node(costs) // 在未处理的节点中找出开销最小的节点
while node is not None: // 这个while循环在所有节点都被处理过后结束
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys(): // 遍历当前节点的所有邻居
new_cost = cost + neighbors[n]
if costs[n] > new_cost: // 如果经当前节点前往该邻居更近，
costs[n] = new_cost // 就更新该邻居的开销
parents[n] = node // 同时将该邻居的父节点设置为当前节点
processed.append(node) // 将当前节点标记为处理过
node = find_lowest_cost_node(costs) // 找出接下来要处理的节点，并循环
// 找出开销最低的节点
def find_lowest_cost_node(costs):
lowest_cost = float("inf")
lowest_cost_node = None
for node in costs: // 遍历所有的节点
cost = costs[node]
if cost < lowest_cost and node not in processed:// 如果当前节点的开销更低且未处理过，
lowest_cost = cost // 就将其视为开销最低的节点
lowest_cost_node = node
return lowest_cost_node
Массив стоимостей — это массив стоимостей, по которому можно получить минимальную стоимость, то есть кратчайший путь.
Если вам интересно, вы также можете посмотреть видео профессора Цюй Ванлин из Пекинского университета——«Задача и алгоритм кратчайшего пути с одним источником», говорит очень четко.
миф
прекрасный ум
Алгоритм Дейкстры на самом деле является жадным алгоритмом. Потому что алгоритм всегда пытается сначала посетить следующий узел, ближайший к начальной точке, на каждом шаге цикла.
Недавно Бенгуа случайно посмотрел фильм «Игры разума», который углубил его понимание «Равновесия Нэша».
В теории игр равновесие по Нэшу (или точка равновесия по Нэшу) — это некооперативная игра с участием двух или более игроков, предполагающая, что каждый игрок знает других игроков. В случае стратегии равновесия игрока не существует единого концептуального решения, когда игрок может извлечь выгоду, изменив свою стратегию. -- Википедия
В игровом процессе, независимо от выбора стратегии другой стороной, одна из сторон выберет определенную стратегию, которая называется доминирующей стратегией. Если какой-либо игрок выбирает оптимальную стратегию, когда стратегии всех остальных игроков определены, то комбинация определяется как равновесие Нэша. -- Энциклопедия Байду
Объединив эти два понятия, Бенгуа был сбит с толку:
В этом алгоритме Дейкстры каждый наш ход — это игра. Если каждый шаг игры передается разным людям для достижения их собственного оптимального решения, то обязательно ли окончательное решение будет оптимальным...? Это предполагает устойчивость алгоритма? Или концепция запутана, или она немного философская? В любом случае, это дело довольно интересное. Алгоритмы, теория игр, оптимальные решения...
Концепция
- Алгоритмы графов
«Из известных мне алгоритмов графовые алгоритмы должны быть наиболее полезными». - Адитья Бхаргава (автор Algorithm Illustrated)
Существует три основных типа алгоритмов графа: поиск пути, вычисление центральности и обнаружение сообщества.
Существует два основных графовых алгоритма.Алгоритм обхода:
- Поиск в ширину (BFS)
- Поиск в глубину (DFS)
Те, кто изучал «Структуру данных», не должны быть незнакомы. В то же время BFS можно сравнить с алгоритмом Дейкстры: первый можно использовать для поиска кратчайшего пути в невзвешенном графе, а второй — во взвешенном графе. Также следует отметить, что если вес графа отрицательный, следует использовать [алгоритм Беллмана-Форда]. Заинтересованы в дальнейшем расширении⑧.
инструмент
- Решатель алгоритма Дейкстры (нарисовано):mdahshan.github.io/dijkstra/
выше
Письмо не легко и нуждается в поощрении. Молодые люди, поговорите о боевых искусствах: нравится, нравится и не нравится три раза подряд. Спасибо~
Я Наггетс Энтони, личный веб-мастер, который продолжает выводить~