|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Алгоритмы построения минимальных связывающих деревьев
Для построения МСД разработан ряд полиномиальных алгоритмов. Алгоритм Прима Алгоритм Прима (R.C. Prim) относится к так называемым " жадным" алгоритмам. Жадные алгоритмы действуют, используя в каждый момент лишь часть исходных данных и принимая лучшее решение на основе этой части. В нашем случае мы будем на каждом шаге рассматривать множество ребер, допускающих присоединение к уже построенной части связывающего дерева, и выбирать из них ребро с наименьшим весом. Повторяя эту процедуру, мы получим остовное дерево с наименьшим весом. Начнем с произвольной вершины графа xi и включим ее в остовное дерево. Из всех вершин, соединенных с данной (xjÎ Гxi), ищем вершину, соединенную ребром с наименьшим весом. Это ребро вместе с новой вершиной добавляется в дерево. Из вершин, не вошедших в дерево, ищем вершину, соединенную с уже построенной частью остовного дерева ребром с наименьшим весом. Это ребро вместе с новой вершиной добавляется в дерево и т. д. После того, как в дерево попадут все вершины, работа будет закончена. Пример. Исходный взвешенный граф изображен на рис.7.1 (а).
Рисунок 7.1. Исходный граф (а) и ребра–кандидаты (б) Ребра, вошедшие в дерево, на рисунках будем отмечать жирной линией. В начале процесса выбираем произвольную вершину, например, х1. Выбираем вершины, непосредственно связанные с х1 (рис.7.1.(б)). Ребро наименьшего веса связывает вершины х1 и х2, поэтому к уже построенной части МСД добавляется вершина х2 вместе с ребром (х1 х2). При добавлении к дереву вершины х2 необходимо определить, не следует ли добавить в кандидаты новые ребра. В результате обнаруживаем, что это необходимо проделать с ребрами (х2 х5) и (х2 х7). Здесь же необходимо проверить, являются ли ребра, ведущие из вершины х1, в х3, х4 и х7, кратчайшими среди ребер, соединяющих эти вершины с деревом, или есть более удобные ребра, исходящие из х2. Ребро (х2 х4) короче ребра (х1 х4), и поэтому необходимо его заменить (рис.7.2.(а)).
Рисунок 7.2. Добавление ребра (х1 х2) (а) и ребра (х2 х5) (б) Наименьший вес из пяти ребер - кандидатов имеет ребро (х2 х5), поэтому к дереву нужно добавить его и вершину х5 (рис. 7.2 (б)). Вес ребра (х5 х7) меньше веса ребра (х2 х7), поэтому оно замещает последнее. Из четырех ребер, инцидентных построенной части дерева, наименьший вес имеет ребро (х1 х3), поэтому следующим к дереву добавляется оно и вершина х3 (рис. 7.3 (а)). Затем к дереву добавляется ребро (х1 х6) вместе с вершиной х6. Поскольку вес ребра (х4 х6) меньше веса ребра (х2 х4), а вес ребра (х6 х7) меньше веса ребра (х5 х7), меняем ребра – кандидаты (рис. 7.3 (б)).
Рисунок 7.3. Добавление в дерево ребра (х1 х3) (а) и ребра (х1 х6) (б) Ребро (х4 х6) имеет наименьший вес среди оставшихся, и оно добавляется следующим (рис. 7.4 (а)). Теперь осталось добавить к дереву всего одно ребро (х6 х7) (рис. 7.4 (б)). После этого процесс завершается, построено МСД с суммарным весом ребер 21.
Рисунок 7.4. Добавление ребра (х4 х6) (а) и ребра (х6 х7) (б) Сложность алгоритма Прима равна O(m3), где m = |X|. Алгоритм Краскала Алгоритм Краскала (J.B. Kruskal) заключается в следующем. Упорядочим все ребра исходного графа по неубыванию весов. Просматривая последовательность слева направо, включаем в дерево каждое ребро, не образующее в дереве цикла. О том, что ребро (хi хj) образует цикл можно судить по тому, что из вершины хi есть путь в вершину хj по другим ребрам дерева. Процесс заканчивается, когда в дерево включено (m – 1) ребро. Построим МСД для графа рис. 7.1 (а). Упорядочим ребра:
МСД алгоритмом Краскала
Суммарный вес ребер МСД равен 21. Сложность алгоритма Краскала равна O(n log n), где n = |U|. Кратчайшие пути Пусть дан граф G(X, Γ ), ребрам которого приписаны веса (стоимости), заданные матрицей C=||cij||m× m. Задача о кратчайшем пути состоит в нахождении пути с минимальным суммарным весом от начальной вершины sÎ X до конечной tÎ X или от начальной вершины s Для нахождения кратчайших путей в графах разработано и реализовано на различных языках программирования много различных алгоритмов. К ним можно отнести алгоритмы: Дейкстры, Дейкстры-Грибова, Левита, Йена, Флойда-Уоршелла, Форда-Беллмана, Джонсона. Кратко рассмотрим эти алгоритмы. Алгоритм Дейкстры находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса. В процессе работы алгоритма поддерживаются три множества: М0 – вершины, расстояние до которых уже вычислено (но, возможно, не окончательно); М1 – вершины, расстояние до которых вычисляется; М2 – вершины, расстояние до которых еще не вычислялось. В простейшем случае, сложность алгоритма составляет O(m2 + n). Здесь m – количество вершин графа, n – количество ребер графа. Эффективность метода Дейкстры существенно зависит от того, как организован поиск во множестве М1 вершины с наименьшим текущим расстоянием. Модификация Грибова заключается в том, что вершины разбиваются на подмножества с близкими, отличающимися меньше чем на минимальную длину ребра, значениями кратчайшего пути в текущую вершину на данном шаге. Затем на каждой итерации берется непустое множество, соответствующее минимальному значению расстояния. Алгоритм Левита позволяет найти кратчайшие пути от заданной вершины до всех остальных вершин. Алгоритм Левита напоминает метод Дейкстры – в процессе работы поддерживаются три множества (M0, M1, M2). Вершины, входящие во множество М1, делятся на два упорядоченных множества – основную и приоритетную очередь. Каждой вершине сопоставляется неотрицательное значение длины кратчайшего из известных на данный момент путей в нее из начальной вершины. В сравнении с методом Дейкстры метод Левита проигрывает на том, что некоторые вершины приходится обрабатывать повторно, а выигрывает на более простых алгоритмах включения и исключения вершин из множества М1. Эксперименты показывают, что для графов с «геометрическим» происхождением, т.е. для графов, построенных на основе транспортных сетей и реальных расстояний, метод Левита оказывается наиболее быстрым. Он выигрывает и по размеру программы. Метод Левита обладает еще и тем преимуществом перед методом Дейкстры, что он применим в случае отрицательных длин ребер. Сложность алгоритма составляет O(n∙ m). Алгоритм Йена предназначен для нахождения нескольких путей минимальной суммарной длины во взвешенном графе с неотрицательными весами между двумя вершинами. Алгоритм Беллмана-Форда решает задачу о нахождении кратчайших путей из одной вершины во все остальные для случая, когда веса ребер могут быть отрицательными. Кроме того алгоритм контролирует отсутствие циклов отрицательного веса, достижимых из исходной вершины. Если в графе нет циклов отрицательного веса, алгоритм находит кратчайшие пути из заданной вершины во все остальные, если же в графе есть циклы отрицательного веса, то, по крайней мере, для некоторых вершин кратчайшего пути не существует. Идея алгоритма, также как и алгоритма Дейкстры, основана на последовательной релаксации ребер, пока не будут найдены кратчайшие расстояния. Сложность алгоритма Форда - Беллмана есть O(n∙ m). Алгоритм Флойда-Уоршелла это динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Сложность алгоритма O(m3), т.е. алгоритм имеет кубическую сложность. Тем не менее, алгоритм определяет только кратчайшие расстояния между всеми парами вершин, но не сохраняет информации о кратчайших путях. Алгоритм Джонсона позволяет найти кратчайшие пути между любыми двумя вершинами графа за O(m2log(m) + n∙ m). Следовательно, для достаточно разреженных графов, он эффективнее альтернативных алгоритмов возведения в квадрат матрицы весов и алгоритма Флойда-Уоршелла. Этот алгоритм основан на идее изменения весов ребер графа. Если для ребер найти такую функцию, которая изменяет их веса, обеспечивая их неотрицательность и оставляя кратчайшие пути такими же (то есть состоящими из тех же ребер), то задачу поиска кратчайших путей между всеми парами вершин можно решить применив алгоритм Дейкстры для каждой вершины. Рассмотрим подробно алгоритм Дейкстры (E.Dijkstra). Он основан на приписывании вершинам временных пометок, дающих верхнюю границу длины пути от s к этой вершине. Эти пометки постепенно уточняются, и на каждом шаге итерации точно одна из временных пометок становится постоянной. Это указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от s к рассматриваемой вершине. Пусть l(xi) пометка вершины xi, а l(xi)+ - постоянная пометка вершины. 1. Положить l(s)=0+ и считать эту пометку постоянной. Положить l(xi)=∞ для всех xi ≠ s и считать их временными. Положить p=s. 2. Для всех xi l(xi) = min[l(xi), l(p) + c(p, xi)]. 3. Среди всех вершин с временными пометками найти такую, для которой l(xi*) = min[l(xi)]. 4. Считать пометку вершины xi* постоянной l(xi*)+ и положить p= xi*. 5. (Если надо найти лишь путь от s до t). Если p=t, то l(p) – длина кратчайшего пути, конец. Если p ≠ t, перейти к п.2. 6. (Если надо найти путь от s до всех остальных вершин). Если все вершины имеют постоянные пометки, то конец, если есть временные пометки, то перейти к п.2. Сами пути можно получить при помощи рекурсивной процедуры с использованием соотношения: l(xi’) + c(xi’, xi)= l(xi), где xi’ – вершина непосредственно предшествующая вершине xi в кратчайшем пути от s к xi. Пример. Дан взвешенный граф G(X, Г) и матрица весов C=׀ ׀ cij׀ ׀ 7× 7 (рис. 7.6). Необходимо найти кратчайшие пути от начальной вершины x1 ко всем остальным вершинам.
Рисунок 7.6. Исходный граф и матрица весов 1. l(x1)=0+; l(xi)= ∞, для всех i ≠ 1, p = x1. Результаты итерации запишем в таблицу.
2. Гp ={x2, x6, x7} – все пометки временные, уточним их: l(x2)=min[∞ , 0++2]=2; l(x6)=min[∞, 0++10]=10;
l(x7)=min[∞, 0++17]=17. 3. l(xi*) = min[l(xi)] = l(x2) = 2. 4. x2 получает постоянную пометку l(x2) = 2+, p=x2. 5. Не все вершины имеют постоянные пометки, поэтому Гp ={x1, x3, x7} – временные пометки имеют вершины x3, x7, уточняем их: l(x3)=min[∞, 2++3]=5; l(x7)=min[17, 2++10]=12. 6. l(xi*) = min[l(xi)] = l(x3) = 5.
7. l(x3) = 5+, p=x3. 8. Не все вершины имеют постоянные пометки, Гp ={x2, x4, x6} – временные пометки имеют вершины x4, x6, уточняем их: l(x4)=min[∞ , 5++15]=20; l(x6)=min[10, 5++3]=8.
9. l(xi*) = min[l(xi)] = l(x6) = 8. 10. l(x6) = 8+, p=x6. 11. Не все вершины имеют постоянные пометки Гp ={x1, x5, x7} – временные пометки имеют вершины x5, x7, уточняем их: l(x5)=min[∞ , 8++15]=23; l(x7)=min[12, 8++3]=11.
12. l(xi*) = min[l(xi)] = l(x7) = 11. 13. l(x7) = 11+, p=x7. 14. Не все пометки постоянные
Гp ={x1, x2, x4, x6} – временную пометку имеет вершина x4, уточняем ее: l(x4)=min[20, 11++5]=16. 15. l(xi*) = min[l(xi)] = l(x4) = 16. 16. l(x4) = 16+, p=x4. 17. Не все пометки постоянные
Гp ={x3, x5, x7} – временную пометку имеет вершина x5, уточняем ее: l(x5)=min[23, 16++5]=21. 18. l(xi*) = l(x5) = 21. 19. l(x5) = 21+, p=x5. 20. Все пометки постоянные. Кратчайшие расстояния от вершины x1 до всех вершин найдены. Как найти кратчайший путь до конкретной вершины, покажем на примере вершины x5. l(x5) = 21, Гx5 ={x4, x6}, 21 = l(x4)+ c(x4, x5)=16+5, 21 ≠ l(x6)+ c(x6, x5)=8+15.
Это означает, что в вершину x5 мы попали из вершины x4. Далее, l(x4) = 16, Гx4 ={x3, x5, x7}, 16 ≠ l(x3)+ c(x3, x4)=5+15, 16 ≠ l(x5)+ c(x5, x4)=21+15, 16 = l(x7)+ c(x7, x4)=11+5. Это означает, что в вершину x4 мы попали из вершины x7. Далее, l(x7) = 11, Гx7 ={x1, x4, x6}, 11 ≠ l(x1)+ c(x1, x7)=0+17, 11 ≠ l(x4)+ c(x4, x7)=16+5, 11 = l(x6)+ c(x6, x7)=8+3. Это означает, что в вершину x7 мы попали из вершины x6. Далее, l(x6) = 8, Гx6 ={x1, x3, x5, x7}, 8 ≠ l(x1)+ c(x1, x6)=0+10, 8 = l(x3)+ c(x3, x6)=5+3, 8 ≠ l(x5)+ c(x5, x6)=21+15, 8 ≠ l(x7)+ c(x7, x6)=11+3. Это означает, что в вершину x6 мы попали из вершины x3. Далее, l(x3) = 5, Гx3 ={x2, x4, x6}, 5 = l(x2)+ c(x2, x3)=2+3, 5 ≠ l(x4)+ c(x4, x3)=16+15, 5 ≠ l(x6)+ c(x6, x3)=8+3. Это означает, что в вершину x3 мы попали из вершины x2. Далее, l(x2) = 2, Гx2 ={x1, x3, x7}, 2 = l(x1)+ c(x1, x2)=0+2, 2 ≠ l(x3)+ c(x3, x2)=5+3, 2 ≠ l(x7)+ c(x7, x2)=11+10. Это означает, что в вершину x2 мы попали из вершины x1. Кратчайший путь от вершины x1 до вершины x5 найден (рис.7.7):
Рисунок 7.7. Кратчайшие пути от вершины x1 до всех вершин
Популярное:
|
Последнее изменение этой страницы: 2017-03-10; Просмотров: 1213; Нарушение авторского права страницы
X до всех остальных, при условии, что такие пути существуют.