Я понимаю, что Dijkstra algorithm, но я не знаю, Понимаете, почему это работает.
При выборе следующей вершины для изучения, почему алгоритм Дейкстры выбирает тот, который имеет наименьший вес? Почему бы просто не выбрать вершину произвольно, так как алгоритм все равно посещает все вершины?
Вы можете рассматривать алгоритм Джикстры как алгоритм заполнения водой (т.е. обрезанный поиск по ширине). На каждом этапе цель состоит в том, чтобы охватить больше всего графика с наименьшим ценовым путем. Предположим, что у вас есть вершины на краю области, которую вы заполнили, и вы перечислите их в терминах расстояния:
v0 <= v1 <= v2 <= v3 ...
Может ли быть более дешевый способ добраться до вершины v1? Если это так, путь должен пройти через v0, так как непроверенная вершина может быть ближе. Итак, вы проверяете вершину v0, чтобы увидеть, к чему вы можете добраться, проверяя, является ли какой-либо путь через v0 более дешевым (любой другой вершиной на один шаг).
Если вы устраните проблему таким образом, вы гарантируете, что ваши расстояния будут минимальными, потому что вы всегда проверяете именно ту вершину, которая может привести к кратчайшему пути. Либо вы найдете этот самый короткий путь, либо вы его исключите, и переходите к следующей вершине. Таким образом, вы гарантированно будете потреблять одну вершину за шаг.
И вы останавливаетесь, не делая больше работы, чем вам нужно, потому что вы останавливаетесь, когда конечная вершина занимает слот "Я самый маленький" v0.
Посмотрим на краткий пример. Предположим, мы пытаемся получить от 1 до 12 путем умножения, а стоимость между узлами - это число, которое вы должны умножить. (Мы ограничим вершины цифрами от 1 до 12.)
Начнем с 1, и мы можем перейти к любому другому node путем умножения на это значение. Таким образом, node 2 имеет стоимость 2, 3 имеет стоимость 3,... 12 имеет стоимость 12, если вы заходите на один шаг.
Теперь путь через 2 мог (не зная о структуре) быстрее добраться до 12, если бы была свободная ссылка от 2 до 12. Нет, но если бы это было, это было бы быстрее всего. Итак, мы проверяем 2. И мы находим, что мы можем добраться до 4 для стоимости 2, до 6 для 3 и т.д. Таким образом, у нас есть таблица затрат:
3 4 5 6 7 8 9 10 11 12 // Vertex
3 4 5 5 7 6 9 7 11 8 // Best cost to get there so far.
Хорошо, теперь, возможно, мы сможем получить 12 от 3 бесплатно! Лучшая проверка. И мы находим, что 3*2==6, поэтому стоимость 6 равна стоимости 3 plus 2, а до 9 - плюс 3, а 12 - плюс 4.
4 5 6 7 8 9 10 11 12
4 5 5 7 6 6 7 11 7
Достаточно честный. Теперь мы тестируем 4, и мы видим, что мы можем добраться до 8 для дополнительного 2 и до 12 для дополнительного 3. Опять же, стоимость перехода на 12 составляет, таким образом, не более 4 + 3= 7:
5 6 7 8 9 10 11 12
5 5 7 6 8 7 11 7
Теперь мы попробуем 5 и 6 - пока никаких улучшений. Это оставляет нам
7 8 9 10 11 12
7 6 8 7 11 7
Теперь, в первый раз, мы видим, что стоимость перехода на 8 меньше стоимости перехода на 7, поэтому нам лучше проверить, нет ли какого-либо свободного способа добраться до 12 от 8. Нет - нет никакого способа добраться туда с целыми числами, поэтому мы его выбросим.
7 9 10 11 12
7 8 7 11 7
И теперь мы видим, что 12 так же дешев, как и любой оставшийся путь, поэтому стоимость достижения 12 должна быть 7. Если бы мы до сих пор отслеживали самый дешевый путь (только заменяя путь, когда он был строго лучше), мы обнаружили бы, что 3*4 - это самый первый способ попасть в 12.
Алгоритм Дейкстра выбирает вершину с наименьшей стоимостью пути, потому что путь через любую другую вершину по меньшей мере столь же дорогостоящий, как путь через вершину с наименьшей стоимостью пути.
При посещении любой другой вершины поэтому, если она более дорогостоящая (что вполне возможно), необходимо посещать не только эту другую вершину, но и ту, которая имеет наименьшую стоимость пути, поэтому вам придется посещать больше вершин прежде чем найти кратчайший путь. Фактически, если вы это сделаете, вы получите алгоритм Bellman-Ford.
Я также должен добавить, что вершина не имеет веса, это край, который имеет вес. Ключом для данной вершины является стоимость кратчайшего пути, найденного до этого вершины из исходной вершины.
Причина, по которой алгоритм Dijsktra работает так, как она есть, отчасти связана с тем, что в ней используется кратчайший путь между node u и w, который включает в себя точку v, также содержит кратчайший путь из u до v и от v до w. Если между u и v существует что-то меньшее, то это не будет самый короткий путь.
Чтобы понять, почему работает алгоритм Дейкстры, изучите основы динамическое программирование, звучит сложно, но очень легко понять принципы,
Ему нравится жадная стратегия. Мой английский не очень хорошо. Он переводится Google. Если вы не понимаете, мне очень жаль.
Алгоритм Дейкстры, a G из S ко всем вершинам кратчайшей длины пути. Предположим, что каждой вершине G в V задан флаг L (V), либо либо число, либо ∞. Пусть P - множество вершин из G, P содержит S, чтобы удовлетворить:
A) Если V - это P, то L (V) из V S в длину кратчайшего пути и существование такого V от S до кратчайшего пути: путь на вершинах в P в
B) Если V не принадлежит P, то L (V) из S в V удовлетворяет следующим ограничениям на длину кратчайшего пути: V - единственный путь P не принадлежит вершине.
Мы можем использовать индукцию для доказательства алгоритма P Dijkstra в соответствии с приведенным выше определением коллекции:
1) Когда число элементов в P = 1, P соответствует первому шагу алгоритма, P = (S), очевидно, выполняется.
2) Пусть P - k, число элементов P удовлетворяет приведенному выше определению, см. алгоритм ниже третьего шага
3) P in и первое, чтобы узнать, не отмечено минимальной вершиной U, обозначенной как L (U), можно доказать из S в U из U за пределами кратчайшего пути, в дополнение к P не содержит элементы не принадлежат.
Так как если есть вне других вершин, кроме U, то самый короткий путь к S, P1, P2... Pn, Q1, Q2... Qn, U (P1, P2... Pn равен P; Q1, Q2,... Qn не принадлежит P), из характера B) кратчайшая длина пути L (Q1) + PATH (Q1, U) > L (U).
который больше, чем S, P1, P2... Pn, U длины канала L (U), не является самым коротким путем. Следовательно, от S до U U за пределами кратчайшего пути помимо P не содержит элементов, не принадлежащих U из S, к длине кратчайшего пути из L (U).
U добавляется к P в форме P ', очевидно, P', чтобы соответствовать характеру A).
Возьмем V не принадлежит P ', очевидно, не принадлежит VP, то от S до V, за исключением кратчайшего пути и удовлетворяющего всем вершинам вне V в P' на пути, есть две возможности: i) содержит U, ii) не содержит U.
На i) S, P1, P2... Pn, U, V = L (U) + W (U, V)
ii) S, P1, P2... Pn, V = L (V)
Очевидно, что два из них указаны в наименьшем V из S, чтобы соответствовать минимальному доступу, а внешнее дополнение ко всем вершинам имеет длину V P '.
Третий шаг к алгоритму, заданному в P 'с элементами k +1 и отвечающим A), B).
По индукционному предложению можно разрешить.
Вот источник.
Он сначала проверяет путь с самым низким весом, потому что это наиболее вероятно (без дополнительной информации), чтобы уменьшить количество проверенных путей. Например:
a->b->c cost is 20 a->b->d cost is 10 a->b->d->e cost is 12
Если цель состоит в том, чтобы перейти от a к e, нам не нужно даже проверять стоимость:
a->b->c->e
Потому что мы знаем это как минимум 20, поэтому мы знаем, что это не оптимально, потому что есть еще один путь со стоимостью 12. Вы можете максимизировать этот эффект, сначала проверив самые низкие веса. Это похоже (так же?) На то, как минимакс работает в шахматах и других играх, чтобы уменьшить коэффициент ветвления дерева игр.
Алгоритм Дийсктры - это жадный алгоритм, который следует за решением эвристики решения локально оптимального выбора на каждом этапе с надеждой на поиск глобального оптимума.