XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 57
Текст из файла (страница 57)
МЕТОД ДИСКРЕТНОГО ДИНАМИ'ЧЕСКОГО ПРОГРАММИРОВАНИЯ Метод дискретного динамического программирования является одним из наиболее эффективных методов реализации многошаговых задач принятия решений в условиях определенности. Приступая к изучению этого метода, заметим, что каждая многошаговая процедура принятия решений в условиях определенности соответствует вполне конкретной задаче выбора кратчайшего (или самого длинного) пути в некоторой ацикличесноб сети. В любой ациклической сети есть лишь один узел-источник, т.е.
узел сети, в который не входит ни одна ориентированная дуга. Это следует из того, что рассматриваемые нами системы имеют единственное начальное и единственное конечное состояния. Напомним, что к задаче выбора кратчайшего пути была преобразована задача о замене оборудования (см. пример 5.6). Одна из специфических особенностей любой ациклической сети состоит в том, что возможна нумерация узлов сети, прн которой для каждой ориентированной дуги (1, у), выходящей из узла с номером 1 и входящей в узел с номером 1', будет иметь место неравенство ~ < 1. Процедура такой нумерации состоит из нескольких этапов. Сначала узлу ациклической сети, в который не входит ни одна ориентированная дуга, присваивают номер 1 и вычеркивают ориентированные дуги, выходящие из него.
После этого в сети выделяется п1 узлов, в каждый из которых не входит ни одна из ориентированных дуг, Этим узлам (в любой последовательности) присваивают номера от 2 до п1+ 1 и вычеркивают ориентированные дуги, выходящие из них. После этого в сети образуется пз узлов, в каждый из которых не входит ни одна из ориентированных дуг, и рассуждения, проведенные выше, повторяют до тех пор, пока не будут пронумерованы все узлы рассматриваемой ациклической сети. Пример П2.1. Пронумеруем узлы ациклической сети, изображенной на рис. П2.1, так, чтобы для любой ее ориентированной дуги (1, 1) имело место неравенство 1 < у.
Рис. П2.1 В соответствии с описанной выше процедурой нумерации узлов ациклической сети, этапы которой частично отражены на рис. П2.2, приходим к результату представленному на рис. П2.3. Рис. П2.2 Рис. П2.3 409 Л = ппп (Д+с;,), ~ег(1) (П2.1) Рис.
П2.4 о < — ппп (о;, о;+с; ), ~е1(11 408 ПРИЛОжКНИК г. дИНЛМИЧКСКОК ПРОГрлММИРовлник Далев будем предполагать, что для ациклической сети выполнены следующие условия: а) узлы сети пронумерованы так, что для любой ее ориентированной дуги ((, г) имеет место неравенство ( < г'; б) для каждой ориентированной дуги (1, г) указана ее длина с; (например, на рис.
П2.3 имеем сг5 = 12, свз — — 10). В этих условиях под длммоб путям от (-го узла ациклической сети до ее 1'-го узла, где ( < г', будем понимать сумму длин входящих в этот путь дуг. Пусть ациклическзя сеть содержит М узлов и необходимо найти кратчайший путь от ее 1-го до ДГ-го узла. Постановка этой задачи и метод ее решения уже известны (см. 5.4 и 5.5), но мы рассмотрим другой подход. Обозначим через Л длину кратчайшего пути от узла 1 ациклической сети до ее узла (, и пусть Л = О. В этом случае й+ с; — длина кратчайшего путй от узла 1 до узла (, где ( < г, при условии, что дуга (1, г) является последней дугой этого пути.
Кратчайший путь от узла 1 до узла г должен содержать некоторую дугу в качестве конечной, и поэтому где Цг) — множество номеров тех вершин рассматриваемой ациклической сети, из которых выходят ориентированные дуги, входящие в узел г'. А так как для всех ориентированных дуг ((, г), входящих в узел г, имеет место неравенство ( < г, то соотношение (П2.1) может быть использовано для последовательного вычисления значений гг, гз, ..., ~н, и мы приходим к следующему алгоритму нахождения кратчайшего пути в ациклической сети. Шаг 1. Полагаем о, =О, ол =ос, 1=2,Ж, г = 2.
Переходим к шагу 2. Ш а г 2 . Вычисляем где запись х ~ — р означает, что переменное х принимает значение у. Переходим к шагу 3. Ш аг 3. Если г = Ю то прекращаем вычисления. Если г' < М, то выполняем присвоение г +- г'+ 1 и переходим к шагу 2. Рассмотренный алгоритм позволяет находить не сам кратчайший путь, а его длину. Для нахождения кратчайшего пути необходимо запоминать номера дуг ((, г), которые составляют путь длиной о .
В примере П2.2 такие дуги для наглядности дополнительно помечены штриховой линией. Пример П2.2. Используем изложенный алгоритм для нахождения кратчайшего пути от узла 1 до узла 9 в ациклической сети, изображенной на рис, П2.3. Ш а г 1 . Полагаем о1 — — О, оь = со, Й = 2, 9, ( = 2. Переходим к шагу 2. Шаг 2. Вычисляем ог '.— ш(п(ог, о1+с1г)=ппп(оо, О+1)= =1, учитывая, что в узел 3 входит единственная дуга (1, 3).
Фиксируем ориентированную дугу (1, 3), выделив ее штриховой линией (рис. П2.4) и переходим к шагу 3. Ш аг 3. Так как г = 2 < 9 = М, то полагаем г' = 3 и переходим к шагу 2. Шз г 2. Вычисляем оз+-ш1п(оз, о1+с1з) =ппп(со, О+2)= =2, учитывая, что в узел 3 входит единственная дуга (1, 3). Фиксируем ориентированную дугу (1, 3), отметив ее штриховой линией, переходим к шагу 3. Ш а г 3 . Так как г = 3 < 9 = Л, полагаем ~' = 4 и переходим к шагу 2.
410 ПРИЛОЖЕНИЕ 2, ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Шаг 2. ПРисваиваем о4+- пйп(о4 ог+см, оз+сз4)— = ппп(оо, 1+6, 2+3) = 5, учитывая, что в узел 4 входят дуги (2, 4), (3, 4). Фиксируем ориентированную дугу (3, 4), отмечаем ее штриховой линией и переходим к шагу 3. Ш а г 3 . Так как 1 = 4 ( 9 = 11', полагаем 1' = 5 и переходим к шагу 2. Ш а г 2. Присваиваем оз 4 — ш1п1оз ог+ сзз о4+ с48) = = ппп(ао, 1+12, 5+4) = 9, учитывая, что в узел 5 входят дуги (2, 5), (4, 5).
Фиксируем ориентированную дугу (4, 5), отмечаем ее штриховой линией и переходим к шагу 3. Шаг 3. Так как 1= 5(9= У, полагаем 1'= 6 и переходим к шагу 2. Шаг 2. Присваиваем ое 4 — пйп(ое, оз+сзе, о4+слв) = = пйп(оо, 2+4, 5+2) = б, учитывая, что в узел 6 входят дуги (3, б), (4, 6). Фиксируем ориентированную дугу (3, 6), отмечаем ее штриховой линией и переходим к шагу 3. Ш а г 3. Так как 1 = 6 < 9 = Х, полагаем 7' = 7 и переходим к шагу 2. Ш аг 2. Присваиваем о1 4 — пйп(от, о4+с41, оз+с81) = = ш1п(оо, 5+15, 9+7) = 16, учитывая, что в узел 7 входят дуги (4, 7), (5, 7). Фиксируем ориентированную дугу (5, 7), отмечаем ее штриховой линией и переходим к шагу 3.
Шаг 3. Так как 1=7 < 9= Х, полагаем 1'=8 и переходим к шагу 2. Шаг 2. Присваиваем ое ппп(оа, о4+с48 об+ с68) = = ппп(оо, 5+7, 6+7) = 12, учитывая, что в узел 8 входят дуги (4, 8), (б, 8). Фиксируем ориентированную дугу (4, 8), отмечаем ее штриховой линией и переходим к шагу 3. Ш а г 3. Так как 1 = 8 < 9 = М, полагаем у' = 9 и переходим к шагу 2. Ш а г 2. Вычисляем оз+-ш1п1ое, об+сея, о1+с18, ов+сяэ) = = пни(оо, 6+15, 16+3, 12+10) = 19, учитывая, что в узел 9 входят дуги (6, 9), (7, 9), (8, 9). Фиксируем ориентированную дугу (7, 9), отмечаем ее штриховой линией и переходим к шагу 3. 411 Шаг 3. Так как 4'= 9= г1, вычисления прекращаем. Кратчайший путь найден: 1 — >3 — >4-454 7-49.
Его длина (см. рис. П2.4) равна 2+ 3+4+7+3 = 19. Для наглядности для каждого узла укажем длину кратчайшего пути до него от узла 1 (рис. П2.5). Итак, рассмотренный алгоритм позволяет находить кратчайший путь от узла 1 до любого узла сети. 1 е 16 Рис. П2.8 Алеормпзля маяоз4сдеммя в ациклической сети мамболее длиммоео пу414м аналогичен рассмотренному алгоритму выбора кратчайшего пути и отличается от последнего лишь тем, что на шаге 1 начальные значения оь берутся равными — оо (при Й ф 1), а на шаге 2 вместо минимума нужно определять максимум.
Пример П2.3. В ациклической сети из предыдущего примера (см. рис. П2.3) рассмотрим задачу поиска наиболее длинного пути от узла 1 до узла 9. На первом шаге полагаем о1 — — О, оь = — со, к = 2, 9, и 1 = 2. ПеРехоДим к шагУ 2. ПРисваиваем оз 4 — шах(оз, о1+с11) = = шах( — оо, 0+1) = 1, учитывая, что в узел 2 входит единственная дуга (1, 2). Отмечаем зту дугу и переходим к шагу 3, На третьем шаге, так как 1 = 2 < 9 = 11', полагаем у' = 3 и снова переходим к шагу 2. Дальнейший ход решения не вызывает затруднений. Окончательный результат представлен на рис. П2.6, на котором для каждого узла указана наибольшая длина пути до него от узла 1. 412 ПРИЛОЖЕНИЕ 2. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 1 19 99 Рис.
П2.6 413 Заметим, что использование нумерации узлов ациклической сети, при которой для всех ориентированных дуг (1, у) выполнено неравенство 1 > «', приводит к изменению порядка отсчета узлов: в задаче поиска кратчайшего 1наиболее длинного) пути длина пути отсчитывается не от его начала, а от конца. На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
