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

Рассмотрим основные понятия сложности задач.

Задачи условно можно разделить на два класса - легкие и трудные. Задачи, для решения которых требуется выполнить O(n), O(n2), O(n3), ... операций - это легкие задачи (здесь n - параметр сложности исходных данных). Задачи же с оценкой сложности O(2n) и более - сложные. Первую группу задач называют задачами полиномиальной сложности, поскольку их временная сложность ограничивается сверху некоторым полиномом (быть может, очень большой, но конечной степени n). Обозначим множество таких задач Р. Вторую группу называют задачами экспоненциальной сложности, поскольку в общем случае (т. е. для исходных данных, наиболее "неудобных" для любого из алгоритмов, решающих задачу) требуется количество операций, увеличивающееся с ростом n, по крайней мере, экспоненциально. Обозначим множество этих задач ЕХР.

Понятие сведения одной задачи к другой. Положим, у нас есть решающий некоторую задачу алгоритм; можно ли его использовать для решения другой задачи, а если можно, то как?

Задача Q сводится к задаче P за полиномиальное время, если существует детерминированный полиномиальный алгоритм, преобразующий произвольный частный случай задачи Q (частную задачу, полученную подстановкой значений вместо параметров общей задачи Q) в некоторый частный случай задачи P, и второй детерминированный полиномиальный алгоритм, преобразующий решение задачи P в решение задачи Q.

Где проходит граница между классами задач полиномиальной сложности P и экспоненциальной сложности ЕХР? Ответ на этот вопрос, т. е. описание границы (например, задачи с такими-то свойствами входят в класс P, а все остальные входят в класс ЕХР) в настоящее время не известен. Чтобы разведать границу, ввели еще один класс задач - NP. Интуитивно предполагается, что он может оказаться "нарушителем границы". Это класс задач, которые можно решить за полиномиальное время (P), но на машине, более мощной, чем обычная однопроцессорная машина - на недетерминированном (N) вычислителе. Недетерминированный вычислитель исполняет так называемые недетерминированные алгоритмы. Напомним свойство детерминированности: определенность (детерминированность) алгоритма означает, что для каждого шага могут быть по набору исходных для шага данных однозначно вычислены результаты выполнения шага, и эти результаты не зависят ни от каких случайных факторов. Соответственно этому и алгоритм в целом по окончании работы исполнителя выдает вполне определенный результат.

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

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

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

Рассмотрим связь между классами P и NP.

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

Задача, решаемая за полиномиальное время на обычной машине, может быть решена за полиномиальное время и на недетерминированной машине, т. е.

PÍNP

Верно ли обратное (и тогда p=NP) или существуют задачи, решаемые за полиномиальное время на недетерминированной машине, но требующие экспоненциального времени на однопроцессорной машине (тогда p Ì NP, NP\P ¹ Æ)?

В первом случае ничего нового в классификации задач от введения класса NP не получим. Но появляется много надежд. Дело в том, что для некоторых задач из класса NP известны только экспоненциальные алгоритмы для их решения на однопроцессорной машине. Если P = NP, т. е. надежда разработать и полиномиальные алгоритмы.

Но и во втором случае появляется много вопросов. Что собой представляет класс NP? Чем задачи из этого класса отличаются от других задач из ЕХР?

Проблема равенства классов сложности P и NP является одной из важнейших проблем теории алгоритмов.

Предельно упрощённое описаниеклассов P и NP выглядит так: P — это вычислительные задачи, которые легко решаются, а NP — те задачи, решение которых легко проверяется. Примером первого класса задач служит сортировка списка фамилий по алфавиту: очевидно, расположить в нужном порядке даже очень большое число элементов списка несложно. Класс NP включает такие задачи, для которых легко проверить, является ли предлагаемое решение верным. Например, у вас есть код, вы не знаете алгоритма кодирования, но можете легко проверить. является ли какая-либо определённая комбинация правильным кодом...NP-задачи можно сравнить с пазлом, поскольку собрать его трудно, а проверка качества сборки занимает лишь пару секунд.

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

Это и есть образец проблемы NP: легко проверить, будет ли составленная в результате разбивка на 100 аудиторий с именами студентов в них удовлетворять требованиям декана. Но задача по составлению такой разбивки, которая бы действительно устроила декана, практически нерешаема. Общее количество операций, которые нужно произвести, чтобы оптимально заполнить 100 аудиторий студентами, превышает количество атомов в известной части Вселенной. Таким образом, невозможно построить такой суперкомпьютер, который сможет решить проблему "грубой силой" или простым перебором вариантов - всех комбинаций из 100 аудиторий со студентами.

Одна из выдающихся проблем информатики в том, чтобы определить, есть ли такие вопросы, ответы на которые можно быстро проверить, но которые требуют невозможно долгого времени на решение каким-либо непосредственным способом. Проблема P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время и используя полиномиальную память)?.. То есть действительно ли задачу легче проверить, чем решить?..

ЛЕКЦИЯ 10. ПЕРЕБОРНЫЕ АЛГОРИТМЫ

Цель лекции: ознакомиться с алгоритмами Порождение и перебор комбинаторных объектов.
Рассматриваемые вопросы: алгоритмы получения последовательностей,перестановок разбиений, сочетаний.

Порождение и перебор комбинаторных объектов

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

Схема перебора всегда будет одинакова:

