Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 78
Текст из файла (страница 78)
15.2 а, полное время получается наименьшим, если на первом конвейере выбираются рабочие места 1, 3 и 6, а на втором — места 2, 4 и 5. На рисунке указаны величины е„а,, Рг и жь Самый быстрый путь через фабрику выделен жирной линией. В части б рисунка приведены величины Д (з], г"', 1; ]з] и 1*, соответствующие примеру, изображенному в части а (о том, что означают эти величины, будет сказано немного позже). Очевидный метод перебора, позволяющий минимизировать время сборки на конвейерах с малым числом рабочих мест, становится неприменимым для большого количества рабочих мест. Если заданы списки рабочих мест, которые исполь- Глава 15.
Динамическое программирование 389 Рабочее Рабочее Рабочее Рабочее Рабочее Рабочее место бш место 52 2 место З2 э место 52 6 место 5; 5 место З2 6 Сб кои Выход готоаого аатомобида Запуск шасси Сбо ко Рабочее Рабочее Рабочее место 52 2 место 52,2 место 52,2 Рабочее Рабочее Рабочее местобт,я место525 место526 а) 2 2 Э Я 5 6 У 2 Э Я 5 6 Л И, $" .)Ва 2У ач) ЗЯ:: ср) 2)о )б. 2ь дз 29 зр У =)В 22И й":сэ:!В,'Ч;1'~:,: 22И фб)э.б)аа;,.дэ г=! б) Рис. 15.2. Пример задачи на составление расписания сборочного конвейера зуются на первом и втором конвейерах, то время полного прохождения шасси по конвейеру легко вычислить за время 0(п).
К сожалению, всего существует 2" возможных комбинаций. Это легко понять, рассматривая множество рабочих мест первого конвейера как подмножество множества 11, 2,..., Эф очевидно, что всего существует 2" таких подмножеств. Таким образом, способ, при котором наиболее рациональное прохождение по конвейеру определяется методом перебора всех возможных вариантов, в результате чего определяется время сборки для каждого варианта, занял бы время, равное й (2"). Очевидно, что при больших п этот способ неприемлем. Первый этап: структура самой быстрой сборки В парадигме динамического программирования первый этап заключается в том, чтобы охарактеризовать структуру оптимального решения.
В задаче по составлению расписания работы конвейера этот шаг можно выполнить следующим образом. Рассмотрим способ, при котором шасси, поступившее на первый конвейер, попадет на рабочее место о) за кратчайшее время. Если 2 = 1, существует всего один способ прохождения такого отрезка пути, поэтому легко определить время достижения рабочего места о) .
Однако если ) = 2,3,..., п, возможен один из двух вариантов: на рабочее место о) шасси могло попасть непосредственно с рабочего места о) 2 или с 5 2. В первом случае временем перехода 390 Часть 1Ч. Усовершенствованные методы разработки и анализа от одного рабочего места к другому можно пренебречь, а во втором переход займет время тз„ г. Рассмотрим обе этн возможности отдельно, хотя впоследствии станет ясно, что у них много общего. Сначала предположим, что самый быстрый путь, проходящий через рабочее место 5з;, проходит также через рабочее место 51 1.
Основной вывод, который можно сделать в этой ситуации, заключается в том, что отрезок пути от начальной точки до 51 . з тоже должен быть самым быстрым. Почему? Если бы на это рабочее место можно было бы попасть быстрее, то при подстановке данного отрезка в полный путь получился бы более быстрый путь к рабочему месту 51 „;, а это противоречит начальному предположению. Теперь предположим, что самый быстрый путь, проходящий через рабочее место 51, проходит также через рабочее место 5з ~ 1.
В этом случае можно прийти к выводу, что на рабочее место 5з 1 шасси должно попасть за кратчайшее время. Объяснение аналогично предыдущему: если бы существовал более быстрый способ добраться до рабочего места 5з ы то при подстановке данного отрезка в полный путь получился бы более быстрый путь к рабочему месту 51 э а это снова противоречит сделанному предположению.
Обобщая эти рассуждения, можно сказать, что задача по составлению оптимального расписания (определение самого быстрого пути до рабочего места 5;,з) содержит в себе оптимальное решение подзадач (нахождение самого быстрого пути до рабочего места 51 1 нли 5з 1). Назовем это свойство олтимальной лодсшрукюиурой (ероша! зиЬзггисшге). В разделе 15.3 мы убедимся, что наличие этого свойства — один из признаков применимости динамического программирования. С помощью свойства оптимальной подструктуры можно показать, что определение оптимального решения задачи сводится к определению оптимального решения ее подзадач. В задаче по составлению расписания работы конвейера рассуждения проводятся следующим образом. Наиболее быстрый путь, проходящий через рабочее место 51, должен также проходить через рабочее место под номером з' — 1, расположенное на первом или втором конвейере.
Таким образом, если самый быстрый путь проходит через рабочее место 5гз, то справедливо одно из таких утверждений: ° этот путь проходит через рабочее место 51 и после чего шасси попадает непосредственно на рабочее место 51 ° этот путь проходит через рабочее место 5э и после чего автомобиль перебрасывается из второго конвейера на первый, а затем попадает на рабочее место 51 Из соображений симметрии для самого быстрого пути, проходящего через рабочее место 5з,э справедливо одно из следующих утверждений: Глава 15.
Динамическое программирование 391 ° этот путь проходит через рабочее место Яз и после чего шасси попадает непосредственно на рабочее место Язб, ° этот путь проходит через рабочее место 5~3 и после чего автомобиль перебрасывается из первого конвейера на второй, а затем попадает на рабочее место Язб. Чтобы решить задачу определения наиболее быстрого пути до рабочего места з, которое находится на любом из конвейеров, нужно решить вспомогательную задачу определения самого быстрого пути до рабочего места 3 — 1 (также на любом из конвейеров). Таким образом, оптимальное решение задачи об оптимальном расписании работы конвейера можно найти путем поиска оптимальных решений подзадач.
Второй этап: рекурсивное решение Второй этап в парадигме динамического программирования заключается в том, чтобы рекурсивно определить оптимальное решение в терминах оптимальных решений подзадач. В задаче по составлению расписания работы конвейера роль подзадач играют задачи по определению самого быстрого пути, проходящего через з-е рабочее место на любом из двух конвейеров для 3 = 2, 3,..., и. Обозначим через г"; [Я минимально возможное время, в течение которого шасси проходит от стартовой точки до рабочего места Я; . Конечная цель заключается в том, чтобы определить кратчайшее время г"', в течение которого шасси проходит по всему конвейеру.
Для этого автомобиль, который находится в сборке, должен пройти весь путь до рабочего места и, находящегося на первом или втором конвейере, после чего он покидает фабрику. Поскольку самый быстрый из этих путей является самым быстрым путем прохождения всего конвейера, справедливо следующее соотношение: =пцп®[п]+х~ ~з[п]+ха). (15.
1) Легко также сделать заключение по поводу величин ~~ [1] и Гз [1]. Чтобы за кратчайшее время пройти первое рабочее место на любом из конвейеров, шасси должно попасть на это рабочее место непосредственно. Таким образом, можно записать уравнения ,1з [1] = ез + аз ы У2 [Ц ез + овд (15.2) (15.3) А теперь рассмотрим, как вычислить величину г"; Ц при з' = 2, 3,..., и (и г = = 1, 2).
Рассуждая по поводу ~~ [) ], мы пришли к выводу, что самый быстрый путь до рабочего места 5~3 является также либо самым быстрым путем до рабочего Часть 1Ч. Усовершенствованные методы разработки и анализа 392 места 5~ и после чего шасси попадает прямо на рабочее место 5~3, либо самым быстрым путем до рабочего места ог и с последующим переходом со второго конвейера на первый. В первом случае можно записать соотношение ~~ [7] = = ~з [7' — Ц + азб, а во втором — соотношение Л [7] = )г [7 — Ц+ арго ~ + атб.
Таким образом, при 7' = 2, 3,..., п выполняется уравнение ~~ [Я = ш)п()~ [7 — Ц+ а~о,Л [7 — Ц+ тг3 з+ аду). (15.4) Аналогично можно записать уравнение ~г[7] = ш1п(~г[7 — Ц+аго А [7 Ц+11д 1 +ого). Комбинируя уравнения (15.2)-(15.5), получим рекуррентные соотношения (15.5) е ~ + а~ з ш(п(Л [7 Ц+аьй Я[7 Ц+1гн ~ + аьу) ег+агл т)п (~г [г — Ц + аг у, Л [т' — Ц + тз3 з + агб) (15.6) при 7' > 2. (15.7) при 7' > 2.
На рис. 15.2б приведены величины 7"; [Я, соответствующие примеру, изображенному на рис. 15.2а, и вычисленные по уравнениям (15.6) и (15.7), а также величина г'. Величины Л [7] являются значениями, соответствующими оптимальным решениям подзадач. Чтобы было легче понять, как конструируется оптимальное решение, обозначим через 1; [)] номер конвейера (1 или 2), содержащего рабочее место под номером 7' — 1, через которое проходит самый быстрый путь к рабочему месту Я;3. Индексы 1 и 7' принимают следующие значения: 1 = 1, 2; 7' = 2, 3,..., п. (Величины 1; (Ц не определяются, поскольку на обоих конвейерах отсутствуют рабочие места, предшествующие рабочему месту под номером 1.) Кроме того, обозначим через 1* номер конвейера, через и-е рабочее место которого проходит самый быстрый полный путь сборки. Величины 1; [7] облегчат определение самого быстрого пути. С помощью приведенных на рис.
15.2б величин 1' и 1; [7] самый быстрый способ сборки на заводе, изображенном на рис. 15.2а, выясняется путем таких рассуждений. Начнем с 1* = 1; при этом используется рабочее место Я~ в. Теперь посмотрим на величину 1~ [б], которая равна 2, из чего следует, что используется рабочее место Ягы Продолжая рассуждения, смотрим на величину 1г [5] = 2 (используется рабочее место Яг 4), величину 1г (4] = 1 (рабочее место Я~ 3) величину 1~ (3] = 2 (рабочее место Яг г) и величину 1г [2] = 1 (рабочее место 5~3).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
