1 Приближенные алгоритмы Комбинаторные алгоритмы

2 Объект исследования NP-трудные задачи оптимизации

3 Оптимизационная задача Оптимизационная задача Π есть либо задача минимизации, либо задача максимизации и состоит из множества Ω Π индивидуальных задач; для каждой I Ω Π конечного множества Sol Π допустимых решений индивидуальной задачи I ; функции h Π, сопоставляющей каждой индивидуальной задаче I Ω Π и каждому допустимому решению σ Sol Π некоторое рациональное число y(I, σ), называемое величиной решения σ.

4 Оптимальное решение Если Π задача минимизации, то оптимальным решением индивидуальной задачи I Ω Π является такое допустимое решение σ* Sol Π, что для всех σ Sol Π выполнено неравенство y(I, σ*) y(I, σ). Для обозначения величины y(I, σ*) оптимального решения индивидуальной задачи I будет использоваться символ OPT(I).

5 NP-трудная задача Задача Π является NP-трудной, если к ней сводится некоторая NP-полная задача. Существование точного полиномиального алгоритма для NP-трудной задачи влечет P = NP. Почти все интересные дискретные оптимизационные задачи NP-трудны.

6 Что делать с NP-трудными задачами? Решать точно «переборными» алгоритмами Решать приближенно –с апостериорной оценкой точности –с априорной оценкой точности Мы будем строить приближенные полиномиальные алгоритмы с априорной оценкой точности.

7 Приближенный алгоритм Полиномиальный алгоритм A называется ρ-приближенным алгоритмом для задачи минимизации Π, если для каждой индивидуальной задачи I Ω Π, A(I) ρOPT(I).

8 Полиномиальная приближенная схема (PTAS) Семейство приближенных алгоритмов для задачи Π, {A ε } ε называется полиномиальной приближенной схемой, если алгоритм A ε (1+ε)-приближенный алгоритм и время его работы ограничено полиномом от размера входа при фиксированном ε.

9 Вполне полиномиальная приближенная схема (FPTAS) Семейство приближенных алгоритмов для задачи Π, {A ε } ε называется вполне полиномиальной приближенной схемой, если алгоритм A ε (1+ε)-приближенный алгоритм и время его работы ограничено полиномом от размера входа и 1/ε.

10 Алгоритм Как построить приближенный алгоритм? –Изучение комбинаторной структуры задачи. –Изучение свойств оптимального решения. –Поиск алгоритмической техники, которая использует эти свойства. Обобщение и расширение техники и опыта, накопленного при построении полиномиальных алгоритмов.

11 Задача линейного программирования

12 Полиномиально разрешимые задачи Задача об остовном дереве минимального веса Задача о максимальном потоке Задача о максимальном паросочетании Задача о k-факторе минимального веса

13 Вопрос о качестве алгоритма Как оценить качество алгоритма? Сравнить стоимость получаемых решений со стоимостью оптимального решения. Найти стоимость оптимального решения также сложно, как и само оптимальное решение.

14 Как оценить качество алгоритма? Найти «хорошую» полиномиально вычислимую нижнюю оценку на стоимость оптимального решения.

15 Задача «Вершинное покрытие наименьшей мощности» Дано: Связный граф G = (V, E). Найти вершинное покрытие наименьшей мощности.

16 Максимальное паросочетание Дан граф G = (V, E), подмножество ребер M E называется паросочетанием, если никакие два ребра из M не смежны, то есть не имеют общей граничной точки. Паросочетание максимальное по включению. Паросочетание максимальное по мощности. Размер паросочетания максимального по включению является нижней границей на стоимость оптимального решения задачи «Вершинное покрытие наименьшей мощности».

17 Алгоритм «Простой» 1.Найти в графе G произвольное паросочетание M максимальное по включению. 2.Выдать множество вершин, попавших в паросочетание M.

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

19 Качество анализа, нижней оценки, … Можно ли за полиномиальное время получать решение с гарантированной оценкой лучше чем 2? –Можно ли улучшить анализ качества алгоритма «Простой»? –Можно ли построить алгоритм, который всегда находит решение с оценкой лучше чем 2 от предложенной нижней границы? –Существует ли другой алгоритм с гарантированной оценкой лучше чем 2?

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

21 Качество анализа, нижней оценки, … Можно ли за полиномиальное время получать решение с гарантированной оценкой лучше чем 2? –Можно ли улучшить анализ качества алгоритма «Простой»? Ответ нет. –Можно ли построить алгоритм, который всегда находит решение с оценкой лучше чем 2 от предложенной нижней границы? –Существует ли другой алгоритм с гарантированной оценкой лучше чем 2?

22 Сравнение нижней оценки и оптимального решения

23 Качество анализа, нижней оценки, … Можно ли за полиномиальное время получать решение с гарантированной оценкой лучше чем 2? –Можно ли улучшить анализ качества алгоритма «Простой»? Ответ нет. –Можно ли построить алгоритм, который всегда находит решение с оценкой лучше чем 2 от предложенной нижней границы? Ответ нет. –Существует ли другой алгоритм с гарантированной оценкой лучше чем 2?

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

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

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

27 Алгоритм Хватала 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)

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

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

30 Доказательство леммы 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).

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

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

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

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

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

36 Доказательство Пусть с > 0: w(v) = с deg(v). Пусть U оптимальное вершинное покрытие.

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

38 Алгоритм «Уровневый» 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}) (удаляем вершины степени 0) 2)While V i do: c min{w(v)/deg(v)} t(v) c deg(v) (находим наибольшую пропорционально- степенную функцию относительно w) 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}) (удаляем вершины степени 0) 3)Output (Sol)

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

40 Пример Sol

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

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

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

44 Пример Sol

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

46 Схема работы алгоритма DkDk W k-1 D k-1 W1W1 D1D1 W0W0 D0D0 GkGk G k-1 G1G1 G0G0 Sol C*G i – вершинное покрытие G i Пусть t 0,…t k-1 функции на графах G 0,…G k-1.

47 Доказательство Пусть C полученное вершинное покрытие. Пусть C* оптимальное вершинное покрытие. C*G i – вершинное покрытие G i Лемма 4.4

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

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

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

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

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

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

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