Принцип оптимальности и метод динамического программирования

Дадим более подробное описание рассматриваемой общей задачи многошаговой оптими-зации. Предполагается, что задан простой ориентированный взвешенный граф G (V, A) c мно-жеством вершин V и множеством дуг A. Предполагается также, что каждой дуге (x, y) сопостав-лено число w (x, y), интерпретируемое как длина, стоимость, вес данной дуги. Далее будет ис-пользоваться общий термин «вес». Рассматриваются все ориентированные пути длины N (т.е. состоящие из N последовательных дуг) с началом в заданной вершине x ⁰. Для каждого такого пути P определяется его вес W (P) как сумма весов входящих в него дуг. Путь P называется оп-тимальным, если для любого другого пути P’ длины N с началом в вершине x ⁰ выполняется неравенство W (P) ≥ W (P’). В тех случаях, когда необходимо явно указать на длину и начальную вершину оптимального пути, будет использоваться обозначение P (x ⁰, N).

Очевидным образом определение оптимального пути переносится на случай минимизации (вместо максимизации) веса. Заметим, однако, что в рассмотренных в главе 8 задачах на крат-чайшие пути не предполагалась, что число дуг в рассматриваемых путях фиксировано. Для су-ществования решения там требовались дополнительные условия типа неотрицательности весов дуг или неотрицательности циклов. В данном случае при фиксированной длине пути множество путей всегда конечно и, следовательно, задача оптимизации (и на максимум, и на минимум) всегда имеет решение. Заметим также, что в общем случае оптимальный путь (далее для опре-делённости будем рассматривать задачу максимизации) может не быть простым путём или це-пью (см. определения в разделе 2.3). Это означает, что он может проходить несколько раз через одни и те же вершины и дуги.

Далее в этом разделе излагается хорошо известный метод поиска пути максимального ве-са при заданном начальном состоянии x ⁰и заданной длине N. Этот метод называется методом динамического программирования. Идея метода состоит в сведении задач длины N к семейст-ву задач длины N – 1, и т.д., вплоть до непосредственно решаемых задач длины 1. Введём необ-ходимые формальные обозначения.

Обозначим задачу поиска максимального пути длины r с начальной вершиной x через Z (r, x), её решение (т.е. соответствующий максимальный путь) – через P (x, r), а вес этого пути – через W (x, r). Предположим, что для любой вершины x графа G задача оптимизации Z (r, x) решена, то есть известны и пути P (x, r), и их веса W (x, r). Рассмотрим теперь фиксированную вершину x ⁰ и любой путь P длины r +1 с началом в вершине x ⁰. Следующей (т.е. второй) вершиной на пути P является некоторая вершина x. Вес W (P) пути P равен сумме двух слагаемых: веса w (x ⁰, x) первой дуги пути P и веса W (P’), где P’ – оставшаяся часть пути P от вершины x до его конца, длина которого равна r, т.е.

W (P) = w (x ⁰, x) + W (P’). (4)

Поскольку длина W (x, r) оптимального пути из x длины r предполагается известной, то из (4) сразу следует, что

W (P) ≤ w (x ⁰, x) + W (x, r), (5)

а поскольку вершина x была выбрана произвольно, то из (5) следует, что для веса оптимального пути с начальной вершиной x ⁰ и длиной r +1 выполняется равенство

W (x ⁰, r +1) = max _x { w (x ⁰, x) + W (x, r)}. (6)

Формула (6) является, по сути, формулой перехода от размерности r к бóльшей размернос-ти r +1. Конечно, она позволяет найти не только оптимальные веса путей, но и сами эти пути, добавляя к началу известных путей длины r дугу (x ⁰, x), где x максимизирует правую часть (6). Наконец, при r = 1 оптимальные пути P (x,1) ищутся непосредственно из условия максимизации веса одной дуги с началом в вершине x:

W (x,1) = max _yw (x, y). (7)

