распадается на две:
Нахождение кратчайшего пути в графе с ребрами единичной длины (или с ребрами равной длины).
Нахождение кратчайшего пути в графе с ребрами произвольной длины.
А) Приписываем конечной вершине индекс 0.
Б) Помечаем 1 все смежные вершины.
В) Находим все вершины, смежные вершинам, имеющим индекс 1, и
приписываем им индекс 2.
Г) И т.д., пока не будут помечены все вершины. Значение индекса начальной вершины будет длиной пути.
Нахождение кратчайшего пути в графе с ребрами произвольной длины.
Каждая вершина xi помечается индексом . Конечной вершине приписываем
индекс 0 =0. Для остальных вершин предварительно полагаем i = (i ).
Ищем такую дугу (xi, xj), для которой i – j >l(uij), и заменяем индекс j индексом j’ = i + l(uij) < j. Продолжаем этот процесс замены индексов до тех пор, пока остается хотя бы одна дуга, для которой можно уменьшить j.
Если какую –то вершину можно пометить несколькими способами, то выбирается наименьшее значение.
Сформулируем правило для нахождения кратчайшего пути:
Пусть xn =a – начальная вершина с индексом n. Ищем вершину xp1, такую, что n – p1 = l(un,p1). Далее ищем вершину xp2, такую, что p1 – p2 = l(up1,p2) и т.д. до тех пор, пока не дойдем до конечной вершины.
Пример:
Найти кратчайший путь из вершины 6 в вершину 1.
Вершине 1 присваиваем индекс «0». Для остальных вершин полагаем i = .
Ищем дугу, для которой j – 1> l(xj,x1). Это дуги (x1, x2) и (x1, x3).
Приписываем вершинам 2 и 3 индексы 2’ = 1+ l(x0,x2) = 0 + 2 = 2; 3’=1+l(x0,x3)=0+9=9.
Далее ищем дуги, для которых j – 2 >l(xj, x2); j – 3 > l(xj, x3).
Вершинам 4, 5 приписываем индекс 4’ = 2 + l(x2, x4) = 2 + 3 = 5, 5’=2+l(x2, x5)=2 + 3 = 5. Вершине 6 приписываем индекс 6’=3+l(x3,x6)=9+7=16.
Вершину 6 можно пометить из вершины 4, так как 6 – 4 > l(x4, x6);
16–5 > 6 ; 6’ = 4 + l(x4, x6) = 5 + 6 = 11.
Находим кратчайший путь. Индекс вершины 6 равен 11, значит, длина кратчайшего пути равна 11. Ищем вершину, для которой 6 – j = l(x6, xj). Это вершина 4: 11-6=5. Значит, первой промежуточной вершиной на пути 6 – 1 является вершина 4. Далее ищем вершину, для которой 4 – j = l(x4, xj). Это вершина 2: 5 – 2 = 3. И так далее, пока не дойдем до вершины 1. Получаем кратчайший путь из вершины 6 в вершину 1: 6 – 4 – 2 – 1, длина которого равна индексу вершины 6, т.е. равна 11.
Алгоритм Флойда.
Он работает следующим образом. Первоначально за длину dik кратчайшей цепи между двумя произвольными узлами i и k (между которыми могут быть и промежуточные узлы) принимают длину дуги (i,k), соединяющей эти узлы. Затем последовательно проверяют всевозможные промежуточные узлы, расположенные между i и k . Если длина цепи, проходящей через некоторый промежуточный узел, меньше текущего значения dik , то переменной dik присваивают новое значение ; если
dik > dij + djk , то значение dik заменяют значением (dij + djk). Такую процедуру повторяют для всевозможных пар узлов, пока не будут получены все значения d*ik.
В алгоритме Флойда начальным значением переменной dik является величина Cik, а затем данная оценка последовательно улучшается до тех пор, пока не будет найдена кратчайшая цепь между узлами i и k .
Алгоритм Флойда позволяет решать задачу о многополюсной кратчайшей цепи (пути) для сети из n узлов за n итераций. Обозначим символом djik оценку длины кратчайшей цепи из узла i в узел k , полученную на j-той итерации, и рассмотрим следующую задачу.
ЗАДАЧА: Необходимо соединить восемь объектов многополосной цепью, причем один из объектов (№8) может быть только направляющим информацию, а остальные могут и направлять, и получать информацию без каких-либо ограничений.
На рисунке каждый объект представлен узлом, а каждая линия дугой.
Ориентированные дуги соответствуют распределительным звеньям, которые могут быть использованы для передачи информации только в указанном направлении. Числа, приписанные дугам, соответствуют расстоянию между объектами.
Требуется найти для каждого объекта кратчайшие пути, связывающие его с другими объектами.
Часть выполненной работы
Воспользуемся алгоритмом Флойда. Поскольку n=8, то число итераций в алгоритме будет 8. На каждой итерации строит матрицу длин кратчайших путей, которые содержат текущие оценки длин кратчайших цепей Dj = ||djik||, где D0=||Cik||, и маршрутов Rj, служащую для нахождения промежуточных узлов ( если таковые имеются ) кратчайших цепей. На j-той итерации Rj=||rjik||, где rjik -первый промежуточный узел кратчайшей цепи из i в k, выбираемый среди множества { 1 , 2 , … , j }, i = j = k, R0=||r0ik||, где r0ik = k.
Узел rjik может быть получен из следующего соотношения:
Узел rjik может быть получен из следующего соотношения:
Строим матрицу длин кратчайших цепей D и матрицу маршрутов R , отсутствие связи помечаем знаком .
left0left0left0left01 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 0 9 31 1 2 3 4 5 6 7 8
2 9 0 2 72 1 2 3 4 5 6 7 8
3 2 0 2 4 8 63 1 2 3 4 5 6 7 8
4 3 2 054 1 2 3 4 5 6 7 8
5 7 40 105 1 2 3 4 5 6 7 8
6 810 0 76 1 2 3 4 5 6 7 8
7 6 57 07 1 2 3 4 5 6 7 8
8 9 12 10 0 8 1 2 3 4 5 6 7 8
Итерация 1:
Выбираем базовый узел j = 1. В матрице D0 вычеркиваем j – ю строку (базовую) строку и j – ый (базовый) столбец. Чтобы определить, приведет ли использование узла 1 к более коротким цепям, необходимо исследовать элементы матрицы D0 с помощью трехместной операции:
djik = min[dj-1ik;dj-1ij+dj-1jk],.
Если dj-1ij = , т.е. j – ый элемент базового столбца равен , то djik=dj-1ik.
Если dj-1jk=, т.е. j – ый элемент базовой строки равен , то djik=dj-1ik.
Если dj-1ik и одно из двух значений dj-1ij или dj-1jk превосходит dj-1ik, то замену также производить не следует.
Столбцы 3, 5, 6, 7, 8 содержат элементы, равные и принадлежащие базовой строке, а строки 3, 5 – 8 содержат элементы, равные и принадлежащие базовому столбцу, т.е. исследовать надо элементы (2, 2), (2, 4), (4, 2), (4, 4). Поскольку диагональные элементы можно не рассматривать, необходимо исследовать лишь оценки d024 и d042:
d124= min[d024;d021+d014]= min[;9+3]=12;
d142 = min[d042;d041+d012]= min[;3+9]=12.
Оценки d124 и d142 лучше оценок d024 и d042, поэтому они должны быть внесены в матрицу D1, а в матрице маршрутов R1 надо положить r124=1;r142 = 1.
Итерация 2.
Выбираем узел 2 как базовый, т.е. проверяем, приведет ли его использование к более коротким цепям. Вычеркиваем в матрице D1 вторую строку и второй столбец. Вычеркиваем также столбцы 6,7,8, так как они содержат элементы, равные , принадлежащие базовой строке, и строки 6,7,8, так как они содержат элементы, равные , принадлежащие базовому столбцу. Исключаем также диагональные элементы. Остается исследовать элементы (1,3); (1,4); (1,5); (3,1); (3,4); (3,5); (4,1); (4,3); (4,5); (5,1); (5,3); (5,4). Здесь улучшены могут быть только оценки d113, d115, d131, d145, d151, d154, равные .
d213=min[d113; d112+d123]=min[;9+2]=11;
d231=min[d131; d132+d121]=min[;2+9]=11;
d215=min[d115; d112+d125]=min[;9+7]=16;
. . .
Таким образом, r213 = r231 = r215 = r245 = r251 = r254 =2; остальные элементы r2ij остаются без изменений. Новые матрицы имеют вид:
Аналогично получаем матрицы Dj и Rj, j = 3,…,8. Матрицы Dj и Rj, j=5,6,7,8, остаются без изменений. Следовательно, оптимальное решение соответствует матрицам D5 и R5, определяющим и оптимальное расстояние для передачи между объектами, и последовательность передачи информации.
Алгоритм Дейкстра
Опишем метод решения задачи о кратчайшем пути на взвешенном графе. Пусть …
MrFavor 5.0
Имеется большой опыт в написании рефератов, эссе и рецензий по следующим дисциплинам: психология, менеджмент, маркетинг, философия, социология и управление персоналом.
На странице представлен фрагмент
Уникализируй или напиши новое задание с помощью нейросети
