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

 

 

^{2. АлГОРИТМЫ ОБРАБОТКИ ДАННЫХ}

 

 

 

 

 

 

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

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

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

• постоянные - сложность не зависит от n: 0(1);
• линейные - сложность 0(n);
• полиномиальные - сложность O(n^m), где m - константа;

 

• экспоненциальные - сложность 0(t^ⁿ⁾), где t - константа, которая больше 1, а f(n) - полиномиальная функция;
• суперполиномиальные - сложность 0(е^^я)), где с - константа, а fn) -функция возрастающая быстрее постоянной, но медленнее линейной;

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

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

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

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

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

78

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 лет.

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

2.2. Методы разработки алгоритмов

 

2.2.1. Метод декомпозиции

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

Проиллюстрируем этот метод на хорошо известном примере (рис. 23). Так, имеются три стержня A, B и C. Вначале на стержень A нанизаны несколько дисков: диск наибольшего диаметра находится внизу, а выше - диски последовательно уменьшающегося диаметра. Цель головоломки - перемещать диски (по одному) со стержня на стержень так, чтобы диск большего диаметра никогда не размещался выше диска меньшего диаметра и чтобы в конце концов все диски оказались нанизанными на стержень B. Стержень C можно использовать для временного хранения дисков.

Рис. 23. Головоломка «Ханойские башни»

Задачу перемещения n наименьших дисков со стержня A на стержень B можно представить себе состоящей из двух подзадач размера n - 1. Сначала нужно переместить n - 1 наименьших дисков со стержня A на стержень C, оставив на стержне A n-й наибольший диск. Затем этот диск нужно переместить с A на B. Потом следует переместить n - 1 дисков со стержня C на стержень B. Это перемещение n - 1 дисков выполняется путем рекурсивного применения указанного метода. Поскольку диски, участвующие в перемещениях, по размеру меньше тех, которые в перемещении не участвуют, не нужно задумываться над тем, что находится под перемещаемыми дисками на стержнях A, B или C. Хотя фактическое перемещение отдельных дисков не столь очевидно, а моделирование вручную выполнить непросто из-за образования стеков рекурсивных вызовов, с концептуальной точки зрения этот алгоритм все же довольно прост для понимания и доказательства его правильности (а если говорить о быстроте разработки, то ему вообще нет равных). Именно легкость разработки алгоритмов по методу декомпозиции обусловила огромную популярность этого метода; к тому же во многих случаях эти алгоритмы оказываются более эффективными, чем алгоритмы, разработанные традиционными методами.

2.2.2. Динамическое программирование

Этот метод имеет под собой достаточно серьезную научную основу, однако его суть вполне можно объяснить на простом примере чисел Фибоначчи.

Вычислить N чисел в последовательности Фибоначчи: 1, 1, 2, 3, 5, 8, ... , где первые два члена равны единице, а все остальные представляют собой сумму двух предыдущих, N меньше 100.

Самый очевидный способ «решения» задачи состоит в написании рекурсивной функции примерно следующего вида:

function F(X:  integer):  longint; begin

if  (X = 1)  or  (X = 2)  then F := 1

else F := F(X-1)  + F(X-2)

end;

При этом на шестом-седьмом десятке программе перестанет хватать временных ресурсов самой современной вычислительной машины. Это происходит по следующим причинам.

Для вычисления, например, F(40) вначале вычисляется F(39) и F(38) . Причем F(38) вычисляется заново, без использования значения, которое было вычислено, когда считалось F(39), т. е. значение функции при одном и том же значении аргумента считается много раз. Если исключить повторный счет, то функция станет заметно эффективней. Для этого приходится завести массив, в котором хранятся значения нашей функции:

var D: array[1..100]  of longint;

Сначала массив заполняется значениями, которые заведомо не могут быть значениями функции (чаще всего, это «-1», но вполне пригоден 0). При попытке вычислить какое-то значение, программа смотрит, не вычислялось ли оно ранее, и если да, то берет готовый результат.

Функция принимает следующий вид:

function F(X:  integer):  longint; begin

if D[X] = 0 then if (X=1) or (X=2) then D[X] := 1

else D[X] := F(X-1) + F(X-2);

F := D[X]; end;

Этот подход динамического программирования называется подходом «сверху вниз». Он запоминает решенные задачи, но очередность решения задач все равно контролирует рекурсия.

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

D[1] := 1; D[2] := 1;

For i := 3 to N do

D[i] := D[i-1] + D[i-2];

Здесь использован подход «снизу вверх». Чаще всего, такой способ раза в три быстрее. Однако в ряде случаев такой метод приводит к необходимости решать большее количество подзадач, чем при рекурсии.

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

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

2.2.3. Поиск с возвратом

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

Рассмотрим игры двух лиц, которые обычно описываются множеством «позиций» и совокупностью правил перехода из одной позиции в другую, причем предполагается, что игроки ходят по очереди. Будем считать, что правилами разрешены лишь конечные последовательности позиций и что в каждой позиции имеется лишь конечное число разрешенных ходов (рис. 24). Тогда для каждой позиции p найдется число N(p) такое, что никакая игра, начавшаяся в p, не может продолжаться более N(p) ходов.

Терминальными называются позиции, из которых нет разрешенных ходов. На каждой из них определена целочисленная функция f(p), зада-

 

