Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 10 лет назад пользователемНадежда Писклова
1 Вычислительная сложность Классы сложности P и NP. Сергей Казаков, аспирант каф. КТ, НИУ ИТМО
2 Как все начиналось… Начало 1960-х годов Alan Cobham, 1964 Jack Edmonds, 1965 Они ввели сложностные классы 2
3 Разрешимые и неразрешимые задачи Проблема останова – неразрешимая задача Доказательство – от противного. 3
4 Сложностный класс P Класс P класс задач, разрешимых на детерминированной машине Тьюринга за полиномиальное время 4
5 Класс P. Примеры-1 Посчитать сумму чисел Посчитать произведение чисел Проверка простоты числа Сортировка массива Определение связности графа Эйлеров путь/цикл 5
6 Эйлеров путь/цикл in P Путь, проходящий по всем ребрам графа, и при этом только по одному разу Граф Кёнигсбергских мостов: Эйлер (1735 год): цикл существует граф связный и все вершины четной степени 6
7 Эйлеров путь 7
8 Эйлеров цикл procedure find_all_cycles (v): 1. пока есть цикл, проходящий через v 1. находим его 2. добавляем все вершины цикла к ответу 3. удаляем цикл из графа 2. идем по вершинам из ответа и для каждой рекурсивно вызываем себя find_all_cycles(nv) Working Time – O(M), M – число ребер 8
9 Сложностный класс NP Класс NP класс задач, у которых есть сертификат решения, который можно быстро (за полином) проверить на машине Тьюринга. Класс NP класс задач, которые можно быстро решить (за полином) на недетерминированной машине Тьюринга. 9
10 Класс NP. Примеры-1 Задача выполнимости булевых форму (SAT) Определение наличия в графе гамильтонова цикла Задача о коммивояжёре Задача поиска вершинного покрытия графа 10
11 Гамильтонов путь/цикл Гамильтонов путь путь в графе, содержащий каждую вершину графа ровно один раз Гамильтонов цикл – гамильтонов путь, начальная и конечная вершина которого совпадают 11
12 Гамильтонов путь/цикл 12
13 Задача коммивояжёра Задача коммивояжёра (англ. Travelling salesman problem, TSP) 13
14 NP-трудные и NP-полные задачи Сведение по Карпу: P1 сводится к P2 f: (p P1 f(p) P2) NP-трудность: P1 – NP-трудная задача, если P2 NP, P2 сводится к P1 NP-полная задача: из NP и NP-трудная 14
15 Соотношения P и NP 15
16 NP-трудные и NP-полные задачи Стивен Кук (1971 год): термин «NP-полная задача» задача SAT была первой задачей, для которой доказывалось это свойство. Определение наличия в графе гамильтонова цикла – NP-полная Задача о коммивояжёре – с оптимизацией – NP-трудная не длиннее k – NP-полная 16
17 Приближенные решения Многие задачи, представляющие практический интерес – NP-полные Для них маловероятно найти точный алгоритм с полиномиальным временем работы При небольшом объеме входных данных может подойти алгоритм, время работы которого выражается показательной функцией Иногда удается выделить важные частные случаи, разрешимые в течение полиномиального времени 17
18 Приближенные решения Можно найти в течение полиномиального времени решение, близкое к оптимальному. Алгоритм, возвращающий решения, близкие к оптимальным, называется приближенным алгоритмом. 18
19 Методы решения NP-полных задач Приближенные и эвристические методы – применение эвристик для выбора элементов решения. Псевдо полиномиальные алгоритмы – подкласс динамического программирования. Метод локальных улучшений – поиск более оптимального решения в окрестности некоторого текущего решения. Метод ветвей и границ - отбрасывание заведомо неоптимальных решений целыми классами в соответствии с некоторой оценкой. Метод случайного поиска – представление выбора последовательностью случайных выборов. 19
20 Спасибо за внимание! Вопросы? 20
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.