Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 242
Текст из файла (страница 242)
Упражнения 35.2-1. Предположим, что полный неориентированный граф С = (КЕ), содержащий не менее трех вершин, характеризуется функцией стоимости с, удовлетворяющей неравенству треугольника. Докажите, что для всех и, с е У выполняется неравенство с (и, о) > О. 35.2-2. Покажите, как в течение полиномиального времени один экземпляр задачи о юммивояжере можно преобразовать в другой экземпляр, функция стоимости которого удовлетворяет неравенству треугольника.
Оба экземпляра должны содержать одно и то же множество оптимальных туров. Объясните, почему такое полиномиально-временное преобразование не противоречит теореме 35.3, предполагая, что Р ~ МР. 35.2-3. Рассмотрим описанный ниже эвристический метод ближайшей точки (с1озезт-ро)п1 леипзцс), позволяющий создавать приближенные туры в задаче о коммивояжере, функция стоимости которой удовлетворяет неравенству треугольника.
Начнем построение с тривиального цикла, состоящего из одной произвольным образом выбранной вершины. На каждом этапе идентифицируется вершина и, не принадлежащая циклу, причем такая, расстояние от которой до цикла является минимальным. Предположим, что ближе всех к вершине и в цикле расположена вершина о. Цикл расширяется за счет включения в него вершины и сразу после вершины о. Описанные действия повторяются до тех пор, пока в цикл Часть Ч!1. Избранные темы 1164 не будут включены все вершины. Докажите, что этот эвристический метод возвращает тур, полная стоимость которого не более чем в два раза превышает полную стоимость оптимального тура. 35.2-4. Задача о коммивояжере с устранением узких мест (Ьоп!епес1с ггаче1- 11пя-за1езшап ргоЫеш) — это задача поиска такого гамильтонового цикла, для которого минимизируется стоимость самого дорогостоящего входящего в этот цикл ребра.
Предполагая, что функция стоимости удовлетворяет неравенству треугольника, покажите, что для этой задачи существует приближенный алгоритм с полиномиальным временем работы, коэффициент аппроксимации которого равен 3. (Указание: воспользовавшись рекурсией, покажите, что все узлы остовного дерева с узкими местами можно обойти ровно по одному разу, взяв полный обход дерева с пропусками узлов, если ограничить пропуски таким образом, чтобы не пропускать более двух последовательных промежуточных узлов (см.
упражнение 23.-3). Покажите, что стоимость самого дорогостоящего ребра в остовном дереве с узкими местами не превышает стоимости самого дорогостоящего ребра в гамильтоновом цикле с узкими местами.) 35.2-5. Предположим, что вершины экземпляра задачи о коммивояжере расположены на плоскости, и что стоимость с1и, и) равна евклидовому расстоянию между точками и и ю.
Покажите, что в оптимальном туре никогда не будет самопересечений. 35.3 Задача о покрытии множества Задача о покрытии множества — это задача оптимизации, моделируюшая многие задачи выбора ресурсов (гезопгсе-зе1есгюп ргоЫешз). Соответствующая ей задача принятия решения является обобщением ХР-полной задачи о вершинном покрытии, следовательно, она — ХР-сложная. Однако приближенный алгоритм, разработанный для задачи о вершинном покрытии, здесь неприменим, поэтому следует попытаться поискать другие подходы.
Исследуем простой эвристический жадный метод, коэффициент аппроксимации которого выражается логарифмической функцией. Другими словами, по мере того как растет размер экземпляра задачи, размер приближенного решения тоже может возрастать относительно размера оптимального решения. Однако, так как логарифмическая функция возрастает достаточно медленно, этот приближенный алгоритм может тем не менее давать полезные результаты.
Экземпляр (Х, У) задачи о накрытии множества 1зе~-сечет)га ргоЫеш) состоит из конечного множества Х и такого семейства г подмножеств множества Х, что каждый элемент множества Х принадлежит хотя бы одному подмножеству Глава 35. Приближенные алгоритмы 1165 Рис. 35.3. Экземпляр (Х,У) задачи о покрытии множества, в котором множество Х состоит из 12 черных точек, а У = (Яиоз,Яз,Яз,оз оа) из семейства У: Говорят, что подмножество Я Е У' локрываелз (сочегз) содержащиеся в нем элементы. Задача состоит в том, чтобы найти подмножество С С У' минимального размера, члены которого покрывают все множество Х: (35.8) Бес Говорят, что любое семейство С, удовлетворяющее уравнению (35.8), локрыааелз (сочегз) множество Х. Задача о покрытии множества иллюстрируется на рис. 35.3.
Размер семейства С определяется как количество содержащихся в нем подмножеств, а не как суммарное количество отдельных элементов в этих множествах. В примере, проиллюстрированном на рис. 35.3, размер минимального покрытия множества равен 3. Жадный алгоритм возвращает вершинное покрытие, размер которого равен 4, выбирая множества Ям Я4, Яз и Яз в том порядке, в котором они здесь перечислены. Покрытие множества минимального размера имеет вид С ты Я4 Я Задача о покрытии множества является абстракцией многих часто возникающих комбинаторных задач.
В качестве простого примера предположим, что множество Х представляет набор знаний, необходимых для решения задачи, над юторой работает определенный коллектив сотрудников. Нужно сформировать комитет, состоящий из минимально возможного юличества сотрудников, причем такой, что при необходимости любой информации из множества Х, оказывается, что в комитете есть сотрудник, обладающий этим знанием. Если преобразовать эту Часть ЧП. Избранные тема 1166 задачу в задачу принятия решений, то в ней будет спрашиваться„существует ля покрытие, размер которого не превышает Й, где й — дополнительный параметр, определенный в экземпляре задачи. Как предлагается показать в задаче 35.3-2, версия этой задачи в форме задачи принятия решений является Хр-полной.
Жадный приближенный алгоритм Жадный метод работает путем выбора на каждом этапе множества о, покрывающего максимальное количество элементов, оставшихся непокрытыми. ОЕЕЕШ' БЕТ СОЧЕЕ(Х,У) 1 У -Х г с 9 3 тгййеУФ6 4 йо выбирается подмножество Я Е У, максимизирующее величину (Я П У( 5 У -У вЂ” Я 6 С -Сы(Я) 7 гегпгп С Опишем принцип действия алгоритма. На каждом этапе его работы множество У содержит оставшиеся непокрытыми элементы.
Множество С содержит покрытие, которое конструируется. Строка 4 — это этап принятия решения в жадном методе. Выбирается подмножество Я, покрывающее максимально возможное количество еще непокрытых элементов (с произвольным разрывом связей). После выбора подмножества Я его элементы удаляются из множества У, а подмножество Я помещается в семейство С. Когда алгоритм завершает свою работу, множество С будет содержать подсемейство семейства У', покрывающее множество Х.
В примере, проиллюстрированном на рис. 35.3, алгоритм Океепу Бег Сочее добавляет в семейство С множества Яы Я4, Яз и Яз в порядке перечисления. Алгоритм Оееепч Вет Сочен легко реализовать таким образом, чтобы время его работы выражалось полиномиальной функцией от величин )Х! и (У(. Поскольку количество итераций цикла в строках 3-6 ограничено сверху величиной ппп((Х(, )У)), а тело цикла можно реализовать таким образом, чтобы его выполнение завершалось в течение времени О ОХ) )У')), существует реализация, завершающая свою работу в течение времени О ОХ( (У'! ппп (~Х), ~У'!)).
В упражнении 35.3-3 предлагается разработать алгоритм с линейным временем работы. Анализ Теперь покажем, что жадный алгоритм возвращает покрытие множества, не слишком сильно превышающее оптимальное покрытие. Для удобства в этой главе Глава 35. Приближенные алгоритмы 1167 11-е по порядку гармоническое число Н4 = ~ 1 1/г (см. раздел А.1) будет обозна- 4 чаться как Н (г().
В качестве граничного условия введем определение Н (0) = О. Теорема 35.4. Алгоритм Окши' Знт Сотни — это р(п)-приближенный алго- ритм с полиномиальным временем работы, где р (г1) = Н (шах1~5): о Е .г)). Доказалгельство. Уже было показано, что алгоритм Окннй' Бит Сочна выполняется в течение полиномиального времени.
Чтобы показать, что Оквнпу Внт Сотен — это р (г1)-приближенный алгоритм, присвоим каждому из выбранных алгоритмом множеств стоимость 1, распределим эту стоимость по всем элементам, покрытым за первый раз, а потом с помощью этих стоимостей получим нужное соотношение между размером оптимального покрытия множества С' и размером покрытия С, возвращенного алгоритмом.
Обозначим через Яг г'-е подмножество, выбранное алгоритмом Окнюу йнт Сочна; добавление подмножества ог в множество С приводит к увеличению стоимости на 1. Равномерно распределим стоимость, соответствующую выбору подмножества 5;, между элементами, которые впервые покрываются этим подмножеством. Обозначим через с стоимость, выделенную элементу х 6 Х. Стоимость выделяется каждому элементу только один раз, когда этот элемент покрывается впервые. Если элемент х первый раз покрывается подмножеством о;, то выполняется равенство 1 ~Я' (Я1052и'''113' — 1)Г На каждом шаге алгоритма присваивается единичная стоимость, поэтому (С(= ~~1 с .
аЕХ Стоимость, присвоенная оптимальному покрытию, равна сх ЯЕС' аЕЯ и поскольку каждый элемент хеХ принадлежит хотя бы одному множеству о ЕС', справедливо соотношение ЯеС' жеЯ АХ Объединяя два приведенных выше неравенства, получаем соотношение )С) < ~~1 ~~1 с,. (35.9) ЯЕС кЕЯ Часть ЧН. Избранные темы 11б8 Оставшаяся часть доказательства основана на приведенном ниже ключевом неравенстве, которое скоро будет доказано. Для любого множества Я, принадлежащего семейству У, выполняется неравенство ,'~ с, < НЦЯ().
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
