37.2-2

Задачу коммивояжёра можно решать с помощью эвристики ближайшей точки следующим образом. Начнём с тривиального цикла, содержащего одну вершину (её можно выбрать произвольно). Затем будем расширять его так: выбираем самую близкую в циклу вершину v, смотрим, какая вершина и цикла ближе всего кии вставляем v в цикл сразу после и. Так мы делаем до тех пор, пока цикл не пройдёт через все вершины. Докажите, что полученный таким образом цикл имеет стоимость не более чем вдвое худшую оптимального.

Задача о гамильтоновом цикле с короткими рёбрами состоит в отыскании гамильтонова цикла, у которого длина самого длинного ребра была бы как можно меньше. В продположении неравенства треугольника построить полиномиальный приближённый алгоритм, решающий эту задачу с ошибкой не более чем в 3 раза. (Указание: Докажите по индукции, что можно обойти все вершины минимального покрывающего дерева по одному разу, взяв его полный обход и пропуская некоторые вершины, при этом не пропуская более двух внутренних вершин подряд.)

Докажите, что если вершинами графа являются точки на плоскости, а стоимость ребра - расстояние между его концами, то оптимальный цикл в задаче о коммивояжёре является несамопере-секающимся многоугольником.

Задача о покрытии множествами

Эта задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-трудной). Однако подход, использованный в приближенном алгоритме для задачи о вершинном покрытии, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм; даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно медленно (логарифм - медленно растущая функция), поэтому такой подход может быть полезен.

Исходным данными задачи о покрытии множествами (set-covering problem) являются конечное множество X, а также семейство Т его подмножеств. При этом каждый элемент множества X принадлежит хотя бу одному из подмножеств семейства Т:

set

Мы ищем минимальное число подмножеств из J7, которые вместе покрывают множество X, то есть семейство mathcalC наименьшей мощности, для которого

37.2-3

37.2-4

sec

Рис. 37.3 37.3. Пример исходных данных для задачи о покрытии множествами. Множество X состоит из 12 чёрных точек. Семейство Т состоит из 6 множеств Si-Se. Минимальное покрытие имеет размер 3 (множества S3, S4, S5). Жадный алгоритм даёт покрытие размера 4, велючая в него множества Si, S4, S5 и S3 (в указанном порядке).

Такое семейство С мы буде называть покрытием множества X. (Пример задачи о покрытии приведён на рис. 37.3.)

Можно представлять себе X как набор навыков, необходимых для выполнения какого-то задания; есть несколько человек, владеющих некоторыми из них. Надо сформировать минимальную группу для выполнения задания, включающую в себя носителей всех необходимых навыков.

Задачу о покрытии множествами можно сформулировать в варианте, требующем ответа да/нет: «существует ли покрытие размера не болтше к» (для любого заданного к). В упражнении 37.3-2 мы попросим вас доказать, что эта задача является NP-полной.

Жадный приближённый алгоритм

Этот алгоритм основан на простой идее: в каждый момент мы выбираем множество, покрывающее максимальное число ещё не покрытых элементов.

1U <- X

2mathcal{C> <- О

3while U \пе \emptyset

4do выбираем S \in \mathcal{F} с наибольшим S\cap U

5U <- U - S

6\mathcal{C> <- \mathcal{C> \cup \{S\>

7return \mathcal{C}

В примере на рис. 37.3 этот алгоритм выбирает множества в таком порядке: Si, S4, S5 и S3.

У каждый момент работы алгоритма множество U содержит ещё не покрытые элементы, а семейство С - уже включённые в покрытие подмножества. На шаге 4 производится жадный выбор: в качестве S берётся множество, покрывающее наибольшее число ещё не покрытых элементов (если таких несколько, берём любое). После этого S добавляется к семейству С, а его элементы удаляются из U. В конце концов множество ещё не покрытых элементов (U) пусто, а С является покрытием множества X.

Видно, что алгоритм Greedy-Set-Cover полиномиален (время работы оценивается многочленом от Х и \F\): количество повторений цикла не превосходит min(X, \F\), а каждое повторение легко реализовать за 0(А • \F\) операций, так что всего будет 0(Х • \F\ min(X, \F\)) операций. В упражнении 37.3-3 мы предложим вам реализовать этот алгоритм за линейное время.

Анализ алгоритма

Теперь мы должны сравнить размер покрытия, даваемого этим алгоритм, с минимально возможным. Нам понадобится обозначение Н(d) для суммы первых d членов гармонического ряда (см. раз-

Теорема 37.4.

Размер покрытия, даваемого алгоритмом Greedy-Set-Cover, превосходит минимально возможный не более чем в

Доказательство.

Жадный алгоритм отбирает множества одно за другим, на каждом шаге выбирая то из них, которое покрывает больше всего непокрытых элементов. Будем представлять себе, что на каждом шаге имеется доллар, который поровну распределяется между всеми вновь покрытыми элементами. Таким образом, каждый элемент получает деньги только однажды - на том шаге, когда он впервые попадает в покрытие, и получает тем больше денег, чем меньше элементов оказались в том же положении. Формально говоря, если элемент х входит в множество Si, выбранное на г-ом шаге работы алгоритма, и не входит в Sk при меньших к, то он получит

долларов. [Заметим в скобках, что выгоднее получать деньги как можно позже, так как по мере продвижения алгоритма количество вновь покрываемых за раз элементов может только уменьшаться - жадный алгоритм не будет «оставлять лакомый кусок на потом»]

Всего будет израсходовано \С\ долларов, по одному на каждый элемент построенного покрытия С. Эти деньги будут каким-то образом распределены между всеми элементами множества X (элемент х получает сх долларов). Нам надо показать, что оптимальное покрытие (содержащее минимально возможное число множеств) не может быть сильно меньше нашего. Мы сделаем это, убедившись, что для любого множества S из семейства Т общая сумма денег, полученная всеми элементами S, не превосходит Н(\S\), и потому понадобится не менее \С\/Н(max{\S\ : S G J7}) элементов оптимального покрытия, чтобы набрать общую сумму в \С\.

Формально говоря, для оптимального покрытия С* мы имеем

дел 3.1): tf(d) = £ti 1/г.

H(max{\S\ : S G J7})

раз.

1

Si- (S1US2U...S1)\

(37.9)

sec*xes