Комбинаторные алгоритмы Задача о покрытии

Задача о покрытии множествами Дано: Совокупность U из n элементов, и набор подмножеств U, S = {S 1,…, S k }, и веса(стоимости) подмножеств c: S Q +. Найти покрытие наименьшего веса. S' S является покрытием, если любой элемент из U принадлежит хотя бы одному элементу из S'.

Кратность Пусть f i – кратность элемента e i, то есть число множеств из S, в которые он входит. Пусть f = max i=1,…,n f i.

Жадная стратегия Пусть C будет множество элементов уже покрытое на предыдущих итерациях. Тогда α i = c(S i )/|S i – C| называется эффективностью множества S i и равна средней стоимости, с которой покрывается новый элемент. Назовем ценой элемента e среднюю стоимость с которой он был покрыт. Эквивалентно, когда множество S выбрано, мы можем понимать, что его стоимость равномерно распределена среди вновь покрытых элементов.

Алгоритм Хватала 0) Input (U, S, c: S Q + ) 1) C, Sol 2) While C U do: Найти S i S – Sol, у которого α i =c(S i )/|S i – C| минимально. Sol Sol {S i } C С S i (S i – самое эффективное) price(e) = α i для всех e S i – C 3) Output (Sol)

Анализ алгоритма Хватала Упорядочим элементы из U в порядке, в котором они были покрыты алгоритмом. Пусть это будет e 1,…,e n. Лемма 2.1 Для каждого k {1,…,n}, price(e k ) OPT/(n–k+1).

Доказательство леммы 2.1 e i,…,e k,…,e n e 1,…,e i –1 OPT C S – C

Доказательство леммы 2.1 e i,…,e k,…,e n Общая эффективность не больше чем OPT/(n – i + 1) OPT/(n – k + 1) Существует S j S – C с α j OPT/(n – k + 1). price(e k ) OPT/(n–k+1).

Оценка качества алгоритма Хватала Теорема 2.2 Алгоритм Хватала является H n -приближенным алгоритмом для задачи о покрытии множествами, где H n =1+1/2+1/3+…+1/n. Доказательство:

Точность оценки 1+ ε 1/n1/(n–1)1/(n–2) 1/2 1

Задача о вершинном покрытии Дано: Граф G = (V, E), веса вершин w: V Q +. Найти вершинное покрытие наименьшего веса.

Пропорционально-степенная функция Назовем функцию, соответствующую весам вершин, пропорционально-степенной, если существует константа с > 0, такая что вес каждой вершины v V равен с deg(v).

Нижняя оценка Лемма 2.3 Пусть w: V Q + пропорционально- степенная функция. Тогда w(V) 2 OPT.

Наибольшая пропорционально- степенная функция Пусть w: V Q + произвольная функция. Определим наибольшую пропорционально- степенную функцию относительно w в графе G следующим образом: –Удалим из графа все вершины степени 0. Среди оставшихся вершин вычислим c= min{w(v)/deg(v)}. –Тогда t(v) = c deg(v) есть искомая функция Определим через w(v) = w(v) – t(v) остаточную функцию весов.

Алгоритм «Уровневый» 0) Input (G = (V, E), w: V Q + ) 1) Sol, i 0, w(v) w(v), V 0 V – D 0 (D 0 ={v V |deg(v)=0}) 2) While V i do: w(v) w(v) – t i (v) Sol Sol W i (W i ={v V i |w(v)=0}) V i+1 V i – W i i i+1 V i V i – D i (D i ={v G i |deg(v)=0}) 3)Output (Sol)

Пример t(v) = 1 deg(v)

Пример Sol

Пример Sol t(v) = (2/3) deg(v)

Пример 5/3 0 1/3 2/3 Sol

Пример 5/3 1/3 2/3 Sol t(v) = (2/3) deg(v)

Пример Sol

Оценка качества алгоритма «Уровневый» Теорема 2.4 Алгоритм «Уровневый» является 2-приближенным алгоритмом для задачи о вершинном покрытии.

Схема работы алгоритма DkDk W k-1 D k-1 W1W1 D1D1 W0W0 D0D0 GkGk G k-1 G1G1 G0G0 Sol C*G i – вершинное покрытие G i

Точность оценки

Задача о кратчайшей суперстроке Дано: Конечный алфавит Σ и множество из n строк S = {s 1,…,s n } Σ +. Найти кратчайшую суперстроку s, которая содержит каждую строку s i, как подстроку. Без ограничения общности будем считать, что никакая строка s i не содержит другую строку s j, i j, как подстроку.

Задача о кратчайшей суперстроке как задача о покрытии множествами sisi sjsj k > 0 π ijk M ={ π ijk | π ijk – допустимая} π M : set( π )={s S | s – подстрока π } U cover S string S cover {set( π ijk ) | π ijk – допустимая} c(set( π )) = | π |

Нижняя оценка Лемма 2.5 OPT string OPT cover 2 OPT string

OPT cover 2 OPT string s sb1sb1 se1se1 sb2sb2 se2se2 sb3sb3 se3se3 π1π1 π2π2 π3π3

Алгоритм Ли 1)По индивидуальной задаче о кратчайшей суперстроке строим индивидуальную задачу о покрытии множествами. 2)Алгоритмом Хватала находим покрытие. Пусть оно состоит из множеств set(π 1 ),…, set(π k ). 3)Соединяем строки π 1,…,π k в любом порядке. Назовем полученную строку s. 4) Output (s)

Оценка качества алгоритма Ли Теорема 2.6 Алгоритм Ли является 2H n -приближенным алгоритмом для задачи о кратчайшей суперстроке, где n – число строк в исходном примере.

Практика Задача об упаковке в контейнеры с ограничением на число предметов в одном контейнере. Дано: n предметов и их размеры a 1,…,a n (0,1]. Найти упаковку всех предметов в единичные ящики, так чтобы минимизировать число использованных ящиков, при условии что каждый ящик содержит не более пяти предметов. 1. Сформулировать задачу об упаковке как задачу о покрытии. 2. Является ли ваше сведение полиномиальным.