Алгоритм
<<  Алгоритм, событие, или… Формализация понятия «Алгоритм»  >>
Приближенные алгоритмы
Приближенные алгоритмы
Объект исследования
Объект исследования
Что нужно знать
Что нужно знать
Литература по комбинаторной оптимизации
Литература по комбинаторной оптимизации
Задача
Задача
Размер входа
Размер входа
Оптимизационная задача
Оптимизационная задача
Оптимальное решение
Оптимальное решение
Задача о вершинном покрытии
Задача о вершинном покрытии
Алгоритм
Алгоритм
Временная сложность алгоритма
Временная сложность алгоритма
Полиномиальный алгоритм
Полиномиальный алгоритм
Np-трудная задача
Np-трудная задача
Что делать с NP-трудными задачами
Что делать с NP-трудными задачами
Приближенный алгоритм
Приближенный алгоритм
Полиномиальная приближенная схема (PTAS)
Полиномиальная приближенная схема (PTAS)
Вполне полиномиальная приближенная схема (FPTAS)
Вполне полиномиальная приближенная схема (FPTAS)
Алгоритм
Алгоритм
Задача линейного программирования
Задача линейного программирования
Полиномиально разрешимые задачи
Полиномиально разрешимые задачи
Вопрос о качестве алгоритма
Вопрос о качестве алгоритма
Как оценить качество алгоритма
Как оценить качество алгоритма
Задача о вершинном покрытии наименьшей мощности
Задача о вершинном покрытии наименьшей мощности
Максимальное паросочетание
Максимальное паросочетание
Алгоритм «Простой»
Алгоритм «Простой»
Теорема 1.1 Алгоритм «Простой» является 2-приближенным алгоритмом для
Теорема 1.1 Алгоритм «Простой» является 2-приближенным алгоритмом для
Теорема 1.1 Алгоритм «Простой» является 2-приближенным алгоритмом для
Теорема 1.1 Алгоритм «Простой» является 2-приближенным алгоритмом для
Качество анализа, нижней оценки, …
Качество анализа, нижней оценки, …
Точность оценки
Точность оценки
Качество анализа, нижней оценки, …
Качество анализа, нижней оценки, …
Сравнение нижней оценки и оптимального решения
Сравнение нижней оценки и оптимального решения
Качество анализа, нижней оценки, …
Качество анализа, нижней оценки, …
Литература
Литература
Практика
Практика

Презентация: «Приближенные алгоритмы». Автор: Kononov. Файл: «Приближенные алгоритмы.ppt». Размер zip-архива: 67 КБ.

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

содержание презентации «Приближенные алгоритмы.ppt»
СлайдТекст
1 Приближенные алгоритмы

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

НГУ, ауд. 313 четверг 16:00

Лектор: Кононов Александр Вениаминович

1

2 Объект исследования

Объект исследования

Np-трудные задачи оптимизации

2

3 Что нужно знать

Что нужно знать

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

3

4 Литература по комбинаторной оптимизации

Литература по комбинаторной оптимизации

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

4

5 Задача

Задача

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

5

6 Размер входа

Размер входа

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

6

7 Оптимизационная задача

Оптимизационная задача

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

7

8 Оптимальное решение

Оптимальное решение

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

8

9 Задача о вершинном покрытии

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

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

9

10 Алгоритм

Алгоритм

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

10

11 Временная сложность алгоритма

Временная сложность алгоритма

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

11

12 Полиномиальный алгоритм

Полиномиальный алгоритм

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

12

13 Np-трудная задача

Np-трудная задача

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

13

14 Что делать с NP-трудными задачами

Что делать с NP-трудными задачами

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

14

15 Приближенный алгоритм

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

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

15

16 Полиномиальная приближенная схема (PTAS)

Полиномиальная приближенная схема (PTAS)

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

16

17 Вполне полиномиальная приближенная схема (FPTAS)

Вполне полиномиальная приближенная схема (FPTAS)

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

17

18 Алгоритм

Алгоритм

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

18

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

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

19

20 Полиномиально разрешимые задачи

Полиномиально разрешимые задачи

Задача об остовном дереве минимального веса Задача о максимальном потоке Задача о максимальном паросочетании Задача о k-факторе минимального веса ???

20

21 Вопрос о качестве алгоритма

Вопрос о качестве алгоритма

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

21

22 Как оценить качество алгоритма

Как оценить качество алгоритма

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

22

23 Задача о вершинном покрытии наименьшей мощности

Задача о вершинном покрытии наименьшей мощности

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

23

24 Максимальное паросочетание

Максимальное паросочетание

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

24

25 Алгоритм «Простой»

Алгоритм «Простой»

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

25

26 Теорема 1.1 Алгоритм «Простой» является 2-приближенным алгоритмом для

Теорема 1.1 Алгоритм «Простой» является 2-приближенным алгоритмом для

задачи «Вершинное покрытие наименьшей мощности».

Оценка качества алгоритма «Простой»

26

27 Теорема 1.1 Алгоритм «Простой» является 2-приближенным алгоритмом для

Теорема 1.1 Алгоритм «Простой» является 2-приближенным алгоритмом для

задачи «Вершинное покрытие наименьшей мощности».

Оценка качества алгоритма «Простой»

28 Качество анализа, нижней оценки, …

Качество анализа, нижней оценки, …

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

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

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

30 Качество анализа, нижней оценки, …

Качество анализа, нижней оценки, …

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

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

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

32 Качество анализа, нижней оценки, …

Качество анализа, нижней оценки, …

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

33 Литература

Литература

Approximation Algorithms for NP-hard problems, edited by D.Hochbaum, PWS Publishing Company, 1997. V. Vazirani Approximation Algorithms, Springer-Verlag, Berlin, 2001. P. Schuurman, G. Woeginger Approximation Schemes – A Tutorial, chapter of the book “Lecture on Scheduling”, to appear in 2008.

33

34 Практика

Практика

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

34

«Приближенные алгоритмы»
http://900igr.net/prezentacija/informatika/priblizhennye-algoritmy-124245.html
cсылка на страницу
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Алгоритм > Приближенные алгоритмы