3.10. Построение максимального пути

Задача о максимальном пути уже упоминалась нами выше для неориен­тированных графов и заключается в поиске пути максимальной длины, соединяющего две заданные вершины взвешенного графа. Наличие сходства в постановках задач о максимальном и о кратчайшем пути еще не обусловливает полной аналогии в методах их решения. Как указано в разд. 3.3, задача о максимальном пути может быть решена методом перечисления путей, однако этот метод является исключительно гро­моздким и неэффективным. Представляется естественным применить для решения поставленной задачи метод ДП, детально разработанный для задачи о кратчайшем пути. Однако, как показано в разд. 3.4, не всякое формальное, механическое видоизменение метода ДП позво­ляет получить корректный алгоритм решения задачи о максимальном пути. В то же время классический принцип оптимальности Р. Беллмана и соответствующий метод ДП позволяет решать задачи управления многошаговыми процессами в равной мере как на максимум, так и на минимум; этот факт является дополнительным аргументом в пользу разработки надлежащего метода.

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

При изложении данного метода рассмотрим прежде всего наиболее общий и содержательный случай v_KOH ф v_HaH. Обозначим через M(v) длину максимального пути из вершины v в конечную вершину и_кон; если такого пути не существует, то функция М считается неопределенной для вершины v. При этом M(v_нач) равно длине искомого максимального пути и по условию задачи подлежит вычислению.

Пусть для некоторой вершины V & V значение М(у) еще не вы­числено в ходе решения задачи методом ДП, но известны значения M(w) для всех последующих вершин w е V+(v). В этом случае имеет место следующая основная расчетная формула:

M(v) = max {d(v -> w) + M(w)}.                                   (2)

weV+(t>)

Расчеты начинаются с условия

M{_Vkoh) = 0,                                                        (3)

которое по форме является аналогичным соответствующему условию для задачи о кратчайшем пути, но не столь очевидно и требует пояснения. Данное условие можно трактовать как требование не до­пускать зацикливания на начальном этапе построения максимального пути. Действительно, в общем случае при v ф v_KOH ни один путь из v в v_KOU не содержит контуров, проходящих через вершину и_ко„ (иначе вершина v_KOH повторялась бы более одного раза, что противоречило бы самому понятию пути). В то же время в орграфе может суще­ствовать непустой замкнутый путь ИЗ V = v_KOH в v_KOH, что приводит к соотношению M(v_KOls) > 0. Данная возможность вступает в проти­воречие с общим случаем, и для его устранения надлежит принять обсуждаемое условие (3).

Например, в орграфе, представленном на рис. 3.22, в котором длины всех дуг равны 1 и принято г>_Нач = A, v_KOH = В, существует кон-

тур В > С > Г) > В. Этот контур представляет собой максимальный путь (конечно, замкнутый), проходящий через вершину В и по длине равный 3. Но при решении задачи о максимальном пути необходимо исключать возможность составления таких контуров, поскольку пред­положение М(В) = 3 привело бы к ошибке: расчет по формуле (2) дает М(А) = 4, а соответствующий маршрут А—>В—>С—»Б—>В путем не является.

