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

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

3.8.    динамическое программирование на ориентированных графах

Как было показано в предыдущем разделе, общий метод ДП решения задачи о кратчайшем пути для неориентированных графов с незначительными видоизменениями может быть применен и для решения данной задачи на орграфах, причем наличие ориентации ребер сокращает число рассматриваемых вариантов при расчете оценок Е(у). В настоящем разделе мы покажем, что наличие ориентации графа позволяет в ряде случаев упростить общий метод ДП и при расчетах обойтись вообще без использования промежуточных оценок Е{у). Кроме того, как мы увидим ниже в разд. 3.10, ориентация позволяет распространить метод ДП и на задачу о максимальном пути, чем достичь более полного согласия с классическим методом ДП оптимизации многошаговых процессов, рассмотренным в гл. 1.

Изложим метод ДП решения задачи о кратчайшем пути для ориентированных графов. Для этого введем следующие обозначения. Пусть v є V — некоторая вершина орграфа G(V,R). Обозначим через V+(t>) множество вершин, следующих за вершиной v, а через V-(v) — множество вершин, предшествующих вершине V.

V+(v) = {го є V I    существует дуга v —> ги}, V-(v) = {u є V I    существует дуга u —> v}.

 

Структура множеств V+(v) и V-(v) может быть проиллюстрирована рис. 3.17. В соответствии с принятыми обозначениями все исходящие из вершины v дуги заходят в вершины множества V+(v), а все заходящие в вершину v дуги исходят из вершин множества V-{v). На данном рисунке для упрощения все дуги направлены слева направо; при этом множество V-(v) располагается слева, а множество V+ (v) — справа от вершины v. Конечно, в реальных орграфах такое упрощенное расположение вершин может нарушаться, но общие определения остаются справедливыми.

Как и выше, будем обозначать через L(v) длину кратчайшего пути из вершины v в конечную вершину vKOH. Значение функции L(v), не известное еще для некоторой вершины v Є V, может быть непосредственно вычислено в том случае, когда значения L(w) уже определены для всех w Є V+(v). При этом имеет место следующая основная расчетная формула:

L(v) =   min {d(v     го) + L(w)}. (1)

и;ЄУ+(г>)

В данной формуле —как и диктует логика метода ДП —выделяется первый шаг от текущей вершины v к конечной вершине г>кон, проводимый по дуге v —> го; при этом длины L(w) кратчайших путей от последующих вершин го Є V+(v) являются уже известными. Расчеты начинаются с конечной вершины и соответствующего условия L(vKOH) = 0, а Ь(г>нач) равно длине искомого кратчайшего пути и подлежит определению.

Приведенная формула выражает полный аналог классического принципа оптимальности, а ее структура близка к структуре основного функционального уравнения (*) Р. Бел л мана. Функция L(v) является аналогом семейства функций Ві(хі) в принципе оптимальности Р. Белл-мана, а роль управления играет выбор дуги, исходящей из вершины v. На данной формуле и основывается метод ДП решения задачи о кратчайшем пути на орграфах.

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

Рис. 3.18

 

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

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

^нач = 1)     ^кон = 2.

Очевидно, что данный орграф является сетью с одним истоком и двумя стоками — вершинами 2 и 3. Искомый кратчайший путь в данной задаче определяется однозначно и имеет вид 1 —*• 2 независимо от длин дуг орграфа. При этом для вычисления L(l) в соответствии с предлагаемой формулой необходимо знать не только значение L(2) = 0, но и значение L(3), вычислить которое мы никак не можем, поскольку вершина 3, принадлежащая V+(l), не содержит последующих.

Следовательно, для рассмотрения более общих ситуаций в предлагаемый метод расчета необходимо внести определенные уточнения. Именно, в ходе вычисления функции L(v) следует исключать из рассмотрения те «лишние» дуги, через которые заведомо не может проходить кратчайший путь из начальной вершины в конечную. Эти дуги можно отмечать знаком «х» на самом графе или в таблице.

С учетом данного замечания в рассматриваемом орграфе дугу 1 —*• 3 можно исключить из рассмотрения по той причине, что ее конечная вершина 3 не имеет последующих вершин и, следовательно, ни один путь из 1 в 2 не может проходить через 3. Соответственно, по основной формуле (1) получаем

ЦІ) = d(l — 2) + L(2) = d(l 2),

т. е. длина кратчайшего пути равна длине дуги 1 —► 2, что уже установлено выше.

