Классификация задач по степени сложности

В предыдущей главе мы убедились, что для решения задачи об эйлеровом цикле имеется прекрасный линейный алгоритм — его сложность O(m), т.е. линейно зависит от числа ребер.

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

Эту задачу изучал ГАМИЛЬТОН, и в честь него она получила название задачи Гамильтона.

Рисунок 8.25

Многие математики в течение нескольких веков занимались задачей Гамильтона.

До сих пор неизвестно ни одного простого необходимого и достаточного условия существования гамильтонова цикла, и до сих пор не построен алгоритм, который проверял бы существование гамильтонова цикла в произвольном графе за ПОЛИНОМИАЛЬНОЕ число шагов (число, ограниченное многочленом фиксированной степени от числа вершин графа).

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

Основное различие между МАТЕМАТИКОЙ и ИНФОРМАТИКОЙ заключается в том, что в информатике недостаточно иметь доказательство существования объекта, недостаточно найти конструктивное доказательство этого факта, т.е. АЛГОРИТМ. Мы должны учитывать противоречия пространства и времени, которые навязывает нам мир: необходимо, чтобы решение можно было вычислить, используя объем памяти и время, приемлемое для человека или машины.

Идеальный случай, когда для решения задачи известна явная математическая формула. Тогда сложность задачи не зависит от входных данных и является постоянной.

Если же мы не располагаем ни явной формулой, ни рекурсивным выражением приемлемой сложности, нам остается только два способа:

ü построение эффективного алгоритма;

ü метод перебора всех возможностей.

Сложность ЗАДАЧИ — сложность НАИЛУЧШЕГО алгоритма, известного для ее решения.

Сложность АЛГОРИТМА — число шагов, необходимых для решения НАИХУДШЕГО из всех возможных случаев, допускающих применение алгоритма.

Это число выражается как функция от РАЗМЕРНОСТИ входных данных задачи — например, числа вершин графа.

Сразу возникает вопрос — если сложность задачи зависит от нашего знания «хороших» алгоритмов, до какого предела можно улучшать данный алгоритм?

Существуют ли методы перевода задачи из класса «сложных» в класс «простых»?

ТРИ КЛАССА ЗАДАЧ

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

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

О(n m), O(n²), O(n³) и т.д.

Все до сих пор изученные нами алгоритмы относятся к КЛАССУ Р ПОЛИНОМИАЛЬНЫХ АЛГОРИТМОВ.

Есть задачи, которые по своей природе имеют экспоненциальную сложность порядка Aⁿ, где A — константа или полином от n.

Это задачи, в которых требуется построить все подмножества данного множества, все клики (полные подграфы) данного графа и т.д. Число ответов в этих задачах уже само по себе экспоненциально, поэтому только их перечисление потребует экспоненциальное число шагов.

КЛАСС Е: ЭКСПОНЕНЦИАЛЬНЫЕ ЗАДАЧИ.

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

Вот неполный список таких задач. (В приложении 1 содержатся точные математические постановки 25 различных задач.)

ü Решение систем уравнений в целых числах.

ü Определение гамильтонова цикла.

ü Составление расписаний и раскрасок.

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

ü Оптимизация пути коммивояжера через сеть городов.

ü Отбор файлов при запросе в информационный банк данных для получения информации с наименьшей стоимостью.

ü Размещение обслуживающих центров для максимального числа клиентов при минимальном числе центров.

ü Оптимальная загрузка емкости, оптимальный раскрой.

ü Диагностика (болезни, поломки).

Этот список далеко не полон, т.к. большая часть современных задач относится к этому классу. Кроме того, названные задачи являются МОДЕЛЬНЫМИ. Каждой из них соответствует несколько реальных формулировок:

ü упорядочение операций;

ü размещение персонала;

ü оптимизация перевозок;

ü управление производством;

ü проектирование в области электроники.

Более того, для большинства этих задач (так называемых NP-полных задач) была доказана ЭКВИВАЛЕНТНОСТЬ — если для одной из них удастся найти полиномиальный алгоритм, автоматически будут решены все остальные.

Назовем его КЛАСС NP: недетерминированные полиномиальные задачи.

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

1. Для небольших n экспоненциальный алгоритм часто более эффективен, чем полиномиальный.

2. Для реальных задач с уточненными данными всегда можно построить полиномиальный алгоритм. Единственное, что утверждает теория — не существует единого полиномиального алгоритма для общего случая.

Если все же постановка задачи остается из класса NP, можно поискать для нее приближенный полиномиальный алгоритм.

Алгоритмы с возвратом

Вернемся к задаче существования ГАМИЛЬТОНОВА ПУТИ — пути, проходящего через каждую вершину графа ровно один раз. В предыдущей главе было упомянуто, что для такой задачи не построен полиномиальный алгоритм. Попробуем произвести полный перебор всех возможных путей. n вершин графа можно расположить в n! различных цепочек. Чтобы проверить для каждой цепочки, реализована ли она как гамильтонов путь на графе, необходимо еще n шагов, итого сложность полного перебора nn! шагов.

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

ОБЩАЯ СХЕМА АЛГОРИТМА С ВОЗВРАТОМ.

Пусть решение, которое мы ищем, имеет вид последовательности <X(1), …, X(n)>.

Будем строить его, начиная с пустой последовательности длины 0.

Пусть на каком-то этапе уже построено ЧАСТИЧНОЕ (неполное) решение длины i: < X(1), …, X(i) >.