Как показывает уже рассмотренный выше пример орграфа на рис. 3.18, вычислить значение М( 1), действуя исключительно по формулам (2) и (3), невозможно, хотя, очевидно, путь 1 —> 2 из на­чальной вершины 1 в конечную вершину 2 является единственным и максимальным. Тем самым и при решении задачи о максималь­ном пути необходимо исключать из рассмотрения те «лишние» дуги, через которые заведомо не может проходить максимальный путь из на­чальной вершины в конечную. Для рассматриваемого орграфа такой дугой является дуга 1 —> 3, исключение которой предельно упрощает ситуацию и позволяет вычислить М( 1) = (1(1 —> 2).

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

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

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

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

Разберем ряд примеров, иллюстрирующих предложенный метод.

1. Рассмотрим орграф, изображенный на рис. 3.23, в котором на­чальной вершиной является В, а конечной —Е. Как легко проверить

с помощью алгоритма Фалкерсона, данный орграф является сетью с входом в вершине А и выходом в вершине G.

Полагая М(Е) = 0, немедленно приходим к невозможности непо­средственного применения основной расчетной формулы (2); для про­должения решения задачи попытаемся исключить некоторые дуги ор­графа. Дуги С -» G и F G могут быть исключены, поскольку вершина G не имеет последующих вершин. После их исключения вер­шина F «теряет» последующую вершину G, и из рассмотрения можно исключить дугу D —> F. При этом у вершины D остается только одна последующая вершина Е, что позволяет вычислить

М(D) = d(D —> Е) + М(Е) = 3 + 0 = 3, M (С) = d(С —> D) + М(D) = 2 + 3 = 5,

M (В) = max {d( В^С) + М( С); d( B->D) + M(D); d( B->E) + M(E)} = = max {1 + 5; 5 + 3; 7 + 0} = 8,

причем максимум в последнем равенстве достигается на дуге В —* D. Таким образом, длина максимального пути из В в Е равна 8, а сам максимальный путь имеет вид В —» D —» Е. Очевидно, что вычислять М(А) нет необходимости (хотя, конечно, это можно сделать).

2.               Рассмотрим задачу о максимальном пути для орграфа, пред­ставленного на рис. 3.16 и не являющегося сетью. Полагая М(3) = 0, немедленно приходим к необходимости исключения «лишних» дуг, по­скольку непосредственно основная формула (2) неприменима. Исклю­чив, как и для задачи о кратчайшем пути из разд. 3.8, дуги 3 —» 2, 5—>2, 7—>2 и 1—>5, можем провести следующую цепочку расчетов:

M(l) = d(l ->3) + Af(3) = 5, M(4) = d(4 -> 1) + М( 1) = 9, M(6) = d(6 -> 4) + М(3) = 10, M (7) = max {d( 7 4) + M( 4); d( 7 -» 6) + M(6)j =

= max {13; 12} = 13, M( 5) = max {d(5 -> 3) + M( 3); d(5 4) + M(4); d(5 7) + M(7)j = = max {20; 17; 16} = 20.

Соответствующим образом устанавливаются и отметки на дугах, используемые при построении искомого максимального пути. Оконча­тельно получаем, что максимальный путь из 5 в 3 состоит из одной дуги 5 —» 3 и имеет длину 20.

3.               Рассмотрим еще один пример и обратимся к решению задачи о максимальном пути для орграфа, представленного на рис. 3.24. Длины

всех дуг будем считать равными единице (они на графе явно не ука­заны). В качестве начальной вершины возьмем вершину 2, в качестве конечной — вершину 6.

Решение задачи зависит от наличия дуги 9 —>6, показанной на ри­сунке штриховой линией; рассмотрим оба случая. Расчет начинается с условия М(6) = 0. Изучая структуру орграфа, устанавливаем:

—               дугу 1 —* 2 можно исключить, поскольку вершина 2 является начальной, и любой маршрут, содержащий 1 —* 2, имеет вид

т. е. проходит через вершину 2 по меньшей мере два раза и путем не является;

—               дугу 3 —* 1 можно исключить, поскольку после исключения дуги 1 —> 2 вершина 1 не имеет последующих (образуется «тупик»);

—               по аналогичной причине можно исключить и дуги 2 —* 3 и 4 —> 3, поскольку вершина 3 больше не имеет последующих.

Таким образом, у вершины 4 остается лишь одна не исключенная исходящая дуга 4 —* 6. В соответствии с основной расчетной форму­лой (2) получаем:

М(4) = (1(4 6) + М(6) = 1 + 0=1;

при этом отмечается дуга 4 —* 6.

После определения М(4) можно пытаться вычислить значение функции М для начальной вершины 2, предшествующей вершине 4. Но у вершины 2 имеется еще одна последующая вершина 5, значение функции М в которой пока неизвестно. Соответственно необходимо или вычислить М(5), или исключить дугу 2 —> 5. Здесь начинает проявляться наличие дуги 9 —* 6.

Рассмотрим случай, когда дуга 9 —> 6 отсутствует. Изучая структуру графа, получаем:

—     дугу 7 —» 8 можно исключить, поскольку любой маршрут, содержащий 7 —> 8, обязательно проходит и по дугам 8 —> 9 и 9 —» 7, т. е. проходит через вершину 7 по меньшей мере два раза и путем не является;

—     по аналогичной причине можно исключить и дуги 8 —> 9 и 9 —* 7, хотя это и не обязательно;

—     дуги 5 —> 7 и 6 —> 7 можно исключить, поскольку после ис­ключения 7 —» 8 вершина 7 не имеет последующих (образуется «тупик»);

—     дугу 2 —> 5 также можно исключить, поскольку после ис­ключения дуги 5 —> 7 вершина 5 не имеет последующих.

Тем самым у вершины 2 остается лишь одна не исключенная ис­ходящая дуга 2 —» 4. В соответствии с основной формулой

М(2) = d(2 -» 4) + М(4) = 1 + 1 = 2;

при этом отмечается дуга 2 —> 4. Для данного случая решение завер­шено; максимальный путь строится с использованием установленных отметок и имеет вид 2 —> 4 —> 6, а длина его равна 2.

Рассмотрим случай, когда дуга 9 —> 6 присутствует в орграфе. В этом случае исключить дуги 7—>8и8—>9не удается. Однако дугу 9 —> 7 можно исключить, поскольку любой маршрут, содержащий 9 —> 7, обязательно проходит и по дугам 7 —» 8 и 8 —> 9, т. е. проходит через вершину 9 по меньшей мере два раза и путем не является. Тем самым у вершины 9 остается лишь одна не исключенная исходящая дуга 9 —> 6. По формуле (2) последовательно получаем:

М(9) = d(9 -> 6) + М(6) = 1+0 = 1, М(8) = d(8 -> 9) + М(9) = 1 + 1 = 2, М(7) = d(7 -> 8) + М(8) = 1 + 2 = 3, М(5) = d(5 -» 7) + М(7) = 1 + 3 = 4;

указанные дуги отмечаем. В настоящий момент у начальной вершины 2 имеются две последующие вершины 4 и 5 с известными значениями максимальных путей; в соответствии с основной формулой получаем:

М(2) = max{d(2 -» 4) +M(4);d(2 -» 5) + М(5)} = 5;

отмечаем дугу 2 —» 5, на которой достигается максимум. Для данного случая решение завершено; максимальный путь имеет вид 2—>5—>7—*8—>9—а длина его равна 5.

4. Для полноты изложения разберем пример задачи о максималь­ном пути, для которого простой анализ структуры орграфа без учета длин дуг не позволяет получить решения. Рассмотрим орграф, пред­ставленный на рис. 3.19, в котором принято и_нач = А, и_кон = Е; оче­видно, что данный орграф сетью не является. Полагая в соответствии с методом ДП М(Е) = 0, немедленно приходим к невозможности даль­нейшего применения основной формулы (2) ни для одной из остав­шихся вершин, поскольку у каждой из них есть последующая вершина с неизвестным еще значением функции М. Более того, ни одной дуги орграфа исключить из рассмотрения невозможно, поскольку через каж­дую из них проходит некоторый путь из А в Е, из которых любой — если, конечно, не принимать во внимание длины дуг — может быть максимальным. Таким образом, в данном случае структурный анализ оказывается слишком «грубым» и недостаточным для продолжения решения.

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

Множество всех путей из А в Е разобьем на следующие два непе­ресекающиеся подмножества:

1)               пути, проходящие по дуге В —* С;

2)               пути, не проходящие по дуге В —* С.

Найдем максимальные пути в каждом из подмножеств методом ДП.

Пути из первого подмножества проходят по дуге В —> С и, тем самым, не могут проходить по дугам С —> Б и Б —> В (иначе путь со­держал бы контур, что невозможно по определению). Следовательно, при расчете максимального пути эти две дуги можно исключить из рас­смотрения. Соответственно становится применимой и расчетная фор­мула (2), по которой получаем:

М(С) = <*(С —> Е) + М(Е) = 10,

М(В) = шах{^(В —> С) + М(С); <*(В —> Е) + М(Е)} = тах{17;4} = 17, М( А) = тах {й(А->В) + М( В); с1{ А-»С) + М( С)} = тах{25; 11} = 25.

Таким образом, среди всех проходящих через В —» С путей максималь­ный путь имеет вид А—>В—>С—>Еипо длине равен 25 (очевидно, что для данного простого орграфа этот путь является единственным в первом подмножестве).

Для путей из второго подмножества, не проходящих по дуге В —» С, при расчете максимального пути эту дугу можно исключить; при этом становится непосредственно применимой формула (2):

М(В) = d(В —> Е) + М(Е) = 4, M(D) = d(D -> В) + М(В) = 7,

М(С) = max {d(С -» D) + M(D); d(C -» Е) + М(Е)} =

= max {9; 10} = 10, М(А) = max {d(A —> В) + М(В); d(A -> С) + М(С)} = = max {12; 11} = 12.

Таким образом, среди путей, не проходящих через В —» С, максималь­ный путь имеет длину, равную 12.

Сопоставляя два рассмотренных случая, получаем, что максималь­ным путем из А в Е в заданном орграфе является путь А —» В —> С —» Е длиной 25. Этот же результат можно получить и методом перечисле­ния путей — для данного простого орграфа перечисление не является излишне громоздким.

Остановимся на методике решения задачи о максимальном пути в специальном случае v_KOH = и_нач; фактически задача состоит в по­иске замкнутого пути, или простого контура максимальной длины, проходящего через указанную вершину. Данная задача может быть решена с использованием следующего приема. В соответствии с ме­тодом ДП принимаем M(v_KOH) = 0. Как только в ходе расчетов зна­чения функции М станут известны для всех вершин, предшеству­ющих вершине г>кон, условие М(г>кон) = 0 устраняется, и значение M(vкон) = М(у_нач) полагается неизвестным. Далее вычисление функ­ции M(v) проводится по обычной схеме.

5. В качестве примера рассмотрим задачу о максимальном замкну­том пути, проходящем через вершину А, для орграфа, представленного на рис. 3.25. Полагая М(А) = 0, проводим следующие расчеты по фор­муле (2):

М{С) = d{С —> А) + М{А) = 9, М(Е) = d(E —> А) + М(А) = 8, М(F) = max{d(F -> А) + М(A); d(F С) + М(С);

d(F —> Е) + М(Е)} = max{10; 12; 13} = 13;

в последнем случае максимум достигается на дуге F —> Е. Дугу Н А, очевидно, можно исключить из рассмотрения. В настоящий момент впервые становятся известны значения функции М для всех вер­шин, предшествующих вершине А; условие М(А) = 0 отбрасывается, а функция М полагается неизвестной для вершины А, играющей роль

не только конечной, но и начальной вершины. Далее вычисления про­должаются обычным образом:

М(В) = тах {<*(В -> С) + М(С); В -> Р) + М(¥)} = 15,

М(Б) = -» Р) + М(Р) = 14.

