Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 262
Текст из файла (страница 262)
Исследуем простой эвристический жадный метод, коэффициент аппроксимации которого выражается логарифмической функцией. Другими словами, по мере того как растет размер экземпляра задачи, размер приближенного решения также может возрастать относительно размера оптимального решения. Однако, так как логарифмическая функция возрастает достаточно медленно, этот приближенный алгоритм может давать полезные результаты. Экземпляр (Х, У) задачи о накрытии множества (зе!-сочеппй ргойеш) состоит из конечного множества Х и такого семейства У подмножеств множества Х, что каждый элемент множества Х принадлежит хотя бы одному подмножеству Часть И»' Избранные темы Рис.
3КЗ. Эюемпляр (Х, У') задачи о покрытии множества, где Х состоит из 12 черных точек, а У' = (Яы Яз, Яз, Я», Яз, Яе ). Минимальным являетса покрытие С = (Яз, Я», Яз), размер которого равен 3. Жадный алгоритм дает покрытие размером 4, выбирая либо множества Яы б», оз и Яз, либо множества Я», Я», Яз и Яа в указанном порядке. из семейства У': Х= ДЯ. Говорят, что подмножество Я Е У покрывание (сокегз) содержащиеся в нем элементы. Задача состоит в том, чтобы найти подмножество С С .Т минимального размера, члены которого покрывают все множество Х: (35.8) Вес Говорят, что любое семейство С, удовлетворяющее уравнению (35.8), локрынаенз (сочегв) множество Х.
Задача о покрытии множества иллюстрируется на рис. 35.3. Размер семейства С определяется как количество содержащихся в нем подмножеств, а не как суммарное количество отдельных элементов в этих множествах, В примере, проиллюстрированном на рис. 35.3, размер минимального покрытия множества равен 3. Задача о покрытии множества абстрагирует многие часто возникающие комбинаторные задачи. В качестве простого примера предположим, что множество Х представляет набор знаний, необходимых для решения задачи, над которой работает определенный коллектив сотрудников. Нужно сформировать комитет, состоящий из минимально возможного количества сотрудннжзв, причем такой, что при необходимости получения любой информации из множества Х окажется, что в комитете есть сотрудник, обладающий необходимыми знаниями. Если преобразовать эту задачу в задачу принятия решений, то в ней будет спрашиваться, существует ли покрытие, размер которого не превышает гс, где )с — дополнительный параметр, определенный в экземпляре задачи.
Как предлагается показать в упр. 35.3.2, версия этой задачи в форме задачи принятия решений является»чР- полной. П71 Глава 35. Прнближенные олгорнтмы Жадный приближенный алгоритм Жадный метод работает путем выбора на каждом этапе множества Я, покрывающего максимальное количество элементов, оставшихся непокрытыми.
бкее15У-Яет-СОчек(Х, У) 1 У=Х 2 С=О 3 згпйе У Ф И 4 Выбрать Я Е У; максимизирующее ~Я П Ц 5 У=У вЂ” Я 6 С = С1л(Я) 7 гегпгп С В примере на рис. 35.3 процедура Окее1эу-Яет-Сочен поочередно добавляет к С множества Яп Я1 и Яь, после чего добавляется либо Яз, либо Яб. Алгоритм работает следующим образом. На каждом этапе его работы множество У содержит элементы, оставшиеся непокрытыми. Множество С содержит покрытие, которое строится алгоритмом. Строка 4 представляет собой этап принятия решения в жадном методе.
Выбирается подмножество Я, покрывающее максимально возможное количество еще непокрытых элементов (с произвольным разрешением неоднозначностей). После выбора подмножества Я его элементы удаляются из множества У, а само подмножество Я помещается в семейство С. Когда алгоритм завершит свою работу, множество С будет содержать подсемейство семейства Т, покрывающее множество Х. Алгоритм бкеепу-Бет-Сочек легко реализовать таким образом, чтобы время его работы выражалось полиномиальной функцией от величин (Х! и ~У !. Поскольку количество итераций цикла в строках 3-6 ограничено сверху величиной ш1п()Х(, ~У'(), а тело цикла можно реализовать таким образом, чтобы его выполнение завершалось за время 0((Х( (У'О, простая реализация алгоритма имеет время работы, равное 0((Х! (У! ш1п((Х(, )У1)).
В упр. 35.3.3 предлагается разработать алгоритм с линейным временем работы. Анализ Теперь покажем, что жадный алгоритм возвращает покрытие множества, не слишком сильно превышающее оптимальное покрытие. Для удобства в этой главе 4-е по порядку гармоническое число Нл = 2"~ 1/1 (см. раздел А.1) будет обозначаться как Н(е(). В качестве граничного условия определим Н(0) = О. Теорема 35.4 Алгоритм Пкее1эу-Яет-Сонек является р(п)-приближенным алгоритмом с полиномиальным временем работы, где р(п) = Н(гиах (~Я~: Я Е У)) . 11 7х ехахть 'е11, Ихбраиные темы ~яе — (Н, О Нз и " . и Н; ,)~ На каждом шаге алгоритма присваивается единичная стоимость, поэтому (С) = ~~~ с (35.9) хЕХ Каждый элемент х Е Х находится как минимум в одном множестве из оптималь- ного покрытия С*, так что с > ~~~ с (35.10) БЕС' хЕх' хЕХ Объединив (35.9) и (35.10), получаем соотношение (С) < ~ ~~> с (35.11) Бес' хек Оставшаяся часть доказательства основана на приведенном ниже ключевом неравенстве, которое будет доказано чуть позже.
Для любого множества Я, принадлежащего семейству У, выполняется неравенство с < Н()Я!) . (35.12) Из неравенств (35.11) и (35.12) следует, что 1с! < х ~н(~н~) Бес' < (С*) Н(гпахДЯ): Я Е У)), что и доказывает теорему. Доказашааьслеао. Мы уже показали, что алгоритм Окллпу-Бит-Соцнк выполняется за полиномиальное время. Чтобы показать, что Окннпу-Ялт-Сочли является р(п)-приближенным алгоритмом, присвоим каждому из выбранных алгоритмом множеств стоимость 1, распределим ее по всем элементам, покрытым за первый раз, а затем с помощью этих стоимостей получим искомое соотношение между размером оптимального покрытия множества С* и размером покрытия С, возвращенного алгоритмом.
Обозначим г'-е подмножество, выбранное алгоритмом Окпии'-Ялт-Сочли, как Не; добавление подмножества Яе в множество С приводит к увеличению стоимости на единицу. Равномерно распределим стоимость, соответствующую выбору подмножества Яь между элементами, которые впервые покрываются этим подмножеством. Обозначим через с стоимость, выделенную элементу з, для каждого х е Х. Стоимость выделяется каждому элементу только один раз, когда этот элемент покрывается впервые. Если элемент х первый раз покрывается подмножеством Яе, то выполняется равенство Глава 35.
Приближенные алюритмы !173 Все, что осталось сделать — это доказать неравенство (35.12). Рассмотрим произвольные множество Я Е У' и индекс 1 = 1, 2,..., ~С~ и введем величину , = ~Н вЂ” (Я 13 Я О .. 13 Н1) ~, ь 1 ~Н1 — 1Я 13Н О" 13Н, 1)~ Заметим, что )Я, — (Я1 ОЯ10 0Я, 1)() )Я вЂ” (Я1 13ог0 ''~1о1 — 1)~ поскольку при жадном выборе множества Я; гарантируется, что множество Я не может покрыть больше новых элементов, чем множество Я, 1в противном слу- чае вместо множества Ял было бы выбрано множество Я). Таким образом, мы получаем неравенство ь ~с < 7 (и, 1 — ен).— вам л=1 П1-1 Теперь ограничим эту величину следуюшим образом: ь (и, 1 — и;) П; 1 и, ЕЕ л=1 л=и,+1 /с ЕЕ «=1 з=и;~-1 с < 1поскольку 3 < и, 1) Е Еу-Е; которая равна количеству элементов множества Я, оставшихся непокрытыми после того, как в алгоритме были выбраны множества 51, Яз,..., Яь Определим величину пс = ~Я~, равную количеству элементов множества Я, которые изначально непокрыты.
Пусть 1е — минимальный индекс, при котором выполняется равенство иь = О, т.е. каждый элемент множества Я покрывается хотя бы одним из множеств Я1, Яз,..., Яы Тогда ил 1 > ил, и при 1 = 1, 2,..., )е множеством Я; впервые покрываются о, 1 — ьх элементов множества Я. Таким образом, /174 Часть Р71 Иьаланнте тент = Н(ис) — Н(иь) = Н(ис) — Н(0) = Н(ио) = Н(ф0, (благодаря телескопичности суммы) (поскольку Н(0) = О) что и завершает доказательство неравенства (35.12). Следсльвле 35.5 Алгоритм Океепч-Бет-Сочен является (1п ~Х~ + 1)-приближенным алгоритмом с полиномиальным временем работы. В некоторых приложениях величина шах(~Я~: Я Е У') представляет собой небольшую константу, поэтому решение, которое возвращается алгоритмом Океепч-бет-Сочен, больше оптимального на множитель, не превышающий малую константу. Одно из таких приложений — получение с помощью описанного выше эвристического метода приближенного вершинного покрытия графа, степень вершин которого не превышает 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
