Сложность проблем

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

Проблемы, которые можно решить с помощью алгоритмов с полиномиальным временем, называют решаемыми, потому что при разумных входных данных обычно могут быть решены за разумное время (точное определение ” разумности” зависит от конкретных обстоятельств).

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

Алан Тьюринг доказал, что некоторые проблемы принципиально неразрешимы, то есть даже отвлекаясь от временной сложности, невозможно создать алгоритм их решения.

Вот некоторые из трудных задач:

• Задача комивояжера. Комивояжер должен объехать N городов с целью осуществления продажи своих товаров. Все N городов соединены дорогами по принципу “каждый с каждым”. Известна стоимость проезда между двумя любыми городами. Найти оптимальный маршур движения так, чтобы побывать во всех городах и при этом иметь минимальные затраты на дорогу.

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

• Тройная выполнимость. Есть список n логических выражений, каждое с тремя переменными.

Например: если (x и y) то z, (x и y) или не z и т.д. Существуют ли такие значения всех переменных, чтобы все утверждения были истинными?

Пример 1. Рассмотрим проблему вскрытия алгоритма шифрования по ключу. Временная сложность такого вскрытия пропорциональна числу возможных ключей, которое экспоненциально зависит от длины ключа. Если n – длина ключа, то сложность вскрытия грубой силой равна O(2n). При n бит сложность равна 256 и в этом случае вскрытие возможно за приемлимое время. При n = 112 бит сложность равна 2112 вскрытие становится невозможным.

Пример 2. Рассмотрим в качестве примера задачу комивояжера. Комивояжер должен объехать N городов с целью осуществления продажи своих товаров. Все N городов соединены дорогами по принципу “каждый с каждым”. Известна стоимость проезда между двумя любыми городами. Найти оптимальный маршур движения так, чтобы побывать во всех городах и при этом иметь минимальные затраты на дорогу. Исходная информация задана в виде перечня городов и соответствующей матрицы стоимостей, то есть двумерного массива с элементами C_ij , равными стоимости проезда из города i в город j. В данном случае матрица имеет N строк и N столбцов. Следует также уточнить, что маршрут начинается и заканчивается в одном (базовом) городе и не может дважды проходить через один и тот же город.

Решение (метод грубого перебора).

Произвольно пронумеруем N городов целыми числами от 1 до N, причем базовый город имеет номер N. Каждый тур (один из возможных маршрутов) однозначно соответствует перестановке целых чисел 1, 2, ..N – 1. Для каждой перестановки строим тур и определяем его стоимость. Обрабатывая все перестановки запоминаем маршрут, который имеет на текущий момент самую низкую стоимость. Если находится маршрут с меньшей стоимостью, то все дальнейшие сравнения осуществляем с ним.

Алгоритм 1. Задача комивояжера

TOUR ←1

MIN ← 1

for I ←1 to (N – 1)! do

P ← get P          (получение I-ой перестановки целых чисел 1,2,..N-1)

T(p),COST(T(p))    Строим тур T(P) and Вычисляем стоимость COST(T(P))

if COST(T(P)) < MIN then

TOUR←T(p),

MIN←COST(T(P))

fi

od

Попробуем оценить сложность данного алгоритма. Алгоритм является факториальным, с оценкой O(n!). В задаче требуется найти (N – 1)! перестановок целых чисел. Если даже требуется только один шаг для каждой перестановки, то эта часть алгоритма потребует O[(n - 1)!] шагов, поэтому любая верхняя граница для общего времени работы должна быть O(n!). Построим таблицу, иллюстрирующую вычислительную сложность алгоритма, предполагая, что производительность компьютера 1GFLOPS (1000000000 op/s).

Кол-во городов, N               Кол-во туров                        T,с                   T,дн                T,лет

2                                             2                      2e-08               << 1               << 1

3                                             6                      6e-08               << 1               <<1

4                                             24                    2e-07               << 1               << 1

10                                           4e+06              4e-02               << 1               << 1

15                                           13e+12            1e+04              0.15                << 1

18                                           6e+15              6e+07              740                 20

19                                           1e+17              1e+09              14000              390

20                                           2e+18              2e+10              280000            770