После этого значения функции М становятся известны для всех вершин, следующих за А, за исключением вершины С. Но дугу А —» С можно исключить, поскольку у вершины С нет последующих. Следо­вательно,

М(А) = тах {д(к —> В) + М(В); д(А —> Б) + М(Б)} = 21.

Таким образом, максимальный путь, начинающийся и заканчиваю­щийся в вершине А, имеет вид

А—>Р—>Е—>А

и по длине равен 21.

Задание. Провести- проверку полученного решения данной задачи методом перечисления путей.

В заключение раздела сделаем ряд замечаний.

Замечание 1. Подобно решению задачи о кратчайшем пути, реше­ние задачи о максимальном пути методом ДП может быть оформлено как с проведением записи на самом графе (этот способ удобен, если структура графа представлена непосредственно в виде схемы), так и с заполнением таблицы, по структуре полностью аналогичной таблице из разд. 3.7. Для орграфа, изображенного на рис. 3.24 и рассмотрен­ного в п. 3 настоящего раздела, при наличии дуги 9 —> 6 решение задачи представлено в приведенной ниже таблице.

 

Максимальный путь строится обычным образом начиная с вер­шины 2 с использованием отметок «/».

Замечание 2. Укажем здесь на еще одно из возможных прило­жений алгоритма перечисления путей. Предположим, что в представ­ленном на рис. 3.24 орграфе дуга 8 —> 9 в рассматриваемом орграфе заменена сложной сетью с входом в вершине 8 и выходом в вершине 9, дуга 9 —> 6 отсутствует. В этом случае определить, можно ли исклю­чить дугу 7 —> 8, не столь просто. Для этого достаточно установить, что все пути, начинающиеся в вершине 8, приводят в вершину 7. Сделать это можно посредством перечисления путей, начинающихся в вершине 8.

путь из А в Е имеет вид

А —> В —> Б —> Е

и по длине равен 3. При этом для внутренней вершины Б этого пуп максимальным путем к вершине Е является не дуга Б —> Е длиной 1 а путь Б —» С —> В —> Е длиной 3.

Данное свойство выражает некоторую «неустойчивость» максималь ного пути на орграфах произвольной структуры.

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

М» = шах {М'(и) + с1(и V)),                                      (4

и€ v- (и)

где через М'(у) обозначена длина максимального пути из начально] вершины <;_нач в вершину у. При этом М'(и_нач) = 0, а М'(и_кон) равн( длине искомого максимального пути и подлежит вычислению. Подоб ные ситуации для орграфов, являющихся сетями, в несколько ины: обозначениях и терминологии будут детально рассмотрены в следую щих разделах.