Как и ранее, рассматриваемые графы будем предполагать полными, а веса реально отсутствую-щих дуг будем считать равными −∞ (в задачах минимизации +∞).

Метод, основанный на проведённых простых рассуждениях, называется методом дина-мического программирования, а основное соотношение (6) называется уравнением Беллмана, по имени американского математика, первым сформулировавшим этот метод именно как об-щий метод решения многошаговых оптимизационных задач (не только дискретных) и решив-шим на его основе многие важные прикладные задачи.

Прежде чем идти дальше, приведём грубую оценку выигрыша, который может дать дина-мическое программирование. Число вершин в орграфе G обозначим через m. Для простоты предположим, что орграф является полным, т.е. из каждой вершины выходят дуги во все вер-шины, включая её саму (т.е. имеются петли при вершинах). Общее число путей длины N равно, очевидно, m^N. В то же время число операций на каждом переходе к следующей размерности имеет порядок m ², а общее число операций при N шагах имеет порядок Nm ². При весьма скром-ных значениях m = 20 и N = 10 для числа операций при методе динамического программирова-ния имеем оценку 10*400 = 4000, в то время как при прямом переборе нужно проверить 20¹⁰ ≈ 10¹⁶ вариантов.

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

Пример 1. Рассмотрим орграф, показанный на рис.8-3. Здесь он перерисован как рис.1. В качестве начальной вершины x ⁰возьмём вершину 1. Положим длину искомого макси-мального пути N = 6.

Рис.1

1. Инициализация и 1-ая итерация. Сформируем таблицу, состоящую из 5-и строк (по числу вершин) и 12-и столбцов. В левой части таблицы представлен исходный граф. В ячейку

Таблица 1.1. Инициализация и итерация 1

всп

−∞

−5

−∞

−4

−∞

(i, j) на пересечении i -ой строки и j -го столбца записан вес дуги из вершины j в вершину i (именно в таком порядке). Эта часть таблицы далее не меняется. В правом столбце в i -ую ячейку слева записаны максимальный вес дуги, выходящей из i -ой вершины, а слева – номер вершины, в которую входит эта дуга. Так, в 1-ой ячейке слева записан максимальный вес дуги, выходящей из вершины 1 (8), а справа – конец этой дуги (вершина 3); во 2-ой ячейке – вес 7 и номер 5, и т.д. С учётом формулы (7) можно сказать, что 1-ый справа столбец содержит всю информацию о максимальных путях длины 1.

2 -ая итерация.

Таблица 1.2. Итерация 2.1

всп

−∞

−5

−∞

−4

−∞

−4

В левый вспомогательный столбец скопируем 1-ый столбец левой части таблицы. В нём будут находиться расстояния от вершины 1 до остальных вершин. В правый вспомогательный стол-бец запишем сумму чисел левого вспомогательного столбца и левого столбца итерации 1. Мак-симальное число (12) из записанных в правый вспомогательный столбец запишем в левую клет-ку 1-ой ячейки итерации 2, а в правую клетку запишем номер строки этого максимального чис-ла (3). Эти операции соответствуют уравнению Беллмана (6). После этого стираем содержимое вспомогательных столбцов и повторяем те же операции для 2-го столбца левой части таблицы:

Таблица 1.2. Итерация 2.2

всп

−∞

−5

−∞

−4

−∞

Повторяем те же действия для 3-го, 4-го и 5-го столбцов. Получаем:

Таблица 1.2. Итерация 2.3

всп

−∞

−5

−∞

−4

−∞

Таблица 1.2. Итерация 2.4

всп

−∞

−5

−∞

−5

−1

−∞

−4

−∞

Таблица 1.2. Итерация 2.5

всп

−∞

−5

−∞

−4

−∞

В результате найдены все максимальные пути длины 2. Из 1-ой вершины имеем путь 1→3→2 с весом 12, из 2-ой вершины – путь 2→5→4 с весом 13, из 3-ей – путь 3→2→5 с весом 11, из 4-ой – путь 4→1→3 с весом 10, из 5-ой – путь 5→4→2 с весом 8.