Как видно из рассмотренного примера, исключение из рассмотрения отдельных дуг приводит к «сужению» множества v+(v), по которому вычисляется минимум в общей формуле (1). В отдельных случаях может оказаться, что для начальной вершины г>нач исключены из рассмотрения все исходящие дуги, т. е. множество V+(uHa4) «сужено» до пустого множества. Это означает, что задача решения не имеет. Так будет, например, если из рассмотренного только что орграфа удалить дугу 1 —> 2.

Таким образом, решение задачи о кратчайшем пути на орграфах методом ДП сводится к двум основным действиям:

исключению «лишних» дуг;

применению основной расчетной формулы (1).

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

Для примера обратимся еще раз к решению задачи о кратчайшем пути для орграфа, представленного на рис. 3.16, где

^нач = 5,     ^кон 3.

Очевидно, что этот орграф не является сетью, поскольку содержит контур

1->5->4->1.

Решение проведем по только что изложенному варианту метода ДП для орграфов. Полагая

L(3) = О,

немедленно получим, что непосредственное применение основной расчетной формулы не позволяет вычислить значение функции L(v) ни для одной вершины орграфа. Следовательно, необходимо по возможности исключить «лишние» дуги. Действительно, из графа можно удалить все входящие в вершину 2 дуги 3 —> 2, 5 —► 2, 7 —> 2, поскольку 2 не имеет исходящих дуг и не может лежать на пути, идущем к конечной вершине 3. Более того, дугу 1 5, входящую в начальную вершину 5, также можно исключить из рассмотрения, поскольку маршрут вида

•Унач = 5->...->1->5->... содержит повторяющуюся вершину 5 и путем не является. После исключения указанных дуг можно провести следующую цепочку расчетов:

L(l) = d(l -> 3) + L(3) = 5 + 0 = 5, L(4) = d(4 1) + ЦІ) = 4 + 5 = 9, L(6) = d(6     4) + L(4) = 1 + 9 = 10, отмечая соответственно дуги 1 -» 3, 4 -> 1 и 6 -» 4. Далее приходится выбирать из нескольких вариантов:

L(7) = min{d(7^4) + L(4);d(7^6) + L(6)} =

= min {4 + 9; 2 + 10} = min {13; 12} = 12, L(5) = min {d(5     3) + L(3); d(5 ^ 4) + L(4); d(5 -> 7) + L(7)} =

= min {20 + 0; 8 + 9; 3 + 12} = min {20; 17; 15} = 15;

отмечаем при этом дуги 7 —► 6 и 5 —> 7, на которых достигаются минимумы. Таким образом, длина кратчайшего пути из 5 в 3 равна 15. Сам кратчайший путь имеет вид

5^7^6^4^1^3

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

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

Замечание 1. Решение данной задачи может быть оформлено и без проведения записи на графе с использованием соответствующей таблицы из разд. 3.7.

Замечание 2. Важно отметить, что существуют орграфы весьма простой структуры, не являющиеся сетями, для которых рассмотренный метод не приводит к решению задачи. В качестве примера рассмотрим орграф, представленный на рис. 3.19, в котором инач = А,

^кон = Е. Искомый кратчайший путь имеет вид

A^C^D^B^E,

а длина его равна 10. Применяя рассмотренный вариант метода ДП и полагая L(E) = 0, получим, что каждая из оставшихся вершин имеет хотя бы одну последующую вершину, для которой значение функции L еще не известно. При этом анализ структуры орграфа не позволяет исключить ни одной дуги: через каждую из них может проходить путь из А в Е. В данной ситуации можно поступить следующим образом:

применить общий метод ДП решения задачи с расчетом вспомогательных оценок (подобный случай детально рассмотрен выше в разд. 3.7);

провести более детальный анализ орграфа, учитывая не только его структуру, но и значения длин дуг (пример подобного анализа будет приведен далее в разд. 3.10 при рассмотрении задачи о максимальном пути).

Замечание 3. В рассмотренном варианте метода ДП расчеты функции L(v) ведутся, как и в классическом случае, в обратном порядке от конечной вершины к начальной. В то же время данный метод легко переформулировать таким образом, чтобы расчеты велись от начальной вершины к конечной; для некоторых задач такой способ представляется более естественным. В этом случае соответствующая расчетная формула может быть записана в виде

L'(v)=   min {L'(u) + d(u ->v)},

иЄУ- (v)

где через L'(v) обозначена длина кратчайшего пути из начальной вершины і>нач в вершину v, а значения L'(u) считаются известными для всех и Є V-(v). При этом L'(vBan) = 0, a L'(vKOH) равно длине искомого кратчайшего пути и подлежит определению. Конечно, возможность применения данной формулы для произвольных сетей может быть сопряжена с необходимостью исключения «лишних» дуг, как и в рассмотренных выше примерах.

 

Страница: | 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 |