1 Лектор: Кононов Александр Вениаминович НГУ, ауд. 313 четверг 16:00 Приближенные алгоритмы

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

3 Что нужно знать! Задача Индивидуальная задача Оптимизационная задача Размер входа индивидуальной задачи Алгоритм Временная сложность алгоритма Полиномиальный алгоритм Задача линейного программирования NP-трудная задача

4 Литература по комбинаторной оптимизации М.Гэри, Д.Джонсон, Вычислительные машины и труднорешаемые задачи, Мир, Х. Пападимитриу, К. Стайглиц, Комбинаторная оптимизация: Алгоритмы и сложность, Мир, Т. Кормен, Ч. Лейзерсон, Р. Риверст, К. Штайн Алгоритмы: построение и анализ, Вильямс, Korte B., Vygen J., Combinatorial Optimization: theory and algorithms, (Algorithms and Combinatorics 21), Springer, Berlin, 2010.

5 Задача Задача Π определяется следующей информацией: общим списком всех ее параметров формулировкой тех свойств, которым должен удовлетворять ответ или, другими словами, решение задачи. Индивидуальная задача I получается из задачи Π, если всем параметрам задачи Π присвоить конкретные значения.

6 Размер входа Размер входа индивидуальной задачи с рациональными данными равен числу бит, требуемых для ее двоичного представления в некоторой «наилучшей» бинарной кодировке.

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

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

9 Задача о вершинном покрытии Дано: Связный граф G = (V, E), веса вершин c: V Q +. Найти вершинное покрытие наименьшего веса. Вершинное покрытие это множество вершин V V такое, что каждое ребро имеет граничную точку в V.

10 Алгоритм Множество исходных данных (Вход) Последовательность инструкций, каждая из которых может быть представлена цепочкой элементарных шагов. Для каждого допустимого входа алгоритм в процессе вычисления выполняет единственно определенную серию элементарных шагов и выдает некоторый ответ.

11 Временная сложность алгоритма Время работы алгоритма удобно выражать в виде функции от одной переменной, характеризующей «размер» индивидуальной задачи, то есть от ее размера входа. Временная сложность алгоритма это функция, которая каждому входу размера x ставит в соответствие максимальное по всем индивидуальным задачам время (число элементарных шагов), затрачиваемое алгоритмом на решение индивидуальных задач данного размера.

12 Полиномиальный алгоритм Алгоритм с рациональным входом называется полиномиальным, если существует целое k такое что алгоритм работает время O(x k ), где x есть размер входа и все числа, используемые алгоритмом в процессе вычислений ограничены величиной O(x k ) бит. Алгоритм с произвольным входом называется сильно полиномиальным, если существует целое k такое что алгоритм работает время O(n k ) на любом входе состоящим из n чисел и он полиномиальный на рациональном входе. Если k =1 алгоритм называется линейным.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33 Литература Approximation Algorithms for NP-hard problems, edited by D.Hochbaum, PWS Publishing Company, V. Vazirani Approximation Algorithms, Springer-Verlag, Berlin, P. Schuurman, G. Woeginger Approximation Schemes – A Tutorial, chapter of the book Lecture on Scheduling, to appear in 2008.

Практика 1.Принадлежит ли задача распознавания существования в сети потока заданной величины к классу NP и почему? 2.Записать задачу о вершинном покрытии наименьшей мощности как задачу ЦЛП. 3.Записать двойственную задачу к ее линейной релаксации. 34