Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 247
Текст из файла (страница 247)
в) Предложите псевдокод, реализующий этот жадный алгоритм. Чему равно время работы этого алгорнтма? г) Покажите, что для расписания, которое возвращается жадным алгоритмом, выполняется неравенство 1 Сыы, < — Г рь+ шах рь. т 1Ф<п Обоснуйте вывод, согласно которому этот алгоритм является 2-прнблнженным алгоритмом с полнномнальным временем выполнения. Заключительные замечания Несмотря на то, что методы, которые не обязательно вычисляют точные решення, были известны несколыю тысяч лет назад (напрнмер, методы приближенного вычисления числа я), понятие приближенного алгоритма имеет намного более короткую историю.
Заслуги по формализации концепцнн приближенного алгоритма с полнномнальным временем работы Хохбаум (НосЬЬашп) приписывает Гарею (Оагеу), Грэхему (ОгаЬаш) н Ульману ((Л!шап) [1091, а также Джонсону (1оЬпзоп) [1бб1. Первый такой алгоритм (ему посвящена задача 35-5) часто приписывается Грэхему [1291. Глава 35.
Приближенные алгоритмы 1187 Со времени публикации этой ранней работы были разработаны тысячи приближенных алгоритмов, позволяющих решать самые разнообразные задачи. По этой теме имеется большое юличество литературы. Недавно вышедшие книги Осиэлло (Аияе11о) н др.
[25), Хохбаума [149) и Вазирани (чахпаш) [305] полностью посвящены приближенным алгоритмам. Это же можно сказать об обзорах Шмойса (БЬшоуз) [277) и Клейна (К!еш) и Юнга (Уоипй) [18Ц. В нескольких других книгах, таких как книги Гарея и Джонсона [110], а также Пападимитриу (Рарайш1птои) и Штейглица (Бге!81йк) [237], также значительное внимание уделяется приближенным алгоритмам. В книге Лоулера (Ьаж!ег), Ленстры (Ьепзпа), Ринноя Кана (В!ппооу Кап) и Шмойса [197] подробно рассматриваются приближенные алгоритмы, предназначенные для задачи о юммивояжере. В книге Пападимитриу н Штейглица авторство алгоритма АРРКОХ ЧЕКТЕХ Сочен приписывается Ф.
Гаврилу (Р. Оачп1) и М. Яннакакису (М. Уаппайа!аз). Большое количество усилий было направлено на исследование задачи о вершинном покрытии (в книге Хохбаума [149] приведено 16 различных приближенных алгоритмов, предназначенных для решения этой задачи), однаю значение всех коэффициентов аппроксимации не меньше 2 — о (1). Алгоритм АРРкох ТБР Толк был предложен в статье Розенкранца (Возеп1сгапгх), Стирнса (Б1еатпз) и Льюиса (Ьетч!з) [26 Ц.
Кристофидис (СЬпзгоЫез) усовершенствовал этот алгоритм и предложил 3/2-приближенный алгоритм, позволяющий решить задачу о коммивояжере с неравенством треугольника. Арора (Агота) [2Ц и Митчелл (МйсЬе!1) [223) показали, что если точки находятся на евклидовой плосюсти, то существует схема аппроксимации с полиномиальным временем работы. Теорема 35.3 доказана Сани (БаЬп!) и Гонзалезом (Оопга1ег) [264]. Анализ жадного эвристического подхода к задаче о покрытии множества построен по аналогии с доказательством более общего результата, опубликованном в статье Чватала (СЬчага!) [6 Ц; представленный здесь основной результат доказан Джонсоном [166] и Ловасом (Ьочазх) [206). Описание алгоритма АРРкох Бивзет Бом и его анализ с неюторыми изменениями взяты из статьи Ибарры (1Ьапа) и Кима (Кпп) [164], где приведены приближенные алгоритмы, предназначенные для решения задач о рюкзаке и о сумме подмножества.
Рандомизированный алгоритм решения задачи о МАХ-3-СЬ!Р выполнимости можно найти в неявном виде в работе Джонсона [166]. Автором алгоритма, предназначенного для решения задачи о взвешенном вершинном покрытии, является Хохбаум [148).
Раздел 35.4 дает лишь поверхностное представление о тех возможностях, которые открываются благодаря использованию рандомизации и линейного программирования при разработке приближенных алгоритмов. Сочетание этих двух идей привело к появлению метода под названием "рандомизированное округление", в котором задача сначала формулируется как целочисленная задача линейного программирования. После этого решается ослабленный вариант задачи, 1188 Часть ЧП. Избранные темы а переменные в этом решении интерпретируются как вероятности. Затем эти вероятности используются для решения исходной задачи.
Впервые этот метод был предложен Рагаваном (Ка8Ьачап) и Томсоном (ТЬошрзоп) [2551, после чего он нашел широкое применение. (Для ознакомления с этой темой см. обзорную статью Мотвани (Монаган(), Наора (Хаог) и Рагавана [2271.) К другим заслуживающим внимания идеям в этой области, предложенным в последнее время, относится метод прямой двойственности (рпша1 биа1) (см. обзор [1161), поиск разреженных разрезов (зратзе сщз) для использования в алгоритмах разбиения [1991, а также применение полуопределенного программирования [115]. Как упоминалось в заключительных замечаниях к главе 34, последние достижения в области вероятностно проверяемых доказательств позволяют найти нижние границы аппроксимируемости многих задач, в том числе некоторых из тех, которые рассматриваются в настоящей главе.
В дополнение к приведенным здесь ссылкам заметим, что глава из книги Ароры и Ланда (Ьши1) [221 содержит хорошее описание отношения между вероятностно проверяемыми доказательствами и степенью сложности приближенных алгоритмов решения различных задач. Введение Анализ алгоритмов требует использования серьезного математического аппарата. Иногда достаточно знаний из простейшего курса высшей математики, но зачастую используемые в данной книге математические концепции и методы могут оказаться новыми для вас. В части 1 мы уже познакомились с асимптотическимн обозначениями и решением рекуррентных соотношений; в этой части вы найдете ряд других математических концепций и методов, используемых при анализе алгоритмов. Как упоминалось во введении к части 1, вы могли быть знакомы со многими рассматриваемыми здесь вопросами еще до того, как приступили к чтению данной книги, так что материал, поданный в приложениях, носит в первую очередь справочный характер.
Тем не менее, здесь, как и в обычных главах, приведены упражнения и задачи, которые помогуг вам повысить свою квалификацию в рассматриваемых областях математики. В приложении А рассматриваются методы вычисления и оценки рядов, часто встречающихся при анализе тех или иных алгоритмов. Многие из приводимых здесь формул можно найти в различных учебниках по математике, но гораздо удобнее, когда все эти формулы собраны в одном месте. В приложении Б приведены основные определения и обозначения, используемые при работе с множествами, отношениями, функциями, графами и деревьями.
В этом приложении вы также найдете некоторые основные свойства этих математических объектов. Приложение В начинается с элементарных принципов комбинаторики — перестановок, сочетаний и т.п. Остальной материал приложения посвящен основам теории вероятности. Большинство алгоритмов в этой книге не требуют использования теории вероятности прн анализе, так что вы можете пропустить эту часть приложения. Вы сможете вернуться к нему позже, при желании детально разобраться с вероятностным анализом алгоритмов. В этом случае вы убедитесь, что данное приложение можно рассматривать и как хорошо организованный справочник. Часть ЧИ1. Приложения: математические основы 1192 А.1 Суммы и их свойства Для данной последовательности чисел аы аз,...
конечная сумма а1 + аз + + . + а„, где п — неотрицательное целое число, кратко записывается как ~ аь. а=1 Если и = О, значение суммы считается равным О. Значение конечного ряда всеща определено и не зависит от порядка слагаемых. Для данной последовательности чисел аы аз,... бесконечная сумма а1+ аз+ +... кратко записывается следующим образом: ,'~ аь, я=г что рассматривается как Ыпз ~ аь.
а=1 Если данный предел не существует„ряд расходщася (йтегдез); в противном случае ряд сходилгся (соптегдез). Члены сходящегося ряда не могут быть суммированы в произвольном порядке. Однако можно переставлять члены абсолютно сходящегося ряда, те. ряда ~,ь аь, для которого сходится также ряд ,'> ь 1 ~аь~. Линейность Для любого действительного числа с и любых конечных последовательностей ам аз,..., а„и Ьы Ьз,..., Ь„ ь и ть ~~> (саь+ Ьь) = с~~> аь+ ~~~ Ьь. /с=1 а=1 а=1 Свойство линейности справедливо также для бесконечных сходящихся рядов. Это свойство может использоваться при работе с суммами, в которые входят асимптотические обозначения. Например, и и , 'оу®)=е '„«,'у(~) а=1 а=1 В этом уравнении 9-обозначение в левой части применяется к переменной Й, а в правой — к и.
Аналогичные действия применимы и к бесконечным сходящимся рядам. Приложение А. Ряды 1193 Арифметическая прогрессия Сумма а=1+2+ ° ° ° +и я=1 называется арифметической лрогресскей и равна к = — п(п+ 1) = 1 а=1 =~( з) (А. 1) (А.2) Суммы квадратов и кубов Для сумм квадратов и кубов справедливы следующие формулы: п(п+ 1) (2п+ 1) б я=о ~~~йз п (п+ 1) а=о 4 (А.З) (А.4) Геометрическая прогрессия Для действительного х ф 1 сумма ,'~ х =1+х+х + +х" в=о называется геометрической прогрессией и равна я=о (А.5) 1 я=о (А.б) В случае бесконечного ряда и ~х~ < 1 получается бесконечно убывающая геомет- рическая прогрессия„сумма которой равна Часть Ч!!!.
Приложения: математические основы 1194 Гармонический ряд Для натурального и, и-е гармоническое число представляет собой 1 1 1,~". 1 Н„= 1+ — + — +. + — = ~ — = )пп+0(1). 2 3 и ~-,)с (А.7) (Мы докажем зто соотношение в разделе А.2.) Интегрирование и дифференцирование рядов Новые формулы могут быть получены путем интегрирования или дифференцирования приведенных выше формул. Например, дифференцируя обе части уравнения суммы бесконечной геометрической прогрессии (А.б) и умножая на х, мы получим для !х! < 1 lсхь = (1 — х) (А.8) Суммы разностей Для любой последовательности ао, аы..., а„справедливо соотношение ,') (аь — аь з) = а„— ао, 1-1 (А.9) ь-1 ,') (аь — аь+1) = ао — а„. г=о В качестве примера такого ряда рассмотрим сумму ь-1 1 Ей(+ ) Поскольку каждый ее член можно записать как 1 1 1 !с (!с+ 1) !с й+ 1' мы получаем поскольку каждый из членов а1, аз,..., а„1 прибавляется и вычитается ровно один раз.
Такие ряды именуют телескопическими (!е!езсорез). Аналогично, Приложение А. Ряды 1195 Произведения Конечное произведение а|аз... а„может быть кратко записано следующим образом: и П оь. Если п = О, значение произведения считается равным 1. Мы можем преобразовать формулу с произведением в формулу с суммой при помощи тождества я п 1к П аь = ~ 15аь. а=1 ью1 Упражнения А.1-1. Найдите простое выражение для ~а~, (2й — 1). * А.1-2. Покажите, используя формулу для гармонического ряда, что 1/(2/с — 1) = 1п (~Я + 0 (1). А.1-3. Покажите, что для О < )х) < 1 справедливо соотношение ~"~ с Йзх" = = х (1 + х)/(1 — х) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
