Имя материала: Динамическое программирование в экономических задачах

Автор: Лежнёв А. В.

3.7.    задача о кратчайшем пути на ориентированных графах

Постановка и методы решения задачи о кратчайшем пути на оргра фах полностью аналогичны ситуации для неориентированных графов Пусть G(V, R) — ориентированный граф. Будем считать, что каждоі дуге г орграфа поставлено в соответствие некоторое неотрицательно число d(f) > 0, называемое длиной или весом дуги. Пусть последова тельность дуг fi, Г2, ■ ■ • , rk образует путь. Длиной пути fi, г і,..., f) называется сумма

d{n) + d(r2) + ... + d(rk)

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

Задача о кратчайшем пути на орграфах может иметь единствен ное решение, несколько различных решений или не иметь решениі вообще; при этом под решением задачи понимается сам кратчайшиі путь и его длина. Конечно, длина кратчайшего пути при условиі его существования определяется однозначно. Отметим, что наличи< ориентации очевидным образом уменьшает число рассматриваемые вариантов путей и снижает трудоемкость решения задачи.

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

методом перечисления путей;

методом ДП на графе;

с помощью алгоритма Дийкстры, упоминавшегося выше по тек сту и представляющего, по существу, один из вариантов ме тода ДП.

Рассмотрим указанные методы решения на примере орграфа, изоб раженного на рис.3.16; в котором начальной является вершина 5, ко нечной — вершина 3. (На данном рисунке уже приведены результата расчетов по методу ДП.)

1. Рассмотрим метод перечисления путей. В рассматриваемом^ при мере вершины орграфа естественно упорядочить по их номерам. Каї и для неориентированных графов, на каждом шаге алгоритма решенш задачи имеется некоторый построенный текущий путь

^нач = 1>[0] ->• 1>[i] ->...—> ЬЩ

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

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

 

Текущий путь

Длина пути

5^2

-

5^3

20

5^4^1^3

17

5-*4^1

-

5^4

-

5^7^4^1^3

16

5^7^4^1

 

5^7^4

-

5-*7^6^4^1^3

15

5^7^6^4-*1

-

5^7^6^4

-

5^7^6

-

5^7

-

5

-

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

5^7^6^4^1^3,

а его длина равна 15.

2. Рассмотрим метод ДП решения поставленной задачи. Отличие его от метода решения задачи для неориентированных графов заключается лишь в том, что при расчете оценок рассматриваются незанятые вершины, не просто смежные с занятыми, а предшествующие им с учетом ориентации дуг. Проведем решение задачи о кратчайшем пути для заданного на рис. 3.16 орграфа методом ДП, ведя запись на самом графе. Напомним, что через L(y) обозначается длина кратчайшего пути из вершины v в конечную вершину, а через E(v) — оценка длины кратчайшего пути (см. разд. 3.4).

Полагаем L(3) = 0, ставим 0 около вершины 3 и объявляем данную вершину занятой, а все остальные — свободными.

Поскольку начальная вершина 5 не является занятой, то приступаем к расчету оценок незанятых вершин. Для занятой вершины 3 предшествующими являются вершины 1 и 5, причем обе они свободны. Вычисляем оценки для этих вершин:

Е(1) = d(l -> 3) + L(3) = 5 + 0 = 5, Е(5) = d(5 -> 3) + L(3) = 20 + 0 = 20.

Полученные значения записываем на графе около вершин 1 и 5, которые переходят в группу пробных вершин. Отмечаем (например, короткими стрелками) дуги 1 —► 3 и 5 —► 3. Из двух пробных вершин 1 и 5 значение оценки для вершины 1 минимально и равно 5. Полагаем

ЦІ) = Е(1) = 5,

отмечаем жирным шрифтом данное значение на графе я объявляем вершину 1 занятой.

Начальная вершина 5 не является занятой, поэтому продолжаем расчет оценок. Занятыми в настоящий момент являются вершины 1 и 3, а предшествующими им незанятыми служат вершины 4 и 5. При этом вершина 5 имеет оценку, исходящая дуга 5 —> 3 уже учтена выше и не требует повторного рассмотрения. Вершина 4 является свободной, а дуга 4 —> 1 еще не рассматривалась. Вычисляем оценку для этой вершины:

