Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 267
Текст из файла (страница 267)
Первый такой алгоритм часто приписывается Грэхему (бгаЬаш) [148]. Со времени публикации этой ранней работы были разработаны тысячи приближенных алгоритмов, позволяющих решать самые разнообразные задачи. По этой теме имеется большое количество литературы. Недавно вышедшие книги Осиэлло (Аигбейо) и др. [25], Хохбаума [17Ц и Вазирани (Чахпаш) [343] полностью посвящены приближенным алгоритмам. То же самое можно сказать об обзорах Шмойса (Яппоув) [313] и Клейна (К!еш) и Юнга (Уоппй) [206].
В нескольких других книгах, таких как книги Гарса (багеу) и Джонсона ()оЬпвоп) [128], а также Пападимитриу (Рарагйпп!пои) и Штейглица (8!е!8П!х) [269], также значительное внимание уделяется приближенным алгоритмам. В книге Лоулера (Ьаэн!ег), Ленстры (1.епв!та), Ринноя Кана (Вэппооу Кап) и Шмойса (Яппоув) [224] подробно рассматриваются приближенные алгоритмы, предназначенные для решения задачи о коммивояжере.
В книге Пападимитриу (Рарайш!впору) и Штейглица (8!е!8!Иг) авторство алгоритма АРРкох-Чектех-Соуек приписывается Ф. Гаврилу (К банп!) и М. Яннакакису (М. Уаппа(гак!в). Большое количество усилий было направлено на исследование задачи о вершинном покрытии (в книге Хохбаума (НосЬЬашп) [17Ц перечислены 16 различных приближенных алгоритмов, предназначенных для решения этой задачи), однако значение всех коэффициентов аппроксимации не меньше 2 — о(1).
Алгоритм АРРкох-ТБР-Толк был предложен в статье Розенкранца (Ковеп)сгап!г), Стирнса (Яеагпв) и Льюиса (Ьевс!в) [296]. Кристофидис (СЬпв!обдев) усовершенствовал этот алгоритм и предложил 3!!2-приближенный алгоритм, позволяющий решить задачу о коммивояжере с неравенством треугольника. Арора (Агога) [22] и Митчелл (МйсЬей) [255] показали, что если точки находятся на евклидовой плоскости, то существует схема аппроксимации с полиномиальным временем работы. Теорема 35.3 доказана Сани (БаЬп!) и Гонзалезом (белка!ех) [299].
Анализ жадного эвристического подхода к задаче о покрытии множества построен по аналогии с доказательством более общего результата, опубликованным Глава 35. Приближенные алгарнжллы !393 в статье Чватача (СЬчаЗа1) [67]; представленный здесь основной результат доказан Джонсоном ()оЬпзоп) [189] и Ловасом (1.очазя) [237]. Описание алгоритма Аггкох-Бцвзлт-8пм и его анализ с некоторыми изменениями взяты из статьи Ибарры (1Ьапв) и Кима (Кпп) [186], где приведены приближенные алгоритмы, предназначенные для решения задач о рюкзаке и о сумме подмножества. Задача 35.7 представляет собой комбинаторную версию более общего результата по приближению целочисленной задачи о рюкзаке, полученного Бинстоком (В(епзюс1с) и Мак-Клоски (МсС!оа)гу) [44].
Рандомизированный алгоритм решения задачи о МАХ-3-СХЕ-выполнимости можно найти в неявном виде в работе Джонсона ()оЬпзоп) [189]. Автором алгоритма, предназначенного для решения задачи о взвешенном вершинном покрытии, является Хохбаум (НосЬЬашп) [170]. Раздел 35.4 дает лишь поверхностное представление о тех возможностях, которые открываются благодаря использованию рандомизации и линейного программирования при разработке приближенных алгоритмов. Сочетание этих двух идей привело к появлению метода под названием ирандомизированное округление", в котором задача сначала формулируется как целочисленная задача линейного программирования.
После этого решается ослабленный вариант задачи, а переменные в этом решении интерпретируются как вероятности. Затем эти вероятности используются для решения исходной задачи. Впервые этот метод был предложен Рагаваном (Каййачап) и Томсоном (ТЬошрзоп) [288], после чего он нашел широкое применение. (Для ознакомления с этой темой см. обзорную статью Мотвани (Моплгап!), Наора (Ыаог) и Рагавана (Каййачап) [259].) К другим заслуживающим внимания идеям в этой области, предложенным в последнее время, относятся метод прямой двойственности (рпша! дпа() (см.
обзор Гоманса (Ооетапя) и Вильямсона (%!!Лашзоп) [134]), поиск разреженных разрезов (зрагзе сига) для использования в алгоритмах разбиения [228], а также применение полуопределенного программирования [133]. Как упоминалось в заключительных замечаниях к главе 34, последние достижения в области вероятностно проверяемых доказательств позволяют найти нижние границы аппроксимируемости многих задач, в том числе некоторых из тех, которые рассматриваются в настоящей главе. В дополнение к приведенным здесь ссылкам заметим, что глава из книги Ароры (Агога) и Ланда ((.ппг)) [23] содержит хорошее описание отношения между вероятностно проверяемыми доказательствами и степенью сложности приближенных алгоритмов решения различных задач.
Введение Анализ алгоритмов требует серьезного математического аппарата. Иногда достаточно знаний из простейшего курса высшей математики, но зачастую используемые в данной книге математические концепции и методы могут оказаться новыми для вас. В части 1 вы уже познакомились с асимптотическими обозначениями и решением рекуррентных соотношений; в этой части вы найдете ряд других математических концепций и методов, используемых в ходе анализа алгоритмов. Как упоминалось во введении к части 1, вы могли быть знакомы со многими рассматриваемыми здесь вопросами еше до того, как приступили к чтению данной книги, так что материал, представленный в приложениях, следует рассматривать, в первую очередь, как справочный.
Тем не менее здесь, как и в основных главах, приведены упражнения и задачи, которые помогут вам повысить свою квалификацию в рассматриваемых областях математики. В приложении А рассматриваются методы вычисления и оценки рядов, часто встречаюшихся в процессе анализа тех или иных алгоритмов. Многие из приводимых здесь формул можно найти в различных учебниках по математике, но гораздо удобнее, когда все эти формулы собраны в одном месте. В приложении Б приведены основные определения и обозначения, используемые при работе с множествами, отношениями, функциями, графами и деревьями. В нем вы также найдете некоторые основные свойства этих математических обьектов.
Приложение В начинается с элементарных принципов комбинаторики — перестановок, сочетаний и т.п. Остальной материал приложения посвящен основам теории вероятности. Большинство алгоритмов в этой книге не требуют использования теории вероятности в ходе анализа, так что можете пропустить эту часть приложения. Вы сможете вернуться к нему позже, при желании детально разобраться в вероятностном анализе алгоритмов. В этом случае вы убедитесь, что данное приложение можно рассматривать и как хорошо организованный справочник. Часть и!!!, сттнтоскениа' математические основы !!97 Приложение Г посвящено матрицам, операциям с ними и некоторым основным свойствам матриц. Вероятно, вы уже сталкивались с большей частью представленного здесь материала при прослушивании курса линейной алгебры, но может оказаться очень удобным иметь такой раздел, в который всегда можно заглянуть, чтобы освежить свою память.
Приложение А. Суммы и ряды Если алгоритм содержит итеративную управляющую конструкцию, такую как цикл тгпйе или 1ог, время его работы можно выразить в виде суммы значений времени выполнения отдельных итераций. Например, в разделе 2.2 указывалось, что 1-я итерация алгоритма сортировки вставкой выполняется за время, в худшем случае пропорциональное 1. Суммируя значения времени, затраченного на выполнение отдельных итераций, мы получим сумму, или ряд, Вычисление этой суммы приводит нас к границе для времени работы алгоритма, равной 9(пз) в худшем случае.
Этот пример свидетельствует о важности понимания и умения вычислять суммы и оценивать их границы. В разделе А.1 перечислены некоторые основные формулы, связанные с суммированием, а в разделе А.2 — некоторые полезные методы оценки сумм. Формулы в разделе А.1 приведены без доказательств, однако в разделе А.2 в качестве иллюстрации описываемые здесь методы использованы для доказательства некоторых формул из раздела А.1.
Остальные доказательства можно найти в различных учебниках по математике. А.1. Суммы н ик свойства Для данной последовательности чисел ам аз,..., а„, где и — неотрицательное целое число, конечная сумма аз + аз + .. + а„кратко записывается как и аь а=1 Если и = О, значение суммы считается равным О.
Значение конечного ряда всегда определено и не зависит от порядка слагаемых. Примсяееяие А. Суммы и ряды П99 Для заданной последовательности чисел аг,аг,... бесконечная сумма а1 + аг + кратко записывается как аь, ь=г что рассматривается как 1пп ~~с аь Если данный предел не существует, ряд рпсходпюая (гйтегдез); в противном случае ряд сходится (сопиегйез).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