3-ья итерация. Повторяем операции 2-ой итерации с той разницей, что теперь прибавляя-ются элементы левого столбца итерации 2:

Таблица 1.3. Итерация 3.1

всп

−∞

−5

−∞

−4

−∞

−4

Таблица 1.3. Итерация 3.2

всп

−∞

−5

−∞

−4

−∞

Таблица 1.3. Итерация 3.3

всп

−∞

−5

−∞

−4

−∞

Таблица 1.3. Итерация 3.4

всп

−∞

−5

−∞

−5

−∞

−4

−∞

Таблица 1.3. Итерация 3.5

всп

−∞

−5

−∞

−4

−∞

4-ая итерация:

Таблица 1.4. Итерация 4.1

всп

−∞

−5

−∞

−4

−∞

−4

Таблица 1.4. Итерация 4.2

всп

−∞

−5

−∞

−4

−∞

Таблица 1.4. Итерация 4.3

всп

−∞

−5

−∞

−4

−∞

Таблица 1.4. Итерация 4.4

всп

−∞

−5

−∞

−5

−∞

−4

−∞

Таблица 1.4. Итерация 4.5

всп

−∞

−5

−∞

−4

−∞

5-ая итерация:

Таблица 1.5. Итерация 5.1

всп

−∞

−5

−∞

−4

−∞

−4

Таблица 1.5. Итерация 5.2

всп

−∞

−5

−∞

−4

−∞

Таблица 1.5. Итерация 5.3

всп

−∞

−5

−∞

−4

−∞

Таблица 1.5. Итерация 5.4

всп

−∞

−5

−∞

−5

−∞

−4

−∞

Таблица 1.5. Итерация 5.5

всп

−∞

−5

−∞

−4

−∞

6-ая итерация. На 6-ой итерации рассматриваемые операции делаются только с 1-ым стол-бцом, поскольку требуется найти максимальный путь с началом в вершине 1:

Таблица 1.6. Итерация 6

всп

−∞

−5

−∞

−4

−∞

−4

Последняя таблица определяет путь длины 6 с началом в вершине 1. Последовательность вершин, образующих искомый путь, выделена. Его вес равен 35. Слева от выделенных вершин указан вес пути от предыдущей вершины до конца. Сам путь таков: 1→3→2→5→4→1→3. Он не является ни простым путём, ни цепью, поскольку дважды проходит по дуге 1→3.

Напомним, что метод находит максимальный путь для произвольной дискретной много-шаговой задачи с аддитивной функцией. Граф здесь только иллюстрирует метод ■

Пример 2. Для того же графа, той же начальной вершины и той же длины пути N = 6 най-дём путь минимального веса. Отличие от предыдущего примера будет состоять только в том, что на итерации 1 будет выбираться дуга не с максимальным, а с минимальным весом; далее в правом вспомогательном столбце будем искать не максимальный, а минимальный элемент. Ко-нечно, вес отсутствующих дуг равен ∞ (а не −∞). Промежуточные таблицы опущены; демонст-рируется только результат каждой итерации.

Таблица 2.1. Инициализация и итерация 1

всп

∞

−4

∞

−5

∞

−5

−4

∞

Таблица 2.2. Итерация 2

всп

∞

−4

∞

−4

∞

−5

∞

−2

−5

−4

∞

Таблица 2.3. Итерация 3

всп

∞

−3

−4

∞

⇐ Предыдущая 23 24 25 26 272829 30 31 32 Следующая ⇒

Поделиться с друзьями:

Дата добавления: 2016-10-07; Мы поможем в написании ваших работ!; просмотров: 611 | Нарушение авторских прав

Поиск на сайте:

Лучшие изречения:

2338 -

| 2092 -

Ген: 0.012 с.