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

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

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

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

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

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

М(у) = max {d(v -> го) + M(w)}. (2)

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

M(vKOH) = 0, (3)

которое по форме является аналогичным соответствующему условию для задачи о кратчайшем пути, но не столь очевидно и требует пояснения. Данное условие можно трактовать как требование не допускать зацикливания на начальном этапе построения максимального пути. Действительно, в общем случае при v ф t>KOH ни один путь из v в vKOH не содержит контуров, проходящих через вершину г>кон (иначе вершина t>KOH повторялась бы более одного раза, что противоречило бы самому понятию пути). В то же время в орграфе может существовать непустой замкнутый путь из v = t>KOH в г>кон, что приводит к соотношению М(г>кон) > 0. Данная возможность вступает в противоречие с общим случаем, и для его устранения надлежит принять обсуждаемое условие (3).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

М(1) = d(l -> 3) + М(3) = 5, М(4) = d(4 -> 1) + М(1) = 9, М(6) = d(6 -> 4) + М(3) = 10,

М(7) = max {d(7 -> 4) + М(4); d(7 -> 6) + М(6)} =

= max {13; 12} = 13, М(5) = max {d(5 -» 3) + М(3); d(5 -> 4) + М(4); d(5 7) + М(7)} =

= max {20; 17; 16} = 20.

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

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

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

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

2-»...-»1-»2-»...-»6,

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

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

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

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

М(4) = d(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 присутствует в орграфе.

8 этом случае исключить дуги 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 —-> 6, а длина его равна 5.

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

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

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

пути, проходящие по дуге В —-> С;

пути, не проходящие по дуге В —-> С.

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

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

М(С) = d(C —* Е) + М(Ё) = 10,

М(В) = max{d(B -» С) + М(С); d(B -> Е) + М(Е)} = тах{17;4} = 17, М(А) = max{d(A—>В) + М(В); d(A-»C) + М(С)} = max{25; 11} = 25.

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

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

Af (В) = d(B -> Е) + М(Е) = 4, М(D) = d(D -> В) + М(В) = 7,

М(С) = max {d(C -> D) + M(D); d(C -> E) + M(E)} =

= max {9; 10} = 10, Af (A) = max {d(A -> B) + M(B); d(A -» С) + M(C)} =

= max {12; 11} = 12.

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

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

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

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

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

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

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

М(В) = max {d(B -> С) + М(С); d(B —> F) + М(F)} = 15, Af(D) = d(D -» F) + Af (F) = 14.

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

Af(A) = max {d(A -> В) + Af (В); d(A -> D) + Af (D)} = 21.

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

A^D^F^E->A

и по длине равен 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. Отметим одно из различий в свойствах решений задач о максимальном и кратчайшем пути. Рассмотрим кратчайший путь, соединяющий некоторые начальную и конечную вершины произвольного взвешенного орграфа. В этом случае участок кратчайшего пути от любой внутренней (промежуточной) вершины этого пути до конечной вершины также является кратчайшим. Если орграф представляет собой сеть, то аналогичное свойство справедливо и для задачи о максимальном пути: любой участок максимального пути является максимальным. Для орграфов, не являющихся сетями, это свойство может не выполняться. В качестве примера рассмотрим орграф, представленный на рис. 3.26, длины всех дуг которого равны единице, начальной является вершина А, конечной — вершина Е. Максимальный

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

А В -». D -» Е

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

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

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

М» = max {M'(u) + d(u v)}, (4

иЄ V(v)

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