- во-первых, надо установить ПОРЯДОК на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);

- во-вторых, научиться переходить от произвольного элемента к HЕПОСРЕДСТВЕHHО СЛЕДУЮЩЕМУ за ним (т.е. для заданного элемента x1 строить такой элемент x2, что x1<x2 и между x1 и x2 нет других элементов).

Hаиболее естественным способом упорядочения составных объектов является ЛЕКСИКОГРАФИЧЕСКИЙ порядок, принятый в любом словаре (сначала сравниваются первые буквы слов, потом вторые и т.д.) - именно его мы и будем чаще всего использовать. А вот процедуру получения следующего элемента придется каждый раз изобретать заново. Пока запишем схему перебора в таком виде:

X:=First;

while X<>Last do Next(X);

где First - первый элемент; Last - последний элемент; Next - процедура получения следующего элемента.

Последовательности

Hапечатать все последовательности длины N из чисел 1,2,...,M.

First = (1,1,...,1) Last = (M,M,...,M)

Всего таких последовательностей будет M^N. Чтобы понять. как должна действовать процедура Next, начнем с примеров.

Пусть N=4,M=3.

Тогда:

Next(1,1,1,1) -> (1,1,1,2) Next(1,1,1,3) -> (1,1,2,1) Next(3,1,3,3) -> (3,2,1,1)

Теперь можно написать общую процедуру Next:

procedure Next;

begin

{найти i: X[i]<M,X[i+1]=M,...,X[N]=M};

X[i]:=X[i]+1;

X[i+1]:=...:=X[N]:=1

end;

Если такого i найти не удается, то следующей последовательности нет - мы добрались до последней (M,M,...,M). Заметим также, что если бы членами последовательности были числа не от 1 до M, а от 0 до M-1, то переход к следующей означал бы прибавление 1 в M-ичной системе счисления.

type Sequence=array [byte] of byte;

var M,N,i:byte;

X:Sequence;

Yes:boolean;

procedure Next(var X:Sequence;var Yes:boolean);

var i:byte;

begin

i:=N;

{поиск i}

while (i>0)and(X[i]=M) do begin X[i]:=1;dec(i) end;

if i>0 then begin inc(X[i]);Yes:=true end

else Yes:=false

end;

begin

write('M,N=');readln(M,N);

for i:=1 to N do X[i]:=1;

repeat

for i:=1 to N do write(X[i]);writeln;

Next(X,Yes)

until not Yes

end.

Перестановки

Hапечатать все перестановки чисел 1..N (то есть последовательности длины N, в которые каждое из чисел 1..N входит ровно по одному разу).

First = (1,2,...,N) Last = (N,N-1,...,1)

Всего таких перестановок будет N!=N*(N-1)*...*2*1. Для составления алгоритма Next зададимся вопросом: в каком случае i-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше i).

Мы должны найти наибольшее i, при котором это так, т.е. такое i, что X[i]<X[i+1]>...>X[N] (если такого i нет, то перестановка последняя). После этого X[i] нужно увеличить минимально возможным способом, т.е. найти среди X[i+1],...,X[N] наименьшее число, большее его. Поменяв X[i] с ним, остается расположить числа с номерами i+1,...,N так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке:

procedure Next;

begin

{найти i: X[i]<X[i+1]>X[i+2]>...>X[N]};

{найти j: X[j]>X[i]>X[j+1]>...>X[N]};

{обменять X[i] и X[j]};

{X[i+1]>X[i+2]>...>X[N]};

{перевернуть X[i+1],X[i+2],...,X[N]};

end;

Разбиения

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

Пример: N=4, разбиения: 1+1+1+1, 2+1+1, 2+2, 3+1, 4.

First = (1,1,...,1) - N единиц Last = (N)

Чтобы разбиения не повторялись, договоримся перечислять слагаемые в невозрастающем порядке. Для составления алгоритма Next зададимся тем же вопросом: в каком случае i-ый член разбиения можно увеличить, не меняя предыдущих?

Во-первых, должно быть X[i-1]>X[i] или i=1. Во-вторых, i должно быть не последним эле ментом (увеличение i надо компенсировать уменьшением следующих). Если такого i нет, то данное разбиение последнее. Увеличив i, все следующие элементы надо взять минимально возможными, т.е. равными единице:

procedure Next;

begin

{найти i: (i<L) and ( (X[i-1]>X[i]) or (i=1) )}

X[i]:=X[i]+1;

{ L:= i + X[i+1]+...+X[L] - 1 }

X[i+1]:=...:=X[L]:=1

end;

Через L мы обозначили количество слагаемых в текущем разбиении (понятно, что 1<=L<=N). Программа будет выглядеть так:

program Razbieniya;

type Razb=array [byte] of byte;

var N,i,L:byte;

X:Razb;

procedure Next(var X:Razb;var L:byte);

var i,j:byte;

s:word;

begin

i:=L-1;s:=X[L];

{поиск i}

while (i>1)and(X[i-1]<=X[i]) do begin s:=s+X[i];dec(i) end;

inc(X[i]);

L:=i+s-1;

for j:=i+1 to L do X[j]:=1

end;

begin

write('N=');readln(N);

L:=N; for i:=1 to L do X[i]:=1;

for i:=1 to L do write(X[i]);writeln;

repeat

Next(X,L);

for i:=1 to L do write(X[i]);writeln

until L=1

end.