ющая выигрыш того из игроков, которому принадлежит ход в этой позиции; выигрыш второго игрока считается равным -f(p).

Если из позицииp имеется d разрешенных ходовp_x, p_d, возникает проблема выбора лучшего из них. Будем называть ход наилучшим, если по окончании игры он приносит наибольший возможный выигрыш при условии, что противник выбирает ходы, наилучшие для него (в том же смысле). Пусть fp) есть наибольший выигрыш, достижимый в позиции p игроком, которому принадлежит очередь хода, против оптимальной защиты. Так как после хода в позицию p выигрыш этого игрока равен -fp), имеем

_{/ (p) = I^{f w d}= ^{0 ,}}

^{[ max {-f(pi),...,- f(p_d)}, если   d>}

Эта формула позволяет индуктивно определить f(p) для каждой позиции p.

 

Функция fp) равна тому максимуму, который гарантирован, если оба игрока действуют оптимально. Следует, однако, заметить, что она отражает результаты весьма осторожной стратегии, которая не обязательно хороша против плохих игроков или игроков, действующих согласно другому принципу оптимальности. Пусть, например, имеются два хода в позиции p и p₂, причем p гарантирует ничью (выигрыш 0) и не дает возможности выиграть, в то время как p₂ дает возможность выиграть, если противник просмотрит очень тонкий выигрывающий ход. В такой ситуации можно предпочесть рискованный ход в p₂, если только нет уверенности в том, что противник всемогущ и всезнающ. Очень возможно, что люди выигрывают у шахматных программ таким именно образом.

Нижеследующий алгоритм, называемый поиском с возвратом, вычисляет f(p).

function BackSearch(p: position):  integer; {оценивает и возвращает выигрыш f(p)  для позиции p} var

m,i,t,d:  integer;

begin

Определить позиции p₁,...,p_d, подчиненные p; if d = 0 then BackSearch := f(p)

else begin m :=

for i:= 1 to d do begin

t := - BackSearch(p_±);

if t > m then m:= t; end;

BackSearch := m; end; end;

Здесь обозначает число, которое не меньше abs(f(p)) для любой терминальной позиции p; поэтому -°° не большеfp) и -f(p) для всех p. Этот алгоритм вычисляет fp) на основе «грубой силы» - для каждой позиции он оценивает все возможные продолжения.

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

Проблема для наиболее интересных игр состоит в том, что размер этого дерева является чрезвычайно огромным, порядка W^L, где W - сред-84 нее количество ходов в позиции, а L - количество уровней дерева. Перебор всего дерева невозможен, главным образом из-за недостатка времени, даже на самых быстрых вычислительных машинах. Все практические алгоритмы поиска являются некоторыми приближениями полного перебора.

2.2.4. Метод ветвей и границ

Перебор, который осуществляет поиск с возвратом, можно уменьшить, используя идею метода «ветвей и границ». Эта идея состоит в том, что можно не искать точную оценку хода, про который стало известно, что он не может быть лучше, чем один из ходов, рассмотренных ранее. Пусть, например, в процессе перебора стало известно, что Xp₁) = -10. Отсюда заключаем, чтоf(p) > 10, и потому не нужно знать точное значениеf(p2), если каким-либо образом узнали, что f(p2) > -10 (поскольку отсюда следует, что -fp₂) < 10). Итак, если ^₂₁ допустимый ход из p₂ и Xp₂₁) < 10, можно не исследовать другие ходы из p₂. Говорят, что ход в позицию p «опровергается» (ходом в ^), если у противника в позиции p есть ответ, по крайней мере, столь же хороший, как его лучший ответ в позиции p_x. Ясно, что если ход можно опровергнуть, можно не искать наилучшее опровержение.

Эти рассуждения приводят к методу «ветвей и границ», гораздо более экономному, чем поиск с возвратом. Определим метод «ветвей и границ» как процедуру с двумя параметрами p и bound, вычисляющую f(p, bound). Цель алгоритма - удовлетворить следующим условиям:

f(p, bound) = f(p), если f(p) < bound,

f(p, bound) > bound, если f(p) > bound.

Идею метода ветвей и границ реализует следующий алгоритм.

Function B&B(p: position, bound:  integer):  integer; {оценивает и возвращает выигрыш F'(p)  для позиции p} label done; var

m,I,t,d:  integer; begin

Определить позиции p₁,~,p_d, подчиненные p; if d = 0 then B&B := f(p)  else begin m := -00;

for i:= 1 to d do begin

t := - B&B(p.,  -m); if t > m then m := t; if m >= bound then goto done; end;

done: B&B := m; end; end;

2.2.5. Метод альфа-бета отсечения

Метод «ветвей и границ» можно еще улучшить, если ввести не только верхнюю, но и нижнюю границу. Эта идея - ее называют минимаксной альфа-бета процедурой или просто альфа-бета отсечением - является значительным продвижением по сравнению с односторонним методом «ветвей и границ». Определим процедуру f с тремя параметрами p, alpha и beta (причем всегда будет выполнено alpha < beta), которая удовлетворяет следующим условиям:

f(p, alpha, beta) < alpha, если f(p) < alpha,

f(p, alpha, beta) = f(p), если alpha < f(p) < beta,

f(p, alpha, beta) > beta, если f(p) > beta.