3.4. Решение задачи о кратчайшем пути методом динамического программирования

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

Пусть V 6 V — некоторая вершина графа. Определим функцию Ь{у) как длину кратчайшего пути, соединяющего вершину у с конечной вершиной г;_коп; если такого пути не существует, то функция Ь считается неопределенной для вершины у. В соответствии с этим определением имеет место равенство Ь(у_кон) = 0, а Х(г'_нач) равно длине искомого кратчайшего пути и подлежит определению.

На каждом шаге решения задачи методом ДП множество вершин графа подразделяется на следующие три непересекающиеся группы:

1)               занятые вершины, для которых значения функции Ь(у) уже вычислены;

2)               пробные вершины, для которых значения функции Ь(у) еще не вычислены, но имеются оценки Е(у) длины кратчайшего пути от у к г>кон (оценки сверху);

3)               свободные вершины, для которых не вычислены ни сами длины Ь(у), ни их оценки Е(у).

В начальный момент решения задачи к занятым вершинам отно­сится только конечная вершина г;_кон, а все остальные — к свободным; по ходу решения группа занятых вершин расширяется, а группа сво­бодных — сужается.

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

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

1.               Начало работы алгоритма. Полагаем Ь(у_кон) = 0, вершину у_шш объявляем занятой, а все остальные вершины — свободными.

2.               Проверка. Если начальная вершина г;_на,, является занятой (т. е. для нее известно значение функции Ь(у)), то переходим к п. 5.

3.               Вычисление или корректировка оценок незанятых вершин (ме­тодика расчетов детально рассмотрена ниже).

4.               Пополнение группы занятых вершин. Из пробных вершин вы­бираем те, для которых оценки имеют минимальное значение (таких вершин может быть одна или несколько). Эти вершины объявляем занятыми и полагаем для них

Ь(у) = Е(у).

Переход к п. 2.

5.               Расчет длины кратчайшего пути завершен. Строим кратчайшие пути (один или несколько). Конец работы алгоритма.

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

Для свободных вершин оценка вычисляется по формуле

E(u) = min {d(uv) + L(v)},

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

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

т = min {d(uv) + L(y)},

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

—               если т > Е(и), то оценка не меняется;

—               если т = Е(и), то оценка не меняется, но к установленным ранее стрелкам добавляются стрелки на тех ребрах вида uv, для которых вычисленный минимум достигается;

—               если m < Е(и), то уменьшаем оценку, полагая Е(и) = т, уста­новленные ранее стрелки убираем и ставим новые стрелки на тех ребрах вида uv, для которых вычисленный минимум достигается.

Таким образом, в ходе корректировки оценка уменьшается или не изменяется: если обозначить через Е(и) уже имеющуюся оценку, то новая оценка вычисляется по формуле

Е(и) = тт{Ё(и),т] < Ё(и).

Для удобства контроля ребра, уже учтенные при вычислении оце­нок, можно отмечать «засечками». При вычислении оценок важно учесть все вершины, смежные с занятыми. Если же незанятых вер­шин, смежных с занятыми, нет, а начальная вершина все еще не явля­ется занятой, то путей, соединяющих заданные начальную и конечную вершины, не существует. В этом случае задача о кратчайшем пути решений не имеет.

U₂

Способ вычисления оценок может быть проиллюстрирован схемой на рис. 3.6. В ней принято, ЧТО вершины 1>1, 1>2, t>3 (и, конечно, г>кон) являются занятыми, причем v\ и г>2 стали занятыми на последнем шаге алгоритма, а г>₃ стала занятой ранее. Сплошными линиями обозначены ребра графа, пунктирными — кратчайшие пути от занятых вершин К конечной. Среди вершин U\,U2,Uz, смежных с занятыми, первые две являются свободными, а из является пробной и имеет оценку

Ё(и₃) = d(u₃v₃) + L(v з),

вычисленную с использованием ребра и₃г>₃. В этом случае справедливы формулы

Е(щ) = d(itiui) + L(vi),

E(u₂) = mm{d(u₂vi) + L(v\), d(u₂v₂) + L(v₂)},

E(u3) = тт{£(из),т}, m = d(u₃v 2) + L(v2).

