Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Труднорешаемые задачи



Теория NP-полноты

Рассмотренные ранее алгоритмы были полиномиальными.

Полиномиальным алгоритмом (или алгоритмом полиномиальной временной сложности) называется алгоритм, временная сложность которого равна O(p (n)), где p (n) – некоторая полиномиальная функция, а n – входная длина.

Множество полиномиальных алгоритмов образует класс полиномиальных алгоритмов – класс Р.

Всякая ли задача может быть решена за полиномиальное время? Ответ отрицательный, так как существуют вообще неразрешимые задачи, и есть задачи разрешимые, но за более чем полиномиальное время. Примеры:

1. Решение задачи об укладке рюкзака. При условии, что каждый из n предметов может быть упакован или не упакован в рюкзак, всего будет 2 n вариантов взятых предметов.

2. Решение задачи коммивояжера сводится в худшем случае к перебору всех возможных маршрутов, а их всего существует
(n- 1)!. Это зависимость не может быть выражена полиномиальной функцией, причем можно заметить, что n ≥2 n

Задачи, для решения которых не существует полиномиального алгоритма, но существует экспоненциальный алгоритм (O(an)), называют труднорешаемыми.

Отличие полиномиальных и экспоненциальных алгоритмов будет более ощутимо, если обратиться к таблице, в которой отображено время работы алгоритма на компьютере, выполняющем 1000000 оп/с:

n O(n)            
n 0.00001 c 0.00002 c 0.00003 c 0.00004 c 0.00005 c 0.00006 c
n2 0.0001 c 0.0004 c 0.0009 c 0.0016 c 0.0025 c 0.0036 c
n5 0.1 c 3.2 c 24.3 c 1.7 мин 5.2 мин 13 мин
2n 0.001 c 1 c 17.9 мин 12.7 дней 35.7 лет 366 столет.
3n 0.059 c 58 мин 6.5 лет 3855 стол. 2∙108 стол. 1.3∙1013ст.
n! 3.6 c 771,5 стол. 8∙1016стол

Таким образом, понятие полиномиально разрешимой задачи принято считать уточнением идеи «практически разрешимой» задачи:

1. Полиномиальные алгоритмы действительно работают быстро, а полиномы больших степеней (n 100) и полиномы с большим коэффициентом пропорциональности (1099· na) на практике встречаются крайне редко.

2. Полиномиальные алгоритмы не зависят от выбора конкретной модели вычислений (Pпо Тьюрингу= Pна МПД= P для параллельных вычислений).

3. Класс Р обладает свойством замкнутости (композиция двух полиномиальных алгоритмов дает алгоритм также полиномиальный, так как сумма, произведение и композиция многочленов, тоже являются многочленами).





Дата публикования: 2015-07-22; Прочитано: 971 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.008 с)...