ЛЕКЦИЯ 14. Классы задач в зависимости от их трудности. Полиномиальные, недетерминированные алгоритмы. Стандартные NP-полные задачи. Решение NP-полной задачи
Кроме правильности и корректности алгоритма и программы важным фактором является – эффективность или сложность алгоритма, т.е. время выполнения T(n), n – входные данные. Нахождение T(n) для программы является сложной задачей. И обычно используют асимптотическую оценку этой функции, т.е. ее примерное поведение при больших n. Эту функцию сложности алгоритма обозначают O(n).
Сложность алгоритма – насколько быстро растет его трудоемкость с увеличением объема входных данных, или количество элементарных операций.
В настоящее время принято использовать виды оценки сложности вычисления (классы сложности) приведенные в табл. 13.
Таблица 13.
Классы сложности алгоритмов
Порядок от сложного к простому
Название класса сложности
Математическая формула
Примеры алгоритмов
Факториальная
n!
Алгоритмы комбинаторики (сочетания, перестановки и др.)
Экспоненциальная
Алгоритмы перебора
Полиномиальная
Алгоритмы простой сортировки
Линейный логарифм
Алгоритмы быстрой сортировки
Линейная
Перебор элементов массива
Логарифмическая
Бинарный поиск
Константная
k
Обращение к элементу массива по индексу
k – константа, n – переменные (входные данные)
Для решения различных задач комбинаторной оптимизации некоторые из алгоритмов весьма эффективны, другие — очень медлительны. И некоторые задачи просто не допускают эффективных алгоритмов. Возникает естественный вопрос: почему? Действительно ли, некоторые задачи по существу своему более сложные, чем другие, или пока для их решения не найдено эффективных алгоритмов?
Есть по крайней мере две причины для классификации задач по сложности. Во-первых, если мы знаем, что задача принадлежит классу очень сложных задач, то мы не должны сосредотачиваться на получении оптимального решения, а можем попытаться получить приближенное решение, верхние и нижние оценки, воспользоваться эвристиками и т.д. Во-вторых, если задачи принадлежат одному классу, то иногда решения одной из них удается преобразовать в метод решения другой. Не легко определить, какая задача принадлежит какому классу. Две задачи могут казаться весьма похожими, однако одна из них может быть намного сложнее другой.
Для примера рассмотрим две задачи.
(i) Задано множество n попарно различных положительных целых чисел x1, x2,…, хп(n четно). Необходимо разбить это множество на два подмножества мощности п/2каждое так, чтобы разность между суммами элементов этих подмножеств была максимальной.
(ii) Задано множество n попарно различных положительных целых чисел x1, x2,…,хп(п четно). Необходимо разбить это множество на два подмножества так, чтобы разность между суммами элементов этих подмножеств была минимальной.
Задачу (i) можно решить, сортируя числа x1, x2,…, хп и помещая п/2меньших чисел в первое подмножество, а п/2больших — во второе. Данная процедура выполнима за время O(nlogn). Другой способ — найти медиану и использовать ее для разбиения чисел на два множества. Известен алгоритм, который находит k-oeнаибольшее число среди n целых чисел за время О(п), поэтому второй метод решения задачи (i) использует время О(п). Так как, надо полагать, каждый алгоритм, решающий эту задачу, должен проверить каждое число, то О(п)является нижней оценкой. На самом деле, мы можем решить обобщение этой задачи, когда требуется разбить множество на подмножества мощности k и n - k: для этого достаточно найти k-oeнаибольшее число.
Задачу (ii) можно решить, разбивая при всех k исходное множество на подмножества мощности k и (п – k)и записывая суммы. Рассматривая все k, мы, конечно же, найдем минимальную разность. Этот алгоритм использует время, равное O(2n). Конечно, для этой задачи существуют более быстрые алгоритмы, однако никем не найден полиномиальный алгоритм или алгоритм с оценкой времени выполнения, в которой n не появлялось бы в показателе степени.
Замечание 1. Если x1, x2,…, хп заданы, то это индивидуальная задача. Решить задачу означает решить все индивидуальные задачи. Для конкретной индивидуальной задачи могут существовать очень эффективные алгоритмы, но нас интересует, как алгоритм ведет себя на самых худших входных данных.
Замечание 2. Имеются ввиду «большие» задачи. В качестве параметра, отвечающего за размер входных данных, можно выбирать разные величины, однако изменение параметра не должно приводить к изменению класса сложности.
Замечание 3. Существуют многочисленные способы кодирования данных для описания одной и той же задачи. Например, граф может быть задан матрицей инцидентности «узлы-дуги» или списком всех узлов с указанием соседних смежных узлов. Время работы алгоритма не зависит от способа кодирования, т.е сложность алгоритма никогда одновременно не будет полиномиальной для одного разумного способа кодирования и экспоненциальной для другого разумного способа кодирования. В этом смысле все разумные способы кодирования дают один и тот же результат.
Замечание 4. Разные компьютеры выполняют один и тот же алгоритм за разное время. Самый простой компьютер называется машиной Тьюринга. Это искусственный компьютер, модель абстрактной машины, которая может писать символы на ленту, читать, стирать их и заканчивать свою работу. Кроме этого, имеются несколько моделей машин с произвольным доступом к памяти. Эти модели являются аналогами самых производительных современных компьютеров. Оказывается, что если алгоритм использует экспоненциальное время на машине Тьюринга, то он требует экспоненциального времени на любом реальном компьютере и наоборот. Таким образом, мы можем предположить, что у нас есть компьютер с одним центральным процессором и неограниченной памятью.
