Алгоритмы обработки данных

1. NP-сложные и труднорешаемые задачи

Для оценки сложности алгоритма, как уже говорилось выше (см. п. 1.2), используется О-символика.

На основе этой оценки можно привести следующую классификацию алгоритмов, при размере входных данных, равном n:

• постоянные – сложность не зависит от n: O(1);

• линейные – сложность О(n);

• полиномиальные – сложность O(n^m), где m – константа;

• экспоненциальные – сложность O(t^f(n)), где t – константа, которая больше 1, а f(n) – полиномиальная функция;

• суперполиномиальные – сложность O(с^f(n)), где с – константа, а f(n) – функция возрастающая быстрее постоянной, но медленнее линейной;

Простые задачи (решаемые) – это задачи, решаемые за полиномиальное время.

Труднорешаемые задачи – это задачи, которые не решаются за полиномиальное время, либо алгоритм решения за полиномиальное время не найден.

Помимо этого, как было доказано А. Тьюрингом, существуют принципиально неразрешимые задачи.

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

1. класс P – класс задач, которые можно решить за полиномиальное время;

2. класс NP – класс задач, которые можно решить за полиномиальное время только на недетерминированной Машине Тьюринга, которая в отличии от обычной Машины Тьюринга может делать предположения. Это задачи, у которых есть ответ, найти который трудно, но проверить можно за полиномиальное время;

3. класс NP-полных задач – класс задач, не менее сложных, чем любая NP задача;

4. класс EXPTIME – класс задач, которые решаются за экспоненциальное время;

5. класс EXPTIME-полных задач – класс задач, которые не решаются за детерминированное полиномиальное время. Известно, что P <> EXPTIME.

Очевидно, что P входит в NP, но вот проверить, что (P <> NP) или (P = NP) до сих пор не удалось.

В качестве примера NP-полной задачи приведем задачу коммивояжера. Имеется n пунктов, расстояния между любыми двумя из которых известны и представляют собой целые числа. Требуется объехать все пункты, посетив каждый по одному разу и, возвратившись в исходный пункт, так, чтобы длина полученного кольцевого маршрута была наименьшей.

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

Принимая n=100 и произведя очень грубую (явно заниженную) оценку, то можно сделать вывод, что для решения данной задачи придется выполнить не менее 10²¹ операций. Скорость самых современных ЭВМ не превосходит 10¹² операций в секунду. Следовательно, для получения результата придется ждать 10⁹ секунд, или более 30 лет.

В настоящее время полиномиальное решение задачи коммивояжера не известно.