Главная » Просмотр файлов » Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013)

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

Файл №1162189 Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013)) 87 страницаТ. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189) страница 872019-09-19СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Первоначальный вызов процедуры Рщнт-ОРт1МАе-РАкемз(в,1, п) выводит оптимальную расстановку сюбок в последовательности (А1, Аз,..., А„). Рк!мт-ОРт!мА1.-РАкехз(в,1, !) В!==1 2 рппг "А"; 3 е1зе рпп1 "('* 4 РК1НТ-ОРТ1МАь-РАКЕНЯ(в, г, в[!,5]) 5 РК!ХТ-ОРТ!МАЕ-РАКЕНЯ(в, в[1,5] + 1, 1) 6 рппг ")" В примере, проиллюстрированном на рис. 15.5, вызов процедуры РкпчтОрт!МА~.-РАкенз(в, 1,6) дает строку ((А1(АзАз))((А4Аь)Ае)). Упражнения 15.2.1 Найдите оптимальную расстановку скобок в произведении последовательности матриц, размерности которых равны (5, 10, 3, 12, 5, 50, 6). 15.2.2 Разработайте рекурсивный алгоритм млтк1х-снА1н-мтл.т1Реу(А, в,1,5), в котором оптимальным образом вычисляется произведение заданной последовательности матриц (А1, Аз,..., А„).

На вход этого алгоритма, кроме того, поступают индексы 1 и 1, а также таблица в, вычисленная с помощью процедуры МАтк1хСнА1м-Окпек. (Начальный вызов этой процедуры выглядит следующим образом; МАтк!х-СНА!н-М~л.т1Р1л'(А, в, 1, п).) 15.2З Покажите с помощью метода подстановок, что решением рекуррентного соотношения (15.6) является П(2"). 15.2.4 Опишите граф подзадач для перемножения цепочки матриц для входной цепочки длиной и. Сколью вершин в этом графе? Сюлью в нем ребер, и что они собой представляют? 15.2.5 Пусть 11(1,5) — количество обращений к элементу матрицы го[1,5], которые выполняются в ходе вычисления других элементов этой матрицы в процедуре МАТК!х-СнА1м-Окпек.

Покажите, что полное количество обращений ко всем 4з'з Часть |И усовершенстеованные методы разработки и анази т элементам равно (Укаэаниез для решения может оказаться полезным уравнение 1А.З).) 15.2. б Покажите, что в полной расстановке скобок в и-элементном выражении используется ровно и — 1 пар скобок. 15.3.

Элементы динамического программирования Несмотря на рассмотренные в предыдущем разделе два примера, в которых применялся метод динамического программирования, возможно, вам все еще не совсем понятно, когда применим этот метод. В каких случаях задачу можно решать с помощью динамического программирования? В данном разделе рассматриваются два ключевых ингредиента, которые должны быть присущи задаче оптимизации, чтобы к ней можно было применить метод динамического программирования: наличие оптимальной подструктуры и перекрывающихся подзадач. Мы также более полно рассмотрим метод запоминания (шешо1га11оп) и изучим, каким образом он позволяет воспользоваться преимуществами перекрывающихся подзадач при нисходящем рекурсивном подходе.

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

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

В разделе 15.1 было установлено, что оптимальное разрезание стержня длиной и 1если разрезание вообще имеет место) включает оптимальные разрезания частей, появившихся в результате первого разреза. В разделе 15.2 было продемонстрировано, что в оптимальную расстановку скобок, в результате которой последовательность матриц А,А,11 А разбивается на подпоследовательности между матрицами Аь и А1, „1, входят оптималь- Глава 15.

Динамическое нрограммирование иые решения задач о расстановке скобок в подпоследовательностях А,Аиь5 . Ан я А~~-1 Аьв.г . Аэ. Можно видеть, что поиск оптимальной подструктуры происходит по общему образцу. 1. На этапе 1 следует показать, что в процессе решения задачи приходится делать выбор. В рассмотренных примерах это был выбор начального разреза стержня или выбор индекса, при котором разбивается последовательность матриц.

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

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

Характеризуя пространство подзадач, постарайтесь придерживаться такого практического правила: попытайтесь сделать так, чтобы это пространство было как можно проще, а затем расширьте его до необходимых пределов. Например, пространство в подзадачах„возникающих в задаче о разрезании стержня, было образовано задачами оптимального разрезания стержня длиной в для каждого размера 1. Это подпространство оказалось вполне подходящим, и не возникло необходимости его расширять. Теперь предположим, что в задаче о перемножении цепочки матриц предпринимается попытка ограничить пространство подзадач произведениями вида А~ Аз .

А . Как и ранее, оптимальная расстановка скобок должна разбивать произведение междУ матРицами Ан и Аьн.~ Лла некотоРого индекса 1 ( й < 51 Если lс не всегда равно 5 — 1, мы обнаружим, что возникают подзадачи вида АзАэ . Аь и Анв.лАв+з А и что последняя подзадача не является подзадачей вида АзАз .. А .. В этой задаче необходима возможность изменения обоих концов последовательности, те. чтобы в подзадаче А,А, кв А могли меняться оба индекса — и в, и 51 Оптимальная подструктура изменяется в области определения задачи в двух аспектах.

!. Количество подзадач, которые используются при оптимальном решении исходной задачи. 4!4 Часть |У. 'зсовершенствованные методы разработки и аназшо 2. Количество выборов, возникающих при определении того, какая подзадача (подзадачи) используется в оптимальном решении.

В оптимальном решении задачи о разрезании стержня длиной п используется только одна подзадача размером п — з, но для поиска оптимального решения необходимо рассмотрение и вариантов значения з'. Перемножение подцепочкн матриц АеА;ьз Аз служит примером с двумя подзадачами и з — з вариантами выбора. Если задана матрица Аы у которой происходит разбиение произведения, то возникают две подзадачи — расстановка скобок в подпоследовательностях А,Аз~з Аь и Аь~1Аь >з А, причем для каждой из них необходимо найти оптимальное решение.

Как только оптимальные решения подзадач найдены, выбирается один нз з — з вариантов индекса к. Если говорить неформально, время работы алгоритма динамического программирования зависит от произведения двух множителей: общего количества подзадач и количества вариантов выбора, возникающих в каждой подзадаче. При разрезании стержня всего у нас возникало ез(п) подзадач и не более и вариантов выбора, что дает время работы 0(пз).

При перемножении матриц всего возникало кр(пз) подзадач, и в каждой из них — не более и — 1 вариантов выбора, поэтому время работы в этом случае равно 0(ззз) (на самом деле — 9(ззз) согласно упр. 15.2.5). Обычно граф подзадач представляет собой альтернативный путь выполнения этого анализа. Каждая вершина соответствует подзадаче, а варианты выбора для каждой подзадачи представлены ребрами, входящими в соответствующую вершину. Вспомним, что в задаче о разрезании стержня граф имел п вершин и не более и ребер на одну вершину, что дает время работы О(тР). Если изобразить граф подзадач для перемножения цепочки матриц, то он будет иметь 9(пз) вершин, а каждая вершина — степень не выше и — 1, что всего дает О(п ) вершин и ребер.

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

Например, в задаче о разрезании стержня мы сначала решали подзадачи оптимальных способов разрезания стержней длиной з для з = О, 1,..., зз — 1, а затем определяли, какая подзадача дает оптимальное решение для стержня длиной о„используя уравнение (15.2). Стоимость, которая относится к самому выбору, представляет собой член р, в уравнении (15.2).

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

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

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6552
Авторов
на СтудИзбе
299
Средний доход
с одного платного файла
Обучение Подробнее