Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 77

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 77)

43-47).— Прим, ред. Часть!П. Структуры данных 382 Иосифа целых чисел 1, 2,..., и. Например, (7, 3)-перестановка Иосифа имеет вид (3,6,2,7,5,1,4). а) Пусть тп — некоторая фиксированная константа. Разработайте алгоритм, который для данного и за время О (тт) выводит (и, т)-перестановку Иосифа.

б) Пусть т не является константой. Разработайте алгоритм, который для данных п и т за время О (и 18 и) выводит (и, тп)-перестановку Иосифа. Заключительные замечания В книге [247) Препарата (Ргерагага) и Шамос (балашов) описывают ряд деревьев отрезков, встречавшихся литературе, и приводят результаты из работ Эдельсбруннера (Н.

Ебе1зЬп~ппег, 1980) и Мак-Крейта (МсСге18пй 1981). В книге приведено дерево отрезков, в котором для данной статической базы данных из и отрезков все к отрезков, перекрывающихся с заданным, могут быль найдены за время О(1с+ 18п). ЧАС ТЫУ Усовершенствованные методы разработки и анализа Введение В этой части описаны три важных метода разработки и анализа эффективных алгоритмов: динамическое программирование (глава 15), жадные алгоритмы (глава ! 6) и амортизационный анализ (глава 17). В предыдущих частях были представлены другие широко распространенные методы, такие как метод разбиения, рандомизация и решение рекуррентных соотношений. Новые подходы, с которыми нам предстоит ознакомиться в этой части, более сложные, однако они полезны для решения многих вычислительных задач. К темам, рассмотренным в данной части, мы еще обратимся в последующих частях.

Динамическое программирование обычно находит применение в задачах оптимизации, в которых для получения оптимального решения необходимо сделать определенное множество выборов. После того как выбор сделан, часто возникают вспомогательные подзадачи, по виду напоминающие основную. Динамическое программирование эффективно тогда, когда определенная вспомогательная подзадача может возникнуть в результате нескольких вариантов выборов. Основной метод решения таких задач заключается в сохранении решения каждой подзадачи, которая может возникнуть повторно.

В главе 15 показано, как благодаря этой простой идее алгоритм, время решения которого экспоненциально зависит от объема входных данных, иногда можно преобразовать в алгоритм с полиномиальным временем работы. Жадные алгоритмы, как и алгоритмы, применяющиеся в динамическом программировании, используются в задачах оптимизации, для рационального решения которых требуется сделать ряд выборов. Идея, лежащая в основе жадного алгоритма, заключается в том, чтобы каждый выбор был локально оптимальным. В качестве простого примера приведем задачу о выдаче сдачи: чтобы свести к минимуму количество монет, необходимых для выдачи определенной суммы, достаточно каждый раз выбирать монету наибольшего достоинства, не превышающую той суммы, которую осталось выдать.

Можно сформулировать много таких задач, оптимальное решение которых с помощью жадных алгоритмов получается намного быстрее, чем с помощью методов динамического программирования. Однако не всегда просто выяснить, окажется ли эффективным жадный алгоритмы. В главе 16 приводится обзор теории матроида, которая часто оказывается полезной для принятия подобных решений.

Амортизационный анализ — это средство анализа алгоритмов, в которых выполняется последовательность однотипных операций. Вместо того чтобы накладывать границы на время выполнения каждой операции, с помощью амортизационного анализа оценивается длительность работы всей последовательности в целом. Одна из причин эффективности этой идеи заключается в том, что в некоторых последовательностях операций невозможна ситуация, когда время работы всех индивидуальных операций является наихудшим. Зачастую некоторые операции Часть 1У.

Усовершенствованные методы разработки и анализа 385 в таких последовательностях оказываются дорогостояшими в плане времени работы, в то время как многие другие — дешевыми. Заметим, что амортизационный анализ — это не просто средство анализа. Его можно рассматривать и как метод разработки алгоритмов, поскольку разработка и анализ времени работы алгоритмов часто тесно переплетаются. В главе 17 излагаются основы трех способов амортизационного анализа алгоритмов.

ГЛАВА 15 Динамическое программирование Динамическое программирование, как и метод разбиения, позволяет решать задачи, комбинируя решения вспомогательных задач. (Термин "программирование" в данном контексте означает табличный метод, а не составление компьютерного кода.) В главе 2 уже было показано, как в алгоритмах разбиения задача делится на несколько независимых подзадач, каждая из которых решается рекурсивно, после чего из решений вспомогательных задач формируется решение исходной задачи. Динамическое программирование, напротив, находит применение тогда, когда вспомогательные задачи не являются независимыми, т.е.

когда разные вспомогательные задачи используют решения одних и тех же подзадач. В этом смысле алгоритм разбиения, многократно решая задачи одних и тех же типов, выполняет больше действий, чем было бы необходимо. В алгоритме динамического программирования каждая вспомогательная задача решается толью один раз, после чего ответ сохраняется в таблице. Это позволяет избежать одних и тех же повторных вычислений каждый раз, когда встречается данная подзадача. Динамическое программирование, как правило, применяется к задачам оюоимизаиии (орбппхайоп ргоЫешз).

В таких задачах возможно наличие многих решений. Каждому варианту решения можно сопоставить какое-то значение, и нам нужно найти среди них решение с оптимальным (минимальным или максимальным) значением. Назовем такое решение одним из возможных оптимальных решений.

В силу того, что таких решений с оптимальным значением может быть несколько, следует отличать их от единственного оптимального решения. Процесс разработки алгоритмов динамического программирования можно разбить на четыре перечисленных ниже этапа. 1. Описание структуры оптимального решения. Глава 15. Динамическое программирование 387 2. Рекурсивное определение значения, соответствующего оптимальному решению. 3. Вычисление значения, соответствующего оптимальному решению, с помощью метода восходящего анализа. 4.

Составление оптимального решения на основе информации, полученной на предыдущих этапах. Этапы 1 — 3 составляют основу метода динамического программирования. Этап 4 может быть опушен, если требуется узнать только значение, соответствующее оптимальному решению. На четвертом этапе иногда используется дополнительная информация, полученная на третьем этапе, что облегчает процесс конструирования оптимального решения. В последуюпшх разделах метод динамического программирования используется для решения некоторых задач оптимизации. В разделе 15.1 исследуется задача по составлению графика работы двух автосборочных конвейеров.

По завершении каждого этапа сборки автомобиль либо остается на том же конвейере, либо перемещается на другой. В разделе 15.2 исследуется вопрос о том, в каком порядке следует выполнять перемножение нескольких матриц, чтобы свести к минимуму общее количество операций перемножения скаляров. На этих двух примерах в разделе 15.3 обсуждаются две основные характеристики, которыми должны обладать задачи, для которых подходит метод динамического программирования.

Далее, в разделе 15.4 показано, как найти самую длинную общую подпоследовательность двух последовательностей. Наконец, в разделе 15.5 с помощью динамического программирования конструируется дерево бинарного поиска, оптимальное для заданного распределения ключей, по которым ведется поиск.

15.1 Расписание работы конвейера В качестве первого примера динамического программирования рассмотрим решение производственной задачи. Некая автомобильная корпорация производит автомобили на заводе, оснащенном двумя конвейерами (рис. 15.1). На оба конвейера, на каждом из которых предусмотрено по несколько рабочих мест, поступают для сборки автомобильные шасси, после чего на каждом рабочем месте конвейера добавляются все новые детали.

Наконец, собранный автомобиль покидает конвейер. На каждом конвейере имеется и рабочих мест, пронумерованных от 1 до и. Обозначим рабочее место под номером г на 1-м конвейере (где ь' принимает значения 1 или 2) через Я; . На обоих конвейерах на рабочих местах с одинаковыми номерами выполняются один и те же операции. Однако конвейеры создавались в разное время и по разным технологиям, поэтому время выполнения одних и тех же операций на разных конвейерах различается. Обозначим время сборки на рабочем месте Я;у через сч . Как видно из рис. 15.1, шасси поступает на первое Часть еЧ. Усовершенствованные методы разработки и анализа 388 Рабочее место 5,а Рабочее место 5~ „ Рабочее место 5ц Рабочее место 5, „, Рабочее место 5,, Рабочее место5, а сб кон Высок тотоаото аатомобааа Запуск а~асса обо ко Рабочее Рабочее Рабочее место 5т, место 5та место 5тт Рабочее «ссттт 5т ч Рабочее место 5т„м Рабочее место 5т „ Рнс.

15.1. Производственная задача по опрсдслснню оптимального способа сборки рабочее место одного из конвейеров, а затем переходит от одного рабочего места к другому. Постановка шасси на конвейер занимает время еп а снятие готового автомобиля с конвейера — время х;. Обычно поступившее на конвейер шасси проходит все этапы сборки на одном и том же конвейере. Временем перехода от одного рабочего места к другому, если этот переход выполняется в пределах одного конвейера, можно пренебречь. Однако иногда заказчик требует, чтобы автомобиль был собран за кратчайшее время, и такой порядок приходится нарушить.

Для ускорения сборки шасси по-прежнему проходит все п рабочих мест в обычном порядке, однако менеджер может дать указание перебросить частично собранный автомобиль с одного конвейера на другой, причем такая переброска возможна на любом этапе сборки. Время, которое требуется для перемещения шасси с конвейера с на соседний после прохождения рабочего места Ями равно 1ьз, 1 = 1,2,... еп — 1 (поскольку после прохождения и-го рабочего места сборка завершается). Задача заключается в том, чтобы определить, какие рабочие места должны быть выбраны на первом конвейере, а какие — на втором, чтобы минимизировать полное время, затраченное на заводе на сборку одного автомобиля. В примере, проиллюстрированном на рис.

Характеристики

Список файлов книги