Попытаемся продолжить это решение еще на один шаг. Для этого нужно отыскать допустимое X(i+1). X(i+1) считается допустимым, если или < X(1), …, X(i+1) > уже является решением, или относительно < X(1), …, X(i+1) > НЕЛЬЗЯ СРАЗУ сказать, что его невозможно расширить до полного решения.

Дальше существует две возможности:

если X(i+1) допустимо, то следующее допустимое X ищется для частичного решения <X(1), …, X(i+1)> (заметим, что допустимость X(i+1) вовсе не означает, что <X(1), …, X(i+1)> можно расширить до полного решения);

если допустимого X(i+1) не существует, то возвращаемся на шаг назад — к частичному решению < X(1), …, X(i-1) > и для него отыскиваем другое X'[i], не совпадающее с предыдущим X(i).

Более точно, пусть для каждого i>0 существует множество A(i), из которого будут выбираться X(i) — претенденты на i–тую координату частичного решения.

Очевидно, множества A(i) должны содержать все X(i), занимающие i-ю координату любого решения. Кроме того, A(i) всегда будут содержать какие-то лишние элементы, не содержащие в i–й координате ни одного решения.

Теперь общая схема алгоритма с возвратом имеет следующий вид:

1 begin

2 k:=1;

3 while k>0 do

4 if существует еще неиспользованый y Î A(k),
являющийся допустимым then

5 begin

6 X(k):=y; {y испсльзован}

7 if <X(1), …, X(k)> является решением then
write (<X(1), …, X(k)>);

8 k:=k+1

9 end

10 else {возврат на предыдущее частичное решение,
все элементы A(k) становятся
неиспользоваными}

11 k:=k-1

12 end.

Если предположить, что все решения имеют длину, меньшую n+1, и все множества A(k) состоят из конечного числа элементов, то этот алгоритм находит ВСЕ решения.

Тот же самый алгоритм можно очень просто записать с помощью рекурсии.

{рекурсивный вариант алгоритма с возвратом}

1 procedure BC(k);

{генерируем все решения, являющиеся продолжением
частичного решения < X(1), …, X(k-1) >, массив Х —
глобальный}

2 begin

3 for y Î A(k) do

4 if y допустим then

5 begin

6 X(k):=y;

7 if <X(1), …, X(k)> — решение then

8 write (<X(1), …, X(k)>);

9 BC(k+1); {генерируем все решения, являющиеся
продолжением частичного решения
< X(1),…,X(k-1), y >}

10 y становится неиспользованным; {возврат на
<X(1), …, X(k-1)>}

11 end {цикл 3 выберет для продолжения < X(1), …,
X(k-1) > следующий y', не равный y}

12 end;

Генерировать все решения можно вызовом ВС(1). Описание алгоритма возврата мы начали с несколько более сложного нерекурсивного варианта, т.к. в рекурсивном варианте «возврат» является частью механизма рекурсии и не появляется в явном виде.

ЗАДАЧА ГАМИЛЬТОНА

Применим теперь алгоритм с возвратом для поиска всех гамильтоновых циклов в графе G=<V,E>. Каждый такой цикл — последовательность различных вершин графа < X(1), …, X(n+1) > и только X(1)=X(n+1)=k, где k — произвольная фиксированная вершина, соседние вершины X(i), X(i+1) соединены ребром.

Тогда A(i) = V (множество всех вершин) для любого i <= n+1;

y — допустима для продолжения <X(1), …, X(i-1)>, если

y Î ЗАПИСЬ[ X(i-1) ] (y соединен ребром с X(i-1)) и

y не использована (y не принадлежит <X(1), …, X(i-1)>)

АЛГОРИТМ. {Нахождение всех гамильтоновых циклов в графе}

Данные: Граф G=<V,E>, представленный списками ЗАПИСЬ[v], v Î V.

Результаты: Печать всех гамильтоновых циклов графа G.

Переменные ЗАПИСЬ, X, DOP — глобальные.

1 procedure GAMI(i);

{генерирование всех гамильтовых циклов, являющихся
продолжением частичного решения <X[1], …, X[i-1]>}

2 begin

3 for y Є ЗАПИСЬ[X[i-1]] do

4 if (i = n+1) AND (y = k) then

5 write(X[1], …, X[n], k)

6 else if DOP[y] then

7 begin

7 X[i]:=y; DOP[y]:=ложь;

8 GAMI(i+1);

9 DOP[y]:=истина;

{все решения, продолжающие < X[1], …, X[i-1], y > уже сгенерированы, выбираем другое y', а y вновь становится неиспользованным}

10 end

11 end;{GAMI}

1 begin {основная программа}

2 for v Є V do DOP[V]:=истина;

3 X[1]:=k; {k — произвольная}

4 DOP[k]:=ложь;

5 GAMI(2);

6 end.

Рисунок 8.26

Сложность этого алгоритма в наихудшем случае растет по экспоненте с ростом n.

Это справедливо и для случая, когда ищется ровно одно решение (если задача не имеет решения, то эта модификация не влияет на ход выполнения алгоритма).

?Вопрос1. Докажите, представив соответствующий «плохой» граф, что число шагов в алгоритме «GAMI» растет экспоненциально с ростом n.

Ответы

Ответ 1. Граф типа «погремушка». Такой граф не содержит ни одного гамильтонова цикла, в то же время все вершины, кроме V₀, соединены и представляют собой клику, т.е. граф, у которого все вершины соединены попарно. Всего различных путей будет n!, а для проверки каждой u_j из них потребуется n шагов, итого n*n!, что растет быстрее экспоненты.

Рисунок 8.27