Я(4) = d(4 -> 1) + Ці) = 4 + 5 = 9.

Полученное значение записываем на графе около вершины 4. Из двух пробных вершин 4 и 5 минимальное значение 9 оценка принимает для вершины 4. Полагаем

L(4) = Я(4) = 9,

отмечаем жирным шрифтом данное значение на графе и объявляем вершину 4 занятой. Отмечать стрелкой дугу 4 —> 1 нет необходимости, поскольку из вершины 4 исходит только одна эта дуга, и неоднозначности возникнуть не может.

Начальная вершина 5 еще не стала занятой, поэтому продолжаем расчет оценок. Занятыми в настоящий момент являются вершины 1,3,4, предшествующими им незанятыми служат вершины 5,6, 7, причем вершины 6 и 7 свободны. Вычисляем оценки для этих вершин:

Е(6) = d(6 -> 4) + L(4) = 1 + 9 = 10, Е(7) = d(7 -> 4) + L(4) = 4 + 9 = 13,

записываем полученные значения на графе и переводим их в число пробных вершин. Отмечаем стрелкой дугу 7 —> 4 (отмечать дугу 6 —> 4 нет необходимости, поскольку из вершины 6 исходит только одна эта дуга). Для вершины 5 уже известна оценка Е(5) = 20, рассчитанная ранее; сейчас эту оценку необходимо откорректировать, поскольку с момента ее вычисления появилась новая занятая вершина 4, следующая за 5. Вычисляем

m = d(5 -» 4) + L(4) = 8 + 9 = 17.

Поскольку m < Е(5), то полагаем Е(5) — 17, и ранее установленную на дуге 5 —> 3 стрелку переносим на дугу 5 —> 4. Полученные значения оценок записываем на графе около соответствующих вершин. Из пробных вершин 5, 6, 7 минимальное значение 10 оценка принимает для вершины 6. Полагаем

L(6) = E(Q) = 10,

отмечаем жирным шрифтом данное значение на графе и объявляем вершину 6 занятой.

Начальная вершина 5 по прежнему не стала занятой. Занятыми являются вершины 1, 3, 4, 6, предшествующими им незанятыми—вершины 5 и 7. Исходящие из 5 дуги уже учтены ранее.

Вершина 7 имеет оценку Е(7) = 13, причем дуга 7 —> 6 еще не рассматривалась. Корректируем оценку, вычисляя

m = d(7 -> 6) + L(6) = 12.

В ходе корректировки оценка уменьшается, поэтому полагаем Е{7) = 12, ранее установленная на дуге 7 —>• 4 стрелка переносится на дугу 7 —> 6. Полученные значения оценки записываем на графе. Из пробных вершин 5 и 7 минимальное значение 12 оценка принимает для вершины 7. Полагаем

Ц7) = Е(7) = 12,

отмечаем жирным шрифтом данное значение на графе и объявляем вершину 7 занятой.

Начальная вершина 5 все еще не стала занятой, но имеет новую последующую занятую вершину 7. Корректируем оценку:

m = d(5 -> 7) + ЦТ) = 15.

Поскольку m < Е(5) = 17, то полагаем -Е(5) = 15, и ранее установленную на дуге 5 —> 4 стрелку переносим на дугу 5 —> 7. Полученное значение оценки записываем на графе. В настоящий момент имеет оценку только вершина 5, а вершина 2 является свободной. Полагаем

ЦЪ) = Е(Ъ) = 15,

отмечаем жирным шрифтом данное значение на графе и объявляем вершину 5 занятой.

Начальная вершина 5 стала занятой, причем ЦЪ) = 15; следовательно, длина кратчайшего пути из 5 в 3 равна 15. Отметим, что в ходе расчетов вершина 2 осталась свободной, поскольку она не имеет последующих вершин и не может «получить оценки»; очевидно, что в силу отсутствия исходящих из 2 дуг не существует ни одного пути из 5 в 3, проходящего через вершину 2. Все проведенные выше расчеты составили этап, аналогичный этапу условной оптимизации классического метода ДП.

