Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 96
Текст из файла (страница 96)
б. Обобщите сформулированный в и. (а) ответ так, чтобы возвращаемый путь (если он существует) был наиболее вероятным из всех путей, начинающихся в вершине ио и имеющих метку в. Проанализируйте время работы этого алгоритма. 444 Часть 18 усовертенствованные методы разработки и анализа 15.8. Масштабирование изображения У нас имеется цветное изображение, состоящее из зп х и-массива А[1 .. т, 1 .. п] пикселей, где каждый пиксель определяется тройкой интенсивностей красного, зеленого и синего цветов (КкзВ). Предположим, что мы хотим немного сжать это изображение, а именно — удалить по одному пикселю из каждой из т строк, чтобы изображение стало на один пиксель уже.
Во избежание визуальных искажений мы требуем, чтобы пиксели, удаляемые в смежных строках, находились в одном и том же или в смежных столбцах; удаленные пиксели формируют "шов" от верхней до нижней строки, в котором последовательные пиксели шва смежны по вертикали или диагонали. а. Покажите, что количество таких возможных швов растет как минимум экспоненциально с ростом пз, в предположении и > 1. б. Предположим теперь, что для каждого пикселя А[г, з] мы вычисляем действительную меру искажений з1[г, в], указывающую, насколько важен тот или иной пнксель А[в, з] в плане удаления, Интуитивно понятно, что чем меньше эта мера для данного пикселя, тем больше он похож на соседние с ним.
Затем предположим, что мы определяем меру искажений шва как сумму мер искажений составляющих его пикселей. Разработайте алгоритм поиска шва с наименьшей мерой искажений. Насколько эффективен ваш алгоритм? 15.9. Разбиение строки Некоторые языки, ориентированные на работу со строками, позволяют программисту разбивать строки на две части. Поскольку эта операция копирует строки, ее стоимость составляет и единиц времени для разбиения строки из и символов на две части. Предположим, что программист хочет разбить строку на несколько частей, Порядок разбиения может нанять на требуемое для него время.
Предположим, например, что программист желает разбить 20-символьную строку после символов с номерами 2, 8 и 10 (используется нумерация в возрастающем порядке слева направо, начиная с 1). Если разбиения выполняются слева направо, то первое отбит 20 единиц времени, второе — 18 (строка от символа 3 до символа 20 разбивается после символа 8), а третье — 12 единиц, т.е. общая стоимость равна 80. Если же разбиения выполняются справа налево, то их стоимости соответственно равны 20, 10 и 8 единиц времени„так что общая стоимость равна 38 единиц времени. При еше одном порядке можно сначала разбить строку после символа 8 (стоимость 20), а затем разбить полученные части после символа 2 (стоимость 8) и символа 10 (стоимость 12) с общей стоимостью разбиения, равной 40. Разработайте алгоритм, который для данных номеров символов, после которых выполняется разбиение, определяет последовательность разбиений с минимальной общей стоимостью.
Более формализованно — для заданной строки Я длиной и и массива Ц1., т] с точками разбиений вычислить наименьшую стои- 445 Гаага 15. Дннамнчееное нрограммнроаанне мость последовательности разбиений, а также саму последовательность, при ко- торой достигается зта стоимость. 15.1б. Планирование стратегии капиталовложений Ваши знания алгоритмов помогли вам получить потрясающую работу в компании аКрупноТвердьа с единовременным пособием в 10000 долларов. Вы решили вложить эти деньги так, чтобы получить за 1О лет как можно больший доход, и обратились для этого в компанию аМЖ инвест", которая предлагает следующие правила. Компания предлагает вам и различных вариантов капиталовложений, пронумерованных от 1 до п.
В год 5' капиталовложение 1 обеспечивает доход т, . Другими словами, если вы вложите е) долларов в 1 в год 5, то в конце года 5 будете иметь е)г, долларов. Компания гарантирует, что в течение 10 лет ее президент не сбежит, прихватив кассу, и она будет гарантированно выплачивать ваш доход.
Принимать решения о том, куда вложить деньги, вы можете один раз в год. В конце каждого года вы можете либо оставить все деньги там же, где они были в предыдущем году, либо перераспределить их между другими вложениями. Если вы не трогаете свои деньги по окончании года, то платите сбор 11 долларов; если переносите их — то платите сбор 1з > 50 а.
Как указано, вы можете вкладывать деньги в несколько предприятий ежегодно. Докажите, что существует оптимальная стратегия, и заключается она в том, чтобы каждый год вкладывать все деньги в одно предприятие. ~Напомним, что оптимальная стратегия должна максимизировать количество денег по прошествии 10 лет и не рассматривает никакие иные цели, такие, как, например, минимизация рисков.) б. Докажите, что задача планирования оптимальной стратегии капиталовложений демонстрирует оптимальную подструктуру. а Разработайте алгоритм выработки оптимальной стратегии. Каково время работы вашего алгоритма? г.
Предположим, что аМЖ инвест" добавляет ограничение, заключающееся в том, что в одно предприятие не может быть вложено более 15000 долларов. Покажите, что при этом ограничении задача максимизации прибыли по истечении 10 лет не обладает оптимальной подструктурой. 15.11. Разработка производственного плана Компания аЭх, прокачу" изготовляет сани. Естественно, что спрос на эту продукцию колеблется от месяца к месяцу, так что компании требуется разработать стратегию производства с учетом колеблющегося, но предсказуемого спроса. Компании нужен план на следующие п месяцев. Для каждого месяца 1 известен спрос до т.е. количество саней, которые будут проданы.
Пусть Р = '),". 1 е)е— общий спрос саней на все и месяцев. Постоянный штат работников позволяет производить до гп саней в месяц. Если требуется произвести большее количество саней„можно нанять временных работников, оплата которых составляет с 44б Части ! и Зссовершенствованные методы разработки и аназиза долларов за сани.
Кроме того, если в конце месяца остаются нераспроданные сани, приходится платить за их хранение. Стоимость хранения з саней представляет собой функцию Ь(3) для з = 1,2,...,Р, где Ь(Я > О для 1 < 3 < Р и ЬО) < Ь(з + 1) для 1 < 3 < Р— 1. Разработайте алгоритм для расчета производственною плана компании, минимизирующего затраты при выполнении всех ограничений. Время работы алгоритма должно полиномиально зависеть от и и Р, Заключительные замечания Р.
Беллман (К. Ве1!шап) приступил к систематическому изучению динамического программирования в 1955 году. Как в названии идинамическое программирование", так и в термине "линейное программирование" слово "программированием относится к методу табличного решения. Методы оптимизации, включающие в себя элементы динамического программирования, были известны н раньше, однако именно Беллман дал строгое математическое обоснование этой области [36). Галил (Оарй) и Парк (Раг1с) [124) классифицировали алгоритмы динамического программирования в соответствии с размером таблиц и количеством записей, от которых зависит каждый элемент таблицы. Они называют алгоритм динамического программирования 1Р/еР, если размер его таблицы равен 0(пс), а каждый ее элемент зависит от 0(пе) других элементов.
Например, алгоритм перемножения цепочки матриц из раздела 15.2 является алгоритмом 2Р/1Р, а алгоритм поиска наидлиннейшей подпоследовательности из раздела 15.4 — алгоритмом 2Р/ОР. Ху (Нц) и Шинг (8[йп8) [181, 182) разработали алгоритм, позволяющий решить задачу о перемножении матриц в течение времени 0(п 18 и). По-видимому, алгоритм решения задачи о наидлиннейшей общей подпоследовательности, время работы которого равно 0(тп), — плод "народного творчества".
Кнут (Кпц1Ь) [69] поставил вопрос о том, существует ли алгоритм решения этой задачи, время работы которого возрастало бы медленнее, чем квадрат размера. Масек (Мазе1с) и Патерсон (Ра1егзоп) [242) ответили на этот вопрос утвердительно, разработав алгоритм, время работы которого равно 0(гоп/18п), где и < т, а последовательности составлены нз элементов множества ограниченного размера. Шимански (БкппапзЫ) [324) показал, что в частном случае, когда ни один элемент не появляется во входной последовательности более одного раза, эту задачу можно решить за время О((п + гп) 18(п + т)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