Приведенные формулы для вычисления оценок E(u) и длин крат­чайших путей L{u) выражают своеобразный аналог классического принципа оптимальности. Эти формулы носят рекуррентный харак­тер, и в них также выделяется первый шаг от текущей вершины и к конечной вершине г;_кон, проводимый по ребру uv\ при этом длины кратчайших путей от занятых вершин v являются уже известными. Функция L(v) является аналогом семейства функций Беллмана В_г(х_г). Расчеты начинаются с конечной вершины и условия L(v_KOH) = 0, со­ответствующего условию /J,v(.x,v) = 0. Роль управления играет выбор ребра, по которому следует начинать движение из рассматриваемойвершины. Расчет функций Ь(у) представляет собой аналог этапа услов­ной оптимизации классического метода ДП.

Построение кратчайшего пути в п. 5 алгоритма представляет собой аналог этапа безусловной оптимизации метода ДП и проводится сле­дующим образом. Начинается построение с начальной вершины г>_нач. Из этой вершины выходит по меньшей мере одна стрелка, установлен­ная при вычислении оценок для данной вершины. Переходим по этой стрелке (или по одной из них) в следующую вершину. Аналогично, из этой вершины также выходит по меньшей мере одна стрелка, по которой переходим далее. Так продолжаем до тех пор, пока не придем в конечную вершину 1)_КОП. При наличии нескольких кратчайших путей все они могут быть построены с помощью алгоритма перечисления путей (см. ниже замечание 4 данного раздела).

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

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

—               Поскольку начальная вершина Б не является занятой, то пере­ходим к п. 3 алгоритма.

—               Для занятой вершины Е смежными являются вершины А и Р, причем все они являются свободными, т. е. ни для одной из них оценок еще не рассчитано. Вычисляем оценки впервые для этих вершин:

Е( А) = е?(АЕ) + Ь( Е) = 7 + 0 = 7, Е(Р) = <*(РЕ) + Ь( Е) = 4 + 0 = 4.

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

—               Из двух пробных вершин А и Р значение оценки для вершины Р минимально. Полагаем Ь(Р) = Е(Р) = 4, отмечаем жирным шрифтом данное значение на графе, объявляем вершину Р за­нятой. Переход к п. 2.

—               Поскольку начальная вершина Б не входит в группу занятых вершин {Е, Р}, то переходим к п. 3.

—               Для занятых вершин Е и Р смежными являются вершины А, Б,Т, причем вершины Б и Т являются свободными. Вычисляем оценки

для этих вершин:

Е( S) = d(SP) + Ц Р) = 9 + 4 = 13, Е( Т) = d( TP) + L(P) = 6 + 4 = 10.

Полученные значения записываем на графе около соответству­ющих вершин, которые переходят в группу пробных вершин. Отмечаем стрелками ребра SP и ТР. Отметим, что в настоящий момент впервые рассчитана оценка для начальной вершины S. Для вершины А уже известна оценка Е(А) = 7, рассчитанная ранее, причем после ее вычисления стала занятой только вер­шина Р, смежная с А. Проводим соответствующую корректировку оценки:

m = g?(AP) + L(P) = 1 + 4 = 5.

Поскольку m < Е(А), то полагаем Е(А) = m — 5, и ранее установ­ленную на ребре АЕ стрелку переносим на ребро АР. Полученное значение оценки записываем на графе около вершины А.

—               Из трех пробных вершин А, S, Т минимальное значение 5 оценка принимает для вершины А. Полагаем L(А) = Е(А) = 5, отме­чаем жирным шрифтом данное значение на графе и объявляем вершину А занятой. Переход к п. 2.

—               Поскольку начальная вершина S не входит в группу занятых вершин {А,Е,Р}, то переходим к п. 3.

—               В настоящий момент для занятых вершин А, Е, Р смежными яв­ляются вершины Н, S, Т, причем вершина Н является свободной. Вычисляем оценку для этой вершины:

Е(Н) = d( НА) + L( А) = 5 + 5 = 10,

записываем полученное значение на графе и переводим ее в группу пробных вершин. Отмечаем стрелкой ребро НА. Для вершин S и Т уже известны оценки Е(S) = 13 и Е(Т) = 10, причем только вершина А стала занятой после их вычисления. Корректируем значения оценок:

тп( S) = d(SA) + L( А) = 10 + 5 = 15, m(T) = d( ТА) + L( А) = 8 + 5 = 13.

Поскольку m(S) > E(S) и m(T) > Е(Т), то оценки не меняются, и ранее установленные стрелки SP и TP не переносятся.

—               Из трех пробных вершин Н, S, Т минимальное значение 10 оценка принимает сразу для двух вершин Н и Т. Полагаем

L(Н) = Е(Н) = 10, L(T) = £?(Т) = 10, отмечаем жирным шриф­том данные значения на графе, объявляем вершины Н и Т за­нятыми. Переход к п. 2.

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

