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

Алгоритм нахождения максимального пути




 

При решении некоторых практических задач возникает необходимость поиска максимального пути (пути с наибольшей суммой длин дуг). Такая задача сводится к задаче нахождения минимального пути заменой знаков при длинах дуг (в матрице весов C) на противоположные. При этом необходимым является требование отсутствия в ориентированном графе контуров положительной длины.

Пример 3.16.

С помощью модифицированного алгоритма 3.1 найдем максимальный путь из верши­ны х 1 в вершину х 3 в графе, изображенном на рис. 3.11.

Рис. 3.11

Шаг 1. Введем число вершин графа n =5. Матрица весов этого графа после замены знаков при длинах дуг на противоположные имеет вид:

C = .

Шаг 2. Положим k = 0, l 1(0) = 0, l 2(0) = l 3(0) = l 4(0) = l 5(0) = . Эти значения занесем в первый столбец табл. 3.2.

Шаг 3.

k = 1.

l 1(1) = 0.

Равенство (3.1) для k = 1 имеет вид:

li (1) = { lj (0) + cji }.

l 2(1) = min { l 1(0) + c 12; l 2(0) + c 22; l 3(0) + c 32; l 4(0) + c 42; l 5(0) + c 52;} = min {0 – 1; ¥ + ¥; ¥ + ¥; ¥ + ¥; ¥ + ¥} = –1.

l 3(1) = min { l 1(0) + c 13; l 2(0) + c 23; l 3(0) + c 33; l 4(0) + c 43; l 5(0) + c 53;} = min {0 + ¥; ¥ – 8; ¥ + ¥; ¥ – 2; ¥ + ¥} = ¥.

l 4(1) = min { l 1(0) + c 14; l 2(0) + c 24; l 3(0) + c 34; l 4(0) + c 44; l 5(0) + c 54;} = min {0 + ¥; ¥ – 7; ¥ + ¥; ¥ + ¥; ¥ – 4} = ¥.

l 5(1) = min { l 1(0) + c 15; l 2(0) + c 25; l 3(0) + c 35; l 4(0) + c 45; l 5(0) + c 55;} = min {0 – 3; ¥ – 1; ¥ + 5; ¥ + ¥; ¥ + ¥} = –3.

Полученные значения li (1) занесем во второй столбец табл. 3.2. Убеждаемся, что второй столбец, начиная со второго элемента, совпадает с первой строкой матрицы весов, что легко объясняется смыслом величин li (1), которые равны длине минимального пути из первой вершины в i -ую, содержащего не более одной дуги.

k = 2.

l 1(2) = 0.

Равенство (3.1) для k = 2 имеет вид:

li (2) = { lj (1) + cji }.

l 2(2) = min {0 – 1; –1 + ¥; ¥ + ¥; ¥ + ¥; –3 + ¥} = –1.

l 3(2) = min {0 + ¥; –1 – 8; ¥ + ¥; ¥ – 2; –3 + ¥} = –9.

l 4(2) = min {0 + ¥; –1 – 7; ¥ + ¥; ¥ + ¥; –3 – 4} = –8.

l 5(2) = min {0 – 3; –1 – 1; ¥ + 5; ¥ + ¥; –3 + ¥} = –3.

Полученные значения li (2) занесем в третий столбец табл. 3.2. Величины li (2) равны длине минимального пути из первой вершины в i -ую, содержащего не более двух дуг.

k = 3.

l 1(3) = 0.

Равенство (3.1) для k = 3 имеет вид:

li (3) = { lj (2) + cji }.

l 2(3) = min {0 – 1; – 1 + ¥; – 9 + ¥; –8 + ¥; – 3 + ¥} = – 1.

l 3(3) = min {0 + ¥; – 1 – 8; – 9 + ¥; –8 – 2; – 3 + ¥} = – 10.

l 4(3) = min {0 + ¥; – 1 – 7; – 9 + ¥; –8 + ¥; – 3 – 4} = – 8.

l 5(3) = min {0 – 3; – 1 – 1; – 9 + 5; –8 + ¥; – 3 + ¥} = – 4.

