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

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

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

Далее в этом разделе излагается хорошо известный метод поиска пути максимального ве-са при заданном начальном состоянии x0и заданной длине 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). Рассмотрим теперь фиксированную вершину x0 и любой путь P длины r+1 с началом в вершине x0. Следующей (т.е. второй) вершиной на пути P является некоторая вершина x. Вес W(P) пути P равен сумме двух слагаемых: веса w(x0, x) первой дуги пути P и веса W(P’), где P’ – оставшаяся часть пути P от вершины x до его конца, длина которого равна r, т.е.

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

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

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

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

W(x0, r+1) = maxx {w(x0, x) + W(x, r)}. (6)

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

W(x,1) = maxyw(x, y). (7)

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

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

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

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

Пример 1. Рассмотрим орграф, показанный на рис.8-3. Здесь он перерисован как рис.1. В качестве начальной вершины x0 возьмём вершину 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