Читайте также: |
|
Дадим более подробное описание рассматриваемой общей задачи многошаговой оптими-зации. Предполагается, что задан простой ориентированный взвешенный граф G (V, A) c мно-жеством вершин V и множеством дуг A. Предполагается также, что каждой дуге (x, y) сопостав-лено число w (x, y), интерпретируемое как длина, стоимость, вес данной дуги. Далее будет ис-пользоваться общий термин «вес». Рассматриваются все ориентированные пути длины N (т.е. состоящие из N последовательных дуг) с началом в заданной вершине x 0. Для каждого такого пути P определяется его вес W (P) как сумма весов входящих в него дуг. Путь P называется оп-тимальным, если для любого другого пути P’ длины N с началом в вершине x 0 выполняется неравенство W (P) ≥ W (P’). В тех случаях, когда необходимо явно указать на длину и начальную вершину оптимального пути, будет использоваться обозначение P (x 0, N).
Очевидным образом определение оптимального пути переносится на случай минимизации (вместо максимизации) веса. Заметим, однако, что в рассмотренных в главе 8 задачах на крат-чайшие пути не предполагалась, что число дуг в рассматриваемых путях фиксировано. Для су-ществования решения там требовались дополнительные условия типа неотрицательности весов дуг или неотрицательности циклов. В данном случае при фиксированной длине пути множество путей всегда конечно и, следовательно, задача оптимизации (и на максимум, и на минимум) всегда имеет решение. Заметим также, что в общем случае оптимальный путь (далее для опре-делённости будем рассматривать задачу максимизации) может не быть простым путём или це-пью (см. определения в разделе 2.3). Это означает, что он может проходить несколько раз через одни и те же вершины и дуги.
Далее в этом разделе излагается хорошо известный метод поиска пути максимального ве-са при заданном начальном состоянии x 0 и заданной длине 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 0 и любой путь P длины r +1 с началом в вершине x 0. Следующей (т.е. второй) вершиной на пути P является некоторая вершина x. Вес W (P) пути P равен сумме двух слагаемых: веса w (x 0, x) первой дуги пути P и веса W (P’), где P’ – оставшаяся часть пути P от вершины x до его конца, длина которого равна r, т.е.
W (P) = w (x 0, x) + W (P’). (4)
Поскольку длина W (x, r) оптимального пути из x длины r предполагается известной, то из (4) сразу следует, что
W (P) ≤ w (x 0, x) + W (x, r), (5)
а поскольку вершина x была выбрана произвольно, то из (5) следует, что для веса оптимального пути с начальной вершиной x 0 и длиной r +1 выполняется равенство
W (x 0, r +1) = max x { w (x 0, x) + W (x, r)}. (6)
Формула (6) является, по сути, формулой перехода от размерности r к бóльшей размернос-ти r +1. Конечно, она позволяет найти не только оптимальные веса путей, но и сами эти пути, добавляя к началу известных путей длины r дугу (x 0, x), где x максимизирует правую часть (6). Наконец, при r = 1 оптимальные пути P (x,1) ищутся непосредственно из условия максимизации веса одной дуги с началом в вершине x:
W (x,1) = max y w (x, y). (7)
Как и ранее, рассматриваемые графы будем предполагать полными, а веса реально отсутствую-щих дуг будем считать равными −∞ (в задачах минимизации +∞).
Метод, основанный на проведённых простых рассуждениях, называется методом дина-мического программирования, а основное соотношение (6) называется уравнением Беллмана, по имени американского математика, первым сформулировавшим этот метод именно как об-щий метод решения многошаговых оптимизационных задач (не только дискретных) и решив-шим на его основе многие важные прикладные задачи.
Прежде чем идти дальше, приведём грубую оценку выигрыша, который может дать дина-мическое программирование. Число вершин в орграфе G обозначим через m. Для простоты предположим, что орграф является полным, т.е. из каждой вершины выходят дуги во все вер-шины, включая её саму (т.е. имеются петли при вершинах). Общее число путей длины N равно, очевидно, mN. В то же время число операций на каждом переходе к следующей размерности имеет порядок m 2, а общее число операций при N шагах имеет порядок Nm 2. При весьма скром-ных значениях m = 20 и N = 10 для числа операций при методе динамического программирова-ния имеем оценку 10*400 = 4000, в то время как при прямом переборе нужно проверить 2010 ≈ 1016 вариантов.
Как и в других случаях, для ручной реализации метода Беллмана целесообразно использо-вать специальные таблицы, которые будут последовательно заполняться. Для упрощения изло-жения такие таблицы будут рассмотрены в следующем примере.
Пример 1. Рассмотрим орграф, показанный на рис.8-3. Здесь он перерисован как рис.1. В качестве начальной вершины x 0 возьмём вершину 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
Дата добавления: 2015-10-16; просмотров: 83 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Предметный указатель | | | Модификация основной постановки |