Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 79
Текст из файла (страница 79)
Глава 15. Динамическое программирование 393 Третий этап: вычисление минимальных промежутков времени На данном этапе на основе уравнения (!5.1) и рекуррентных соотношений (!ч.б) н ('15.7) легко было бы записать рекурсивный алгоритм определения самого быстрого пути сборки автомобиля на заводе. Однако с таким алгоритмом связана одна проблема: время его работы экспоненциально зависит от п. Чтобы понять, почему это так, введем значения г; О), обозначающие количество ссылок в рекурсивном алгоритме на величины», [Я. Из уравнения (15.1) получаем: 7'1 (71) = 7'з (П) = 1.
(15.8) Из рекуррентных уравнений (! 5.6) и (15.7) следует соотношение г, (») = т, (»') = г, (» + 1) + гя (» + 1), (! 5.9) рлзтнзт %лу(а, 1, е, ж, и) 1 »1[Ц вЂ” е1 + а1 1 2»з[Ц вЂ” ез + а7д 3 Гог» -2!оп 4 7!о !1»1(» — Ц + а1 7 <»з(» 5 треп»"1 (»] — »1 [»' — Ц 6 !1(»] 1 7 е!яе»1(7] "- »з(,7 — Ц 8 !1(7] 7 — 2 9 П Уз(» Ц + пгг < Ь(» !О Феп Я»]»з(» — Ц !! 1,(,7] -- 2 !2 е!зе Я,7'] — Л[» — Ц !3 1г [»] — 1 — Ц + !З 7. 1 + а1 7. + П1 + 1г, 1 + а1 .
— Ц +1!7 !+ азу + П'7 7 + !1,7 — 1 + О2,7 справедливое при» = 1,2,..., и — 1. В упражнении !5.1-2 предлагается показать, что г; (») = 2" 7. Таким образом, к величине (1 (Ц алгоритм обращается 2" ' раз! В упражнении 15.1-3 предлагается показать, что полное количество обращений ко всем величинам», (7] равно б7 (2"). Намного лучших результатов можно достичь, если вычислять величины», (»] в порядке, отличном от рекурсивного. Обратите внимание, что при» > 2 каждое значение», (7] зависит только от величин»1(» — Ц и»я [» — Ц. Вычисляя значения», [»] в порядке увеличения номеров рабочих мест» — слева направо (см. рис.
! 5.26), — можно найти самый быстрый путь (и время его прохождения) по заводу в течение времени 6 (и). Приведенная ниже процедура Рлзтввт Юлу принимает в качестве входных данных величины а1 7, 11 7, е; и х„а также количество рабочих мест на каждом конвейере и: Часть |Ч. Усовершенствованные методы разработки и анализа 394 14 И ~1 [и] + х1 (,Тз [и] + хз 15 ФЬеп 7"* = 11[п]+ х1 16 1' = 1 17 еие 1 =,12[о] + х2 18 1* = 2 Процедура ГАЯтезт %Ау работает следующим образом.
В строках 1-2 с помощью уравнений (15.2) и (15.3) вычисляются величины ~з [1] и Тз [1]. Затем в цикле 1ог в строках 3-13, вычисляются величины г"; [Я и 1; Ы при г = 1,2 и 7' = 2, 3,..., и. В строках 4-8 с помощью уравнения (15.4) вычисляются величины 11 [7] и 11 [5], а в строках 9-13, с помощью уравнения (15.5), величины ,1з [7] н 1з [7]. Наконец, в строках 14-18 с помощью уравнения (15.1) вычисляются величины 7".* и 1*.
Поскольку строки ! — 2 и 14-18 выполняются в течение фиксированного времени, и выполнение каждой из и — 1 итераций цикла зог, заданного в строках 3-13, тоже длится в течение фиксированного времени, на выполнение всей процедуры требуется время, равное О (и). Один из способов вычисления значений 7".; [Я и 1; [)] — заполнение ячеек соответствующей таблицы.
Как видно из рис. 15.2б, таблицы для величин Д ~Я и 1; [5] заполняются слева направо (и сверху вниз в каждом столбце). Для вычисления величины Т"; [7] понадобятся значения 11 [7' — 1] и Тз [7 — 1]. Зная, что зги величины уже вычислены и занесены в таблицу, их можно просто извлечь из соответствующих ячеек таблицы, когда они понадобятся. Четвертый этап: построение самого быстрого пути После вычисления величин Д [5], 1'", 1; [7] и Г нужно построить последовательность решений, используемых в самом быстром пути сборки.
Ранее было рассказано, как зто можно сделать для примера, проиллюстрированного на рис. 15.2. Приведенная ниже процедура выводит в порядке убывания номера использующихся рабочих мест. В упражнении 15.1-1 предлагается модифицировать зту процедуру так, чтобы номера рабочих мест выводились в ней в порядке возрастания. Рщхт БтАт10из(1, п) 1 г — 1' 2 рпп1 "Конвейер " г ", рабочее место '* п 3 1ог 5' — и пои иго 2 4 до1 -1,[Я 5 рпп1 "Конвейер " г ", рабочее место " 7' — 1 В примере, приведенном на рис.
15.2, процедура Рщнт БтАтвэнз выведет такую последовательность рабочих мест: Глава 15. Динамическое программирование 395 Конвейер 1, рабочее место 6 Конвейер 2, рабочее место 5 Конвейер 2, рабочее место 4 Конвейер 1, рабочее место 3 Конвейер 2, рабочее место 2 Конвейер 1, рабочее место 1 Упражнения 15.1-1. Покажите, как модифицировать процедуру Ршнт Бтлтюнз, чтобы она выводила данные в порядке возрастания номеров рабочих мест.
(Указание: используйте рекурсию.) 15.1-2. С помощью уравнений (15.8) и (15.9) и метода подстановки покажите, что количество обращений г; Ц) к величинам Д Ц в рекурсивном алгоритме равно 2" 1. 15.1-3. Воспользовавшись результатом, полученном при выполнении упражнения 15.1-2, покажите, что полное число обращений ко всем величинам Г"; ] 1], выражающееся двойной суммой х ~~, т~ " г; (1), равно 2"+' — 2. 15.1-4.
В таблицах„содержащих величины Г"; ]Я и (з [2], общее количество ячеек равно 4и — 2. Покажите, как свести количество ячеек к 2и + 2 и при этом иметь возможность вычисления величины Г"* и вывода информации о всех рабочих местах, составляющих самый быстрый путь прохождения завода. 15.1-5. Профессор предположил, что могут существовать значения ео ану и 1;3, для которых процедура РАзтнзт %Ау дает такие значения 1; ]3], что для некоторого рабочего места 2 11 и = 2 и 1з ]3] = 1. Принимая во внимание, что все переходы выполняются в течение положительных промежутков времени Ц 1, покажите, что предположение профессора ложно. 15.2 Перемножение цепочки матриц Следующий пример динамического программирования — алгоритм, позволяющий решить задачу о перемножении цепочки матриц.
Пусть имеется последовательность (цепочка), состоящая из п матриц, и нужно вычислить их произведение А1Аг .. А„. (15.10) Выражение (15.10) можно вычислить, используя в качестве подпрограммы стандартный алгоритм перемножения пар матриц. Однако сначала нужно расставить скобки, чтобы устранить все неоднозначности в порядке перемножения. Порядок Часть !У. Усовершенствованные методы разработки н анализа 396 произведения матриц нолноспвь о определен скобками (Гп)!у рагеп!йез!ге4!), если произведение является либо отдельной матрицей, либо взятым в скобки произведением двух подпоследовательностей матриц, в котором порядок перемножения полностью определен скобками.
Матричное умножение обладает свойством ассоциативности, поэтому результат не зависит от расстановки скобок. Например, если задана последовательность матриц (Аы Аг, Аз, А4), то способ вычисления их произведения можно полностью определить с помощью скобок пятью разными способами: (А1(Аг(АзА4))), (А1((Аг Аз) А4) ), ((А1Аг)(АзА4)), ((А!(АгАз))А4), (ЯА1Аг)Аз)А4) . От того как расставлены скобки при перемножении последовательности матриц, может сильно зависеть время, затраченное на вычисление произведения.
Сначала рассмотрим, как определить стоимость произведения двух матриц. Ниже приводится псевдокод стандартного алгоритма. Атрибуты тоша и со!итпз означают количество строк и столбцов матрицы. МАтих М!лтпчу(А, В) ! !Г со!итппз[А] ф. тошз[В] 2 гпеп еггог "Несовместимые размеры'* 3 е!зе Гог ! — 1 го тоша[А] 4 бо !ог г — 1 ге со!итппз[В] 5 до С[1, г'] - О б !ог к — 1 го со!итпз[А] 7 до С[1, г] — С[4,2]+ А[1, К] В[к,Я 8 гегпгп С Матрицы А и В можно перемножать, только если они соамесгпимы: количество столбцов матрицы А должно совпадать с количеством строк матрицы В. Если А — это матрица размера р х 9, а  — матрица размера д х т, то в результате их перемножения получится матрица С размера р х т.
Время вычисления матрицы С преимущественно определяется количеством произведений скаляров (далее в главе для краткости будем называть эту операцию скалярным умножением— Прим. перев.), которое выполняется в строке 7. Это количество равно рот. Итак, стоимость умножения матриц будет выражаться в количестве умножений скалярных величин. Чтобы проиллюстрировать, как расстановка скобок при перемножении нескольких матриц влияет на количество выполняемых операций, рассмотрим при- Глава 15. Динамическое программирование 397 мер, в котором перемножаются три матрицы (Аы Аго Аз).
Предположим, что размеры этих матриц равны 10 х 100, 100 х 5 и 5 х 50 соответственно. Перемножая матрицы в порядке, заданном выражением ((А|Аз) Аз), необходимо выполнить 10 100 . 5 = 5 000 скалярных умножений, чтобы найти результат произведения А|Аз (при этом получится матрица размером 10 х 5), а затем — еще 10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
