Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 9
Текст из файла (страница 9)
В этой главе мы намерены рассмотреть в деталях некозорые простые задачи с тем, чтобы впоследствии, когда мы перейдем к более трудным задачам, не возникало никаких вопросов, связанных с основными идеями. 46 одномввныв пгоцрссы васпввдвлвния, (гл. т 18. БЛОК. СХЕМА ВЫЧИСЛИТЕЛЬНОГО ПЛАНА ДЛЯ ОБЩЕГО ПРОЦЕССА РАСПРЕДЕЛЕНИЯ Обсуждая сведение задач от математической постановки к программе для вычислительной машины, что займет большую часть нашего последующего изложения, мы будем часто пользоваться блок-схемами.
Они представляют собой диаграммы, разлагающие вычислительный процесс на его составные части и показывающие эти;части достаточно подробно, чтобы их легко можно было программировать, даже не будучи хорошо знакомым с первоначальной математической задачей или методом. Следуя одной из этих схем, можно точно проследить, как задача может быть решена численно (рис. 9). Так как настоящий пример является вводным, мы теперь далил~ детальное объяснение различным этапам. Встречающиеся в дальнейшем блок-схемы будут нме~ь аналогичную структуру, и к ним не будет даваться дополнительных объяснений, Э т а п 1. Основная программа будет применять рекуррентное соотношение (1.22),чтобы вычислить таблицу значений функции /а (е), используя Уа, (х). Для того чтобы включить сюда начальный шаг вычислений — уравнение (1.20), которое дает ~, (х) в пределах общей процедуры, — мы определяем функцию г,(х), тождественно равную нулю.
С помощью этого мы избегаеч составления особой программы для определения у, (х). На практике запоминание нулей выполняется просто посредством установки всей памяти на нуль до введения перфокарт с исходными данными. Тогда область, обозначенная как Г"„(х), автоматически является нулем. Мы можем теперь заставить вычислительную машину определять /, (х), используя уа(х),тем же способом, как она определяет ~,(х) на основе ~„,(х).
Несмотря на то, что У,(х) может быть вычислена гораздо быстрее непосредственно 'из уравнения (1.20), экономйя, получаемая вышеуказанным путем в об.ьеме и времени программирования, вполне компенсирует наше рассмотрение. Интуитивное оправдание равенства нулю функции г"„(х) состоит в том, что, каково бы ни было исходное количество ресурсов, не может быть никзкого дохода при полном отсутствии способов производствз.
В некоторых других процессах нераспределенные ресурсы будут иметь некоторую стоимость, и эта стоимость будет взята равной уа(х). 18) БЛОК-СХВМА ПРОЦВССА РАСПРВДЕЛБНИЯ Э т з п 2. Индекс й будет обознзча|ь число способов, комы ассматриваем (ср. э 3). Вначале мы возьь»йл» за- торые р дачу, включающую только один способ. 11алее индекс л будет возрастать по мере рззвер| ывания вычислений (см. этап 16), Этап 3. Будем вычислять таблицу значений, представляющую функцию у» (х) в дискре»ных точкзх. Начальнсе значение аргуме|ыа х, для которого нужно вычисли~ь у» (х), равно нулю. Вычислив и ззпомнив Г» (О), иы вычисляем Г» (Ь), за»ем г"»(2ц) и г.д. до тех пор, пока не заполнии всю таблицу.
Э г з и 4. Внутренняя рзбсчая ячейка памяти Р будет содержать «наилучший доход до сих пор», ко~да мы испытываем различные поведения, разыскивзя максимизирующее. Записывая с самого начала в ячейку большое (по модулю) отрицательное число (обозначенное через — сс», но, конечно, не являющееся действи»ельной бесконечностью), мы обеспечиваем, чго испьпывземое первое решение о поведении будег принято ка|» «наилучп»ее до сих поря.
Как и на этапе 1, это— искусственный элемен|, вводимый, чтобы избежать рассмо»рения первого шага процесса в виде особого случая. Э т а п 5. Мы применяем обозначение хя(х), чтобы указать, что наше решение о распределении дало количество начального ресурса х на шаге Рис. 9. Й. Так как сначзла»1=1 и 48 одномвгныв пгоцвссы влспввдвлвния 1гл. 1 .с=О, мы испытываем 0 в качестве начального значения для х,(О). Этап б. Этот этап составляет главную часть вычислений. Только что мы детализировали шаг (а: ресурсы х и распределение хя(х).
Используя функцию дохода 8а(ха) и оптимальный доход на (7г — 1)-м шаге Уа,(х — хя), мы вычисляем общий доход, связанный с данным решением на данном шаге, и запоминаем это число в ячейке ю Этап 7. Сравним это число с числом в ячейке р, наилучшим доходом от всех ранее испытанных поведений для этого частного состояния и шага. Если текущее решение дает меньший доход, чем некоторое предыдушее решение, переходим к этапу 9. Если это — наилучшее решение о распределении среди испытанных до сих пор, выполняем этап 8.
Э т а п 8. Заменим содержимое ячейки 8 большим доходом, который как раз и хранился в ячейке ю (Там, где смысл очевиден, мы не будем стараться проводить различие в обозначениях между наименованием ячейки и ее содержимым.) Ячейка Т должна содержать «наилучшее поведение до сих пор», следовательно, мы помепшем х„ в ячейку Т. Э г а п 9. Исследовзв эффект назначения количесгва х,, для 7г-го способа, мы теперь готовимся испытать большее назначение х, + Ь.
Этап 1О. Является ли это назначение ббльшим, чем наше начальное количество ресурсов х? Если да, то это решение недопустимо и мы переходим к этзпу 11. Если ха+Ь вЂ” допустимое решение, мы возвращаемся к этапу б, чтобы оценить это решение и сравнить его с предыдушими. Этап 11, Мы только что сравнили все решения для определенного начального количества ресурсов х. Запомним максимальный достижимый доход у„(х) и решение, дающее э~ог доход х„(х).
Этап !2. Увеличим первоначальное количество ресурсов на Ь. Мы теперь имеем новую зздачу, включаюшую то же самое число технологических процессов, но с несколько ббльшим начальным количеством ресурсов. Этап 13. Если новая задача включает количество ресурсов большее, чем то, с которого мы начали задзчу с 11г про цессами, мы, очевидно, не можем достигнуть задачи с А про. цессами и этим большим количеством ресурсов и нам не нужно вычислять этот результат.
Таким образом, мы завер- 49 19) числвнныв Рязхльт'хты шили вычисление таблицы значении' у„(х) и переходим к эгапу 14. Если этот новый х допустим, мы начинаем несь процесс максимизации снова, возвращаясь к этапу 4. Этап 14. «Вывод» резульгатов текущего этапа. Эти резулыаты, и в частности политика в виде некоторой функции количества ресурсов, будут использованы позже, чтобы определить действительное оптимальное поведение, и поэтому должны бьыь записаны на ленте или отперфорированы на картах.
Этап 1о. 1!рограмма относится к некоторым ячейкам памяти, в когорых она отыскиваег у„,(ж), и к друтим ячейкам, где она запоминает новую таблицу уа(х). В этом месте в программе мы завершили применение старой таблицы для вычисления новой. С этого момента мы будем использовать новую таблицу 7«(х) для вычисления 7««г(х). Так как 7«(х) должна теперь играть роль «старой» таблицы, гораздо легче и более действенно заново внесги ее в памягь, чем изменить адреса всех ссылок для нее в программе. Это новое размещение целого массива памяги называется «переносом блока» и выполняегся в долю секунды.
Этап 16. Теперь мы переходим к следукащему способу и готовимся решагь семейство задач, включающих 9-~- 1 вместо 7« процессов. Э т а и !7. Если мы нычислили именно У,(х), то 7г = Аг и /г + 1 = Лг + 1 больше, чем М. Мы тогда останавливаемся н объявляем вычисления ззконченными. Если же 7г меньше нли равно М, мы возвращаемся к этапу 3.
Это завершаег ггаш анализ действительных операций, производимых вычислительной машиной. На всем протяжении книги мы неоднокрапю будем ссылаться на счатистику вычислений, основанную на нашем опыте работы с вычислительной машиной КАНО-Джонниак. Списание машины дано в приложении У.
!9. ЧИСЛЕННЫЕ РЕЗУЛЬТАТЫ В предшествующем разделе мы описали действительные этапы вычислительного решения общей задачи распределения ресурсов. В ходе решения мы получили ряд из Аг табчнц, каждая из когорых доставляет общий доход и начальное поведение для фиксированного числа способов и некоторого интервала значений начальных ресурсов, 50 одномвнныв пеоцвссы васпввдвлвния [гл. ! Использование этих тзблиц для определения решения частной задачи (при,данном числе способов и данном начальном состоянии) составляет вторую и отличную фазу вычислений.
Метод упомянут кратко в последней части й 14. Здесь мы хотим обсудить этот метод более подробно и попутно обеспечи~ь логическую программу для вычислений. Основное соображение заключается в том, что последняя таблица выдает оптимальное начальное распределение для процесса, в котором учзсы л/- /г вует /т/ способов; оно в свою очередь определяет началь.гл -ж нос состояние для задач, включающих /т/ — 1 спосо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