—               Корректируем оценку для вершины S, учитывая, что после ее вычисления стали занятыми две вершины Н и Т:

m = min {d(SH) + L(H); d(ST) + L(T)} = min {2 + 10; 4 + 10} = 12.

Поскольку m < E(S) = 13, то полагаем E(S) — m = 12, ра­нее установленную на ребре SP стрелку снимаем и переносим на ребро SH, на котором достигается минимум. Полученное зна­чение оценки записывается на графе около вершины S.

—               Единственной пробной вершиной является вершина S. Полагаем L(S) = E(S) = 12, отмечаем жирным шрифтом данное значение на графе, объявляем вершину S занятой. Переход к п. 2.

—               Начальная вершина S является занятой. Переход к п. 5.

—               Основная расчетная часть алгоритма завершена, длина кратчай­шего пути равна L(S) = 12. Кратчайший путь строится начиная с вершины S с использованием установленных на графе стрелок SH, НА, АР, РЕ. Таким образом, кратчайший путь имеет вид

S-Н-А-Р-Е. Конец работы алгоритма.

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

К решению данной задачи необходимо сделать ряд следующих за­мечаний.

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

Замечание 2. В рассмотренном примере существует только один кратчайший путь. В иных ситуациях может существовать и большее число кратчайших путей. Например, если длину ребра PS изменить с 9 на 8, то возникнет второй кратчайший путь S — Р — Е той же длины 12. Если и длину ребра AS изменить с 10 на 7, то возникнет и третий кратчайший путь S — А — Р Е. При этом после завершения алгоритма из вершины S будет выходить 3 стрелки SA, SH, SP.

Замечание 3. В отдельных случаях значение длины кратчайшего пути может быть получено до того, как будут рассчитаны оценки всех вершин. Например, если длину ребра РБ изменить с 9 на 1, то сразу после вычисления Ь(Р) = 4 две вершины А и Б получат одинаковые минимальные оценки, равные 5. Это будет означать, что кратчайший путь длины 5 имеет вид в —Р —Е. При этом для вершины Т будет известна только оценка, а вершина Н вообще останется свободной.

Замечание 4. Отметим здесь одно из возможных приложений рассмотренного выше алгоритма перечисления путей. Пусть задача о кратчайшем пути решается для изображенного на рис. 3.7 графа с равными единице длинами всех ребер, начальной вершиной 1 и ко­нечной вершиной 9, причем требуется найти не какой-либо один, а все кратчайшие пути.

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

1-2-5-7-9

1-2-5-8-9

1-3-5-7-9

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

Замечание 5. Важно подчеркнуть, что рассмотренный метод неприемлем для решения задачи о кратчайшем пути на графах, со­держащих ребра с отрицательными весами. Для примера рассмотрим граф, изображенный на рисунке 3.8, с начальной вершиной 1 и ко­нечной вершиной 3. В нем имеются 2 пути: 1 — 3 длиной 1 и 1 — 2 — 3 длиной —1, так что кратчайшим является путь 1 — 2 — 3. Формально проводимые расчеты в этом случае дадут:

Ь{ 3) = О, Е{ 1) = 1, Е( 2) = 2, после чего мы должны принять Ь(\) = 1, что не является верным.

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

Например, для графа на рис. 3.9 с начальной вершиной 1 и конечной вершиной 3 длина максимального пути 1 — 2 — 3 равна 101. Формально проводимые расчеты дадут:

Ь( 3) = 0, Е(1) = 10, Е( 2) = 1,

после чего, следуя желаемой логике, мы должны принять значение Ь( 1) равным 10, что не является верным (здесь функция Ь есть длина максимального пути к вершине 3).Замечание 7. Рассмотренный алгоритм предписывает начинать расчеты с конечной вершины и заканчивать начальной вершиной, т. е. вести их в обратном порядке, что соответствует этапу условной опти­мизации классического метода ДП; при этом построение кратчайшего пути поводится от начальной вершины к конечной. Важно подчеркнуть, что в теории графов можно изменить порядок расчетов и начинать их с начальной вершины, заканчивать конечной вершиной, а сам крат­чайший путь строить начиная с конечной вершины. Соответствующий алгоритм был разработан в 1959 г. и называется алгоритмом Дийкс- тры по имени выдающегося голландского теоретика и практика про­граммирования второй половины XX в. Эдсгера В.Дийкстры (Ес^ег

Букета). В алгоритме Дийкстры занятые вершины называются обычно вершинами с постоянными метками, а пробные вершины — вершинами с временными метками.