Главная | Обратная связь | Поможем написать вашу работу!

Задача нахождения кратчайшего пути

Данная задача состоит в определении в транспортной сети кратчайшего пути между заданными исходным пунктом и пунктом назначения. Такую модель можно использовать для описания разнообразных ситуаций, как показано далее.

Практические примеры задачи нахождения кратчайшего пути

Алгоритм нахождения кратчайшего пути

В этом разделе представлены два алгоритма для решения задачи нахождения кратчайшего пути как в сетях, имеющих циклы, так и в сетях, не имеющих циклов.

1. Алгоритм Дейкстры

2. Алгоритм Флойда

Алгоритм Дейкстры разработан для нахождения кратчайшего пути между заданным исходным узлом и любым другим узлом сети. Алгоритм Флойда более общий, поскольку он позволяет одновременно найти минимальные пути между любыми двумя узлами сети.

АЛГОРИТМ ДЕЙКСТРЫ. В процессе выполнения этого алгоритма при переходе от узла i к следующему узлу j используется специальная процедура пометки ребер. Обозначим через м, кратчайшее расстояние от исходного узла 1 до узла i, через d_ij — длину ребра (i,j). Тогда для узла j определим метку [u_j, i] следующим образом.

[u_j, i] = [u_i + d_ij, i], d_ij>=0

Метки узлов в алгоритме Дейкстры могут быть двух типов: временные и постоянные. Временная метка впоследствии может быть заменена на другую временную, если будет найден более короткий путь к данному узлу. Когда же станет очевидным, что не существует более короткого пути от исходного узла к данному, статус временной метки изменяется на постоянный.

Вычислительная схема алгоритма состоит из следующих шагов.

Шаг 0. Исходному узлу (узел 1) присваивается метка [0, —]. Полагаем i= 1.

Шаг i.

a) Вычисляются временные метки [u_i + d_ij, i] для всех узлов у, которые можно достичь непосредственно из узла i и которые не имеют постоянных меток. Если узел j уже имеет метку [u_j, k], полученную от другого узла k, и если и_i + d_ij < и_j тогда метка [и_j, k] заменяется на [u_i + d_ij, i].

b) Если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном случае выбирается метка [u_r, s] с наименьшим значением расстояния и_r среди всех временных меток (если таких меток несколько, то выбор произволен). Полагаем i = r и повторяем шаг i.

Пример 1

На рис. 6.13 показана транспортная сеть, состоящая из пяти городов (расстояния между городами (в милях) приведены возле соответствующих дуг сети). Необходимо найти кратчайшие расстояния от города 1 (узел 1) до всех остальных четырех городов.

Шаг 0. Назначаем узлу 1 постоянную метку [0, —].

Шаг 1. Из узла 1 можно достичь узлов 2 и 3. Вычисляем метки для этих узлов, в результате получаем следующую таблицу меток.

Узел Метка Статус метки

1 [0,-] Постоянная

2 [0+100,1]=[100,1] Временная

3 [0+30,1]=[30,1] Временная

Среди узлов 2 и 3 узел 3 имеет наименьшее значение расстояния (u₃ = 30). Поэтому статус метки этого узла изменяется на "постоянная".

Шаг 2. Из узла 3 (последнего узла с постоянной меткой) можно попасть в узлы 4 и 5. Получаем следующий список узлов.

Узел Метка Статус метки

1 [0,-] Постоянная

2 [100,1] Временная

3 [30,1] Постоянная

4 [30+10,3]=[40,3] Временная

5 [30+60,3]=[90,3] Временная

Временный статус метки [40, 3] узла 4 заменяется на постоянный (u₄ = 40).

Шаг 3. Из узла 4 можно достичь узлов 2 и 5. После вычисления меток получим следующий их список.

Узел Метка Статус метки

1 [0,-] Постоянная

2 [40+15,4]=[55,4] Временная

3 [30,1] Постоянная

4 [40,3] Постоянная

5 [90,3] или [40+50,4]=[90,4] Временная

Временная метка [100, 1], полученная узлом 2 на втором шаге, изменена на [55, 4]. Это указывает на то, что найден более короткий путь к этому узлу (проходящий через узел 4). На третьем шаге узел 5 получает две метки с одинаковым значением расстояния u₅ = 90.

Шаг 4. Из узла 2 можно перейти только в узел 3, но он уже имеет постоянную метку, которую нельзя изменить. Поэтому на данном шаге получаем такой же список меток, как и на предыдущем шаге, но с единственным изменением: метка узла 2 получает статус постоянной. С временной меткой остается только узел 5, но так как из этого узла нельзя попасть ни в какой другой, процесс вычислений заканчивается.

Алгоритм позволяет проводить вычисления непосредственно на схеме сети, как показано на рис. 6.14.

Кратчайший маршрут между узлом 1 и любым другим узлом определяется начиная с узла назначения путем прохождения их в обратном направлении с помощью информации, представленной в постоянных метках. Например, для определения кратчайшего маршрута между узлами 1 и 2 получаем такую обратную последовательность узлов

(2) -> [55, 4] -> (4) -> [40, 3] -> (3) -> [30, 1] -> (1). Таким образом, получаем путь 1 -> 3 —> 4 —> 2 общей длиной 55 миль.

Упражнения к лабораторной № 2

1. На рис. 6.15 показана транспортная сеть, соединяющая восемь городов, и расстояния между ними. Найдите кратчайшие маршруты между следующими городами.

a) Между городами 1 и 8.

b) Между городами 1 и 6.

c) Между городами 4 и 8.

d) Между городами 2 и 6.

2. Найдите кратчайшие пути между узлом 1 и всеми остальными узлами сети, представленной на рис. 6.16.

3. Найдите оптимальное решение задачи из упр. 6.4,а(1).

4. Найдите оптимальное решение задачи из упр. 6.4,а(2).

5. Найдите оптимальное решение задачи из упр. 6.4,а(4).

Алгоритм Флойда

Найдем для сети, показанной на рис. 6.19, кратчайшие пути между любыми двумя узлами. Расстояния между узлами этой сети проставлены на рисунке возле соответствующих ребер. Ребро (3, 5) ориентированно, поэтому не допускается движение от узла 5 к узлу 3. Все остальные ребра допускают движение в обе стороны.

Шаг 0. Начальные матрицы D₀ и S₀ строятся непосредственно по заданной схеме сети. Матрица D₀ симметрична, за исключением пары элементов d₃₅ и d₅₃, где d₅₃ ⁼ °° (поскольку невозможен переход от узла 5 к узлу 3).

Шаг 1. В матрице D0 выделены ведущие строка и столбец (k = 1). Двойной рамкой представлены элементы d23 и d32, единственные среди элементов матрицы d0, значения которых можно улучшить с помощью треугольного оператора. Таким образом, чтобы на основе матриц D0 и S0 получить матрицы d1 и S1, выполняем следующие действия.

1. Заменяем d23 на d21 + d13 = 3 + 10 = 13 и устанавливаем s23 = 1.

2. Заменяем d32 на d31 + d12 = 10 + 3 = 13 и устанавливаем s32 = 1.

Матрицы d1 и S1 имеют следующий вид.

Шаг 2. Полагаем k = 2; в матрице d1 выделены ведущие строка и столбец. Треугольный оператор применяется к элементам матриц D1 и S2, выделенным двойной рамкой. В результате получаем матрицы D2 и S2.

Шаг 3. Полагаем k = 3; в матрице D2 выделены ведущие строка и столбец. Треугольный оператор применяется к элементам матриц D2 и S2, выделенным двойной рамкой. В результате получаем матрицы D3 и S3.

Шаг 5. Полагаем k = 5, ведущие строка и столбец в матрице D4 выделены. Никаких действий на этом шаге не выполняем; вычисления закончены.

Конечные матрицы D4 и S4 содержат всю информацию, необходимую для определения кратчайших путей между любыми двумя узлами сети. Например, кратчайшее расстояние между узлами 1 и 5 равно d15 = 12.

Для нахождения соответствующих маршрутов напомним, что сегмент маршрута (i,j) состоит из ребра (i,j) только в том случае, когда si,j =j. В противном случае узлы i и j связаны, по крайней мере, через один промежуточный узел. Например, поскольку s15 = 4 и s45 = 5, сначала кратчайший маршрут между узлами 1 и 5 будет иметь вид 1 -> 4 —> 5. Но так как s14<>4, узлы 1 и 4 в определяемом пути не связаны одним ребром (но в исходной сети они могут быть связаны непосредственно). Далее следует определить промежуточный узел (узлы) между первым и четвертым узлами. Имеем s14 = 2 и s24 = 4, поэтому маршрут 1 —> 4 заменяем 1 —> 2 —> 4. Поскольку s12 = 2 и s24 = 4, других промежуточных узлов нет. Комбинируя определенные сегменты маршрута, окончательно получаем следующий кратчайший путь от узла 1 до узла 5: 1 —> 2 —> 4 —> 5. Длина этого пути равна 12 милям.

Упражнения

1. В задаче из примера 6.4-5 определите кратчайшие пути между следующими парами узлов.

a) От узла 5 к узлу 1.

b) От узла 3 к узлу 5.

c) От узла 5 к узлу 3.

d) От узла 5 к узлу 2.

2. Примените алгоритм Флойда к сети, показанной на рис. 6.20. Заметьте, что ребра (7, 6) и (6, 4) ориентированы. Определите кратчайшие пути между следующими парами узлов.

a) От узла 1 к узлу 7.

b) От узла 7 к узлу 1.

c) От узла 6 к узлу 7.

3. Телефонная компания обслуживает шесть удаленных друг от друга районов, которые связаны сетью, показанной на рис. 6.21. Расстояния на схеме сети указаны в милях. Компании необходимо определить наиболее эффективные маршруты пересылки сообщений между любыми двумя районами.

⇐ Предыдущая 123 Следующая ⇒