Построение кратчайшего пути представляет собой аналог этапа безусловной оптимизации. Кратчайший путь строится начиная с вершины 5 с использованием установленных на дугах стрелок, окончательное распределение которых представлено на рис. 3.16. На дугах б _> 4 и 4 —> 1 стрелок не установлено, но у вершин 6 и 4 имеется только по одной исходящей дуге, и направление движения в данном случае определяется однозначно. Таким образом, кратчайший путь составляется из дуг 5 —> 7, 7 —> 6, 6 —► 4, 4 —► 1, 1 —► 3, т. е. имеет вид

5^7^6->4->1->3.

Полученный результат, конечно, совпадает с результатом, полученным выше методом перечисления путей.

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

Замечание. В отдельных случаях решение рассматриваемой задачи методом ДП удобно проводить с использованием таблицы следующей структуры.

 

Вершина орграфа v

Последующая вершина и>

Длина дуги d(v —> и>)

Оценка d(v —> w)+L(u>)

Значение L(v)

 

 

 

 

 

 

В первом столбце v таблицы записываются все вершины орграфа; порядок записи может быть произвольный, но лучше упорядочивать вершины в соответствии с их обозначениями по номерам или по алфавиту. Для каждой вершины организуется свой строчный фрагмент. Во втором столбце го для каждой из вершин записываются все последующие вершины. Если таких нет, то это отмечается прочерком «— ». По существу, первые два столбца полностью задают структуру орграфа. В третьем столбце d{v —> го) записываются длины дуг от вершин, указанных в первом столбце, к последующим вершинам, указанным во втором столбце. Таким образом, первые три столбца содержат все исходные данные задачи. Заполнение первых трех столбцов представляет собой аналог предварительного этапа классического метода ДП.

Последующие два столбца отделяются от первых трех двойной вертикальной линией и уже непосредственно связаны с решением задачи. В четвертый столбец заносятся оценки E{v) = d(v —> w) + L(w), вычисляемые при условии, что значение функции L (го) уже известно для вершины го. В последний пятый столбец заносятся значения функции L(v), равные минимальному значению из соответствующих оценок. Строки, на которых достигается минимальное значение, отмечаются знаком «/» (это отметки играют роль стрелок, устанавливаемых в ходе решения на дугах орграфа, и являются аналогами условно-оптимальных значений управления из классического принципа оптимальности). Заполнение в ходе расчетов последних двух столбцов представляет собой аналог этапа условной оптимизации классического метода ДП.

Для рассматриваемого в качестве примера орграфа соответствующая таблица имеет следующий вид:

 

V

w

d(v —> w)

d(v —> u>) + L(u>)

L{v)

1

/3

5

5 + 0 = 5 [1]

5 [2]

 

5

6

 

 

2

3

2

9

 

0 [1]

4

1

4

4 + 5 = 9 [3]

9 [3]

5

2

10

 

15 [6]

 

3

20

20 + 0 = 20 [2]

 

 

4

8

8 + 9=17 [4]

 

 

/7

3

3 + 12 = 15 [8]

 

6

4

1

1 + 9 = 10 [5]

10 [4]

7

2

7

 

12 [5]

 

4

4

4 + 9 = 13 [6]

 

 

/6

2

2 + 10 = 12 [7]

 

 

Первые три столбца заполняются в соответствии с заданной структурой орграфа. Заполнение правой части таблицы начинается с записи 0 в пятый столбец для конечной вершины 3. Далее расчет и заполнение таблицы проводятся по описанным выше правилам, причем вычисления могут идти не по порядку строк, а вразброс. Для контроля логики решения и последовательности расчетов в приведенной таблице в квадратных скобках «[ ]» указаны порядковые номера вычисления оценок и значений функции L(v).

После завершения заполнения таблицы строится решение задачи с использованием установленных отметок. Длина кратчайшего пути является значением функции L для начальной вершины 5 и равна 15. Кратчайший путь строится следующим образом. Рассматриваем строчный фрагмент, отвечающий начальной вершине 5. В этом фрагменте знак «/» указывает на вершину 7. Следовательно, искомый путь содержит дугу 5 —► 7. Далее, рассматриваем строчный фрагмент, отвечающий вершине 7. В этом фрагменте знак «/» указывает на вершину 6.

Следовательно, искомый путь содержит дугу 7 —> 6. Продолжая аналогично, получим весь кратчайший путь

5^7^6^4^1^3.

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

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

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |