§ 52. Метод динамического программирования

Графы без контуров. Рассмотрим граф без контуров и его порядковую функцию

Рис. 238.

Пусть, например, -граф на рис. 238, а

— его порядковая функция.

Ищем путь из с минимальным значением (закон композиции — сложение).

Рис. 239

Начиная с А, рассматриваем последовательно все вершины графа в порядке возрастания его порядковой функции (вершины одного и того же уровня рассматриваются в произвольном порядке) и приписываем каждой вершине «потенциал», равный минимальному значению пути из в А. Этот процесс иллюстрирует рис. 239, на котором минимальный путь (он единственный) выделен. Для графа на

рис. 238 с порядковой функцией

(см. рис. 240) получаем тот же результат (см. рис. 241).

Рис. 240.

Теоремы оптимальности (§ 51) дают обоснование изложенного способа, называемого методом динамического программирования. Он предложен Веллманом и развит им для последовательных графов (см. § 53). Автор и Крюон перенесли его на случай графов без контуров. Условия его применимости:

1) граф должен обладать порядковой функцией;

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

Случай, когда начальный и (или) конечный уровень содержат более одной вершины. Пусть заданы граф без контуров со значениями, приписанными дугам, и его порядковая функция. Оптимальный путь между его уровнями можно найти изложенным выше способом. Для этого достаточно дополнительно ввести две вершины: вход и выход Вход соединим дугами, приписывая каждой из них значение 0, со всеми вершинами а все вершины соединим дугами с приписывая им также значение 0 (предполагается, что закон композиции — сложение; в случае умножения приписываем этим дугам значение 1). Тогда длина искомого оптимального (т. е. максимального или минимального) пути

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

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

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

Алгоритм Форда [23]. Будем предполагать, что всем дугам рассматриваемого графа приписаны положительные значения (в противном случае мы могли бы, например, добиться этого, прибавляя к каждому значению абсолютную величину наименьшего из них, увеличенную на 1, и будем искать минимальный путь из следующим способом.

Рис. 241.

Каждой вершине будем приписывать символы по следующему правилу:

1) положим при

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

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

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

что значение любого другого пути между не меньше Имеем

Отсюда

Точно так же можно получить

т. е. минимальный путь.

Рис. 242.

Пример. Шаг 1. Приписываем вершине значение 0, а остальным вершинам — значение (рис. 242). Имеем

Затем приписываем значения что иллюстрирует рис. 243.

Шаг 2. Теперь и рассматривая другие вершины видим, что нельзя уменьшить;

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

Рис. 243.

Так как

то полагаем

Так как

то полагаем

Так как

То полагаем

Так как

то полагаем

Так как

то полагаем

Результаты представлены на рис. 244.

Рис. 244.

Шаг 3. Действуя аналогично, видим, что

т. е. значения путей уменьшить больше нельзя. Таким образом, приходим к минимальным путям от до

со значением 21. На рис. 244 представлены также значения минимальных путей от До любой другой вершины.

Отыскание максимального пути графа без контуров. Алгоритм Форда может быть использован для отыскания максимального пути таких графов. Достаточно положить а затем заменять на если до тех пор, пока возможно увеличивать

Алгоритм Беллмана — Калаба [2]. Этот алгоритм использует Принцип оптимальности: «любой подпуть минимального пути

является минимальным путем между соответствующими вершинами». Рассмотрим граф и пронумеруем вершины от 0 до

Пусть значение, приписанное дуге Положим если если

Найдем такой путь

что

минимально. Задача сводится к решению системы

где через обозначены значения оптимальных путей от до

Положим

Вычисляем последовательно

до тех пор, пока не будет выполнено равенство

и тогда будет минимальным значением оптимального пути от 0 до Легко показать, что для его нахождения достаточно итераций.

Пример (см. рис. 242). Матрица (стоимостей) выписана ниже (рис. 245).

Имеем

Вычисляем последовательно

Рис. 245

Результаты сведены в нижеследующую таблицу:

Так как то минимальное значение. По легко выписать оптимальные пути (они даны в (52.11)).

Замечание. Объем вычислений можно сократить, действуя следующим образом.

а) Если наименьший элемент вектора (без учета и то фиксируем и строим вектор

б) Вектор определяем, исходя из и соотношения

в) В векторе выбираем наименьшее значение причем индекс принадлежит вершинам множества где элемент с наименьшим значением при итерации

Рис. 246

Если то -минимальный путь. В противном случае обращаемся к б).

Этим способом нельзя найти максимальный путь.

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

Например, на рис. 246 числа в квадратиках обозначают значения максимальных путей от

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

Пусть значение дуги если Найдем такой путь

что

минимально.

В этом случае задача решается с помощью видоизмененного алгоритма Веллмана — Калаба путем рассмотрения системы

где через обозначено значение оптимального пути от до Аналогично (52.16) — (52.21) полагаем

Вычисляем последовательно

до тех пор, пока не получаем

Например, для графа на рис. 242 путь

со значением

минимален.

С очевидными изменениями изложенный метод годится для отыскания путей с максимальным значением (52.25).

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

Расстояние между двумя вершинами. Путь минимальной длины. Рассмотрим граф . Число дуг в пути минимальной длины от вершины до называют расстоянием от до Например, для графа на рис. 247 . Нахождение расстояния — частный случай задачи оптимизации суммы значений дуг при если

Можно использовать алгоритм как Форда, так и Беллмана—Калаба, но мы поступим иначе. Пусть нужно найти расстояние от до Полагаем если не существует пути от X до Действуем по следующим правилам:

1) помечаем вершину индексом 0;

Рис. 247

2) помечаем индексом 1 все вершины для которых

3) если через обозначено множество вершин, помеченных индексом то образуем множество

4) если принадлежит некоторому то последовательность вершин таких, что

дает искомый путь.

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

(см. скан)