Полученные значения li (3) занесем в четвертый столбец табл. 3.2. Величины li (3) равны длине минимального пути из первой вершины в i -ую, содержащего не более трех дуг.

k = 4.

l 1(4) = 0.

Равенство (3.1) для k = 4 имеет вид:

li (4) = { lj (3) + cji }.

l 2(4) = min {0 – 1; – 1 + ¥; – 10 + ¥; – 8 + ¥; – 4 + ¥} = – 1.

l 3(4) = min {0 + ¥; – 1 – 8; – 10 + ¥; – 8 – 2; – 4 + ¥} = – 10.

l 4(4) = min {0 + ¥; – 1 – 7; – 10 + ¥; – 8 + ¥; – 4 – 4} = – 8.

l 5(4) = min {0 – 3; – 1 – 1; – 10 + 5; – 8 + ¥; – 4 + ¥} = – 5.

Полученные значения li (4) занесем в пятый столбец табл. 3.2. Величины li (4) равны длине минимального пути из первой вершины в i -ую, содержащего не более четырех дуг.

Таблица 3.2

i (номер вершины) li (0) li (1) li (2) li (3) li (4)
  0 0 0 0 0 ¥ – 1 – 1 – 1 1 ¥ ¥ – 9 – 10 – 10 ¥ ¥ – 8 – 8 – 8 ¥ – 3 –3 – 4 – 5

Заменив в табл. 3.2 отрицательные числа положительными, получим таблицу индексов максимальных путей (табл. 3.3). При этом li (k) определяет длину максимального пути из первой вершины в i -ую, содержащего не более k дуг.

Таблица 3.3

i (номер вершины) li (0) li (1) li (2) li (3) li (4)
  0 0 0 0 0 ¥ 1 1 1 1 ¥ ¥ 9 10 10 ¥ ¥ 8 8 8 ¥ 3 3 4 5

Шаг 5. Восстановление максимального пути производится по тому же правилу, что и для минимального пути.

Длина максимального пути равна 10. Этот путь состоит из трех дуг, т. к. li (3) = li (4) = 10. Поэтому в соотношении (3.2) будет выполнено, начиная с n – 1.

Учитывая это замечание, для последней вершины x 3предшествующую ей вершину xr определим из соотношения (3.2) полученного при s =3:

lr (2) + cr 3 = l 3(3), (3.7)

xr Î G- 1(x 3), где G- 1(x 3) - прообраз вершины x 3.

G- 1(x 3)= { x 2, x 4}.

Подставим в (3.7) последовательно r = 2 и r = 4, чтобы определить, для какого r это равенство выполняется:

l 2(2) + c 23 = 1 + 8 ¹ l 3(4) = 10,

l 4(2) + c 43 = 8 + 2 = l 3(4) = 10.

Таким образом, вершиной, предшествующей вершине x 3, является вершина x 4.

Для вершины x 4предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =4:

lr (1) + cr 4 = l 4(2), xr Î G- 1(x 4), (3.8)

где G- 1(x 4) - прообраз вершины x 4.

G- 1(x 4)= { x 2, x 5}.

Подставим в (3.8) последовательно r = 2, r = 3 и r = 5, чтобы определить, для какого r это равенство выполняется:

l 2(1) + c 24 = 1 + 7 = l 4(3) = 8,

l 5(1) + c 54 = 3 + 4 ¹ l 4(3) = 8,

Таким образом, вершиной, предшествующей вершине x 4, является вершина x 2.

Для вершины x 2предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =2:

lr (0) + cr 2 = l 2(1), xr G- 1(x 2), (3.9)

где G- 1(x 2) - прообраз вершины x 2.

G- 1(x 2)= { x 1}.

Подставим в (3.9) r = 1, чтобы определить, выполняется ли это равенство:

l 1(1) + c 12 = 0 + 1 = l 2(1) = 1.

Таким образом, вершиной, предшествующей вершине x 2, является вершина x 1.

Итак, найден максимальный путь – x 1, x 2, x 4, x 3, его длина равна 10.

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...