Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. I. МЕТОДЫ РАСКОПОК
  2. I. Научно-методическое обоснование темы.
  3. I. Научно-методическое обоснование темы.
  4. I. ОСНОВНЫЕ ПРИНЦИПЫ ПОЛИТИКИ ПЕРЕМЕН
  5. I. Структурные принципы
  6. II. Строительная техника, принципы декора.
  7. III)Методики работы над хоровым произведением

Дадим более подробное описание рассматриваемой общей задачи многошаговой оптими-зации. Предполагается, что задан простой ориентированный взвешенный граф 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 | Нарушение авторских прав

Читайте в этой же книге: Определение потоковой сети. | Модификация основной постановки | Поиск максимального потока. | Утверждение 5. | Понятие кратчайшего пути | Алгоритм Дейкстры | Алгоритм Флойда-Уоршолла | Минимаксная модификация задачи о кратчайших путях | Максимальные паросочетания | Задача назначения |
<== предыдущая страница | следующая страница ==>
Предметный указатель| Модификация основной постановки
mybiblioteka.su - 2015-2024 год. (0.019 сек.)