Главная | Обратная связь | Поможем написать вашу работу!

Утверждение 2. (Верхние оценки методом сведения).

Если задачу B можно решить за время T(n) и задача A t(n)-сводима к B (A µ_t₍_n₎ B), то A можно решить за время, не превышающее T(n)+ O (t(n)).

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

Пример 5. Задача о выпуклой оболочке – нижняя оценка [5 п.3.2.].

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

Дано множество Q, содержащее n точек на плоскости. Требуется построить их выпуклую оболочку, т.е. полное описание её границы.

Задача сортировки сводима за линейное время к задаче построения выпуклой оболочки, и, следовательно, для нахождения выпуклой оболочки n точек на плоскости требуется время W (nlog(n)).

Продемонстрируем процедуру такого сведения:

§ Пусть заданы n положительных действительных чисел x₁,x₂,... x_n.

§ Поставим в соответствие числу x_i точку (x_i, x_i²). Все эти точки лежат на параболе y=x².

§ Выпуклая оболочка этого множества точек, представленная в стандартном виде, будет состоять из списка точек множества, упорядоченного по значению абсциссы.

§ Один просмотр этого списка позволяет прочитать в нужном порядке значения x_i.

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

Достаточно простой пример, связанный с вычислением степенной функции по модулю некоторого числа .

Пример 6. Даны три натуральных числа и . Необходимо вычислить . Простой алгоритм основывается на соотношении

Программа 6.1.

y:= 1;

FOR i:=1 to n do y:= y * x (mod m)

и имеет сложность O(n). Однако можно существенно улучшить алгоритм, используя двоичное разложение показателя степени. Пусть , где . Тогда

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

Программа 6.2.

y:= 1;

n1:=n;

x1:=x;

WHILE (n1>0) DO

IF n1 mod 2>=0

BEGIN

x1:=x1*x1 % mod m;

n1=n1 div 2

END

ELSE

BEGIN

y:=y*x mod m

n1:=n1-1

END

Временная сложность алгоритма равна O(log n). Величина выигрыша определяется по таблице при условии, что двоичное разложение n имеет k бит

k=56
k=128

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

Большой интерес представляет связанная с предыдущей задача поиска дискретного логарифма:

Пусть нечетное простое число. Известны натуральные и и выполняется соотношение . Найти .

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

Рассмотрим еще один пример [6 гл.8.], который иллюстрирует разные подходы к решению одной и той же задачи. Различные подходы дают различные временные оценки.

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

Например, если входной вектор есть x[0..9] = (31,-41,59,26, -53,58,97,-93,-23,84), то результатом решения задачи является сумма сегмента x[2..6], которая равна 187. Это максимальная сумма среди всех возможных сегментов массива x. Очевидным решением при всех положительных элементах вектора является сумма элементов всего входного вектора, а при всех отрицательных элементах - пустой сегмент с нулевой суммой.

Программа 7.1. Представляется естественной необходимость перебрать все сегменты входного вектора {[i..j]/0≤i≤j<n}. Вопрос о выборе порядка перебора пока отложим, и будем перебирать сегменты в соответствии с приведенным определением.

{1:}	maxsofar:=0;
{2:}	FOR i:=0 TO n-1 DO	n
{3:}	FOR j:=i TO n-1 DO BEGIN	n+(n-1)+...1=n(n+1)/2
	// Считаем сумму элементов сегмента x[i..j]:
{4:}	Sum:=0	n(n+1)/2
{5:}	FOR k:=i TO j DO	(1+...n)+(1+...(n-1))+...(1) =
{6:}	sum:=sum+x[k];
{7:}	maxsofar:=max(maxsofar,sum)	n(n+1)/2
	END

Оценим время работы этой программы:

Оператор в строке {1:} выполняется 1 раз.
Операторы заголовка цикла в строке {2:} выполняются n раз (и столько же раз выполняется оператор - тело этого цикла).
Операторы заголовка цикла в строке {3:} выполняются n-i раз для каждого i-го прохода внешнего цикла, получается n+ (n-1)+...1 раз.
Такое же количество раз выполняется оператор в строке {4:}.
Операторы заголовка цикла в строке {5:} выполняются j-i+1 раз для каждого i,j-го прохода пары (вложенных) внешних циклов, получается (1+...n)+(1+...(n-1))+...(1) раз.
Такое же количество раз выполняется оператор в строке {6:}.
Оператор в строке {7:} выполняется такое же количество раз как и операторы строки {3:}.

В целом время выполнения этой программы:

T(n)=1+n+3n(n-1)/2+2(n³/6+2n²+3n/4)= O (n³)

Фактически в данном конкретном случае (и как правило в большинстве других) нас мало интересует столь тщательный расчет этой функции T(n). Для упрощения расчета асимптотической оценки времени выполнения вполне достаточно использовать основные свойства О-символики [7 п.1.5.]:

Правило сумм. Если T₁(n) и T₂(n) имеют степени роста O (f(n)) и O (g(n)) соответственно, то T₁(n)+T₂(n) имеет степень роста O (max(f(n),g(n))). Из правила сумм в частности следует, что если f(n)≤g(n) для всех n, превышающих некоторое n₀, то O (f(n)+g(n))= O (g(n)).

Если T₁(n) и T₂(n) – время выполнения программных фрагментов P₁ и P₂ соответственно, то T₁(n)+T₂(n) – время последовательного выполнения этих фрагментов. Если P₁ и P₂ связаны оператором if E then P₁ else P₂, то время выполнения такого оператора (сверху) оценивается как T_E(n)+max(T₁(n),T₂(n)), где T_E(n) – время выполнения сравнения E.

Правило произведений. Если T₁(n) и T₂(n) имеют степени роста O (f(n)) и O (g(n)) соответственно, то T₁(n)*T₂(n) имеет степень роста O (f(n)*g(n)). Из правила произведений следует, что O (c*f(n)) эквивалентно O (f(n)), если с – положительная константа.

Общее правило вычисления времени выполнения цикла заключается в суммировании времени выполнения каждой итерации цикла. Но в некоторых случаях достаточно точную оценку можно получить и более простым рассуждением: если T₁(n) – длина цикла, а T₂(n) – время выполнения тела цикла, то T₁(n)*T₂(n) – время выполнения цикла в целом.

Используя эти правила, время выполнения программы 5.1 можно оценить сверху O (n³) на том простом основании, что имеем трехкратный цикл, каждый из которых имеет длину не более n, а тело внутреннего цикла требует времени O (1).

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

А повторность вычислений в строках (4-6) – явная небрежность (или неграмотность), при фиксированном i и возрастающем j сумму элементов сегментов x[i..j] так конечно не считают.

maxsofar:=0;

FOR i:=0 TO n-1 DO BEGIN Sum:=0;

FOR j:=i TO n-1 DO BEGIN

// Довычисляем сумму для сегмента x[i..j]:

sum:=sum+x[j];

maxsofar:=max(maxsofar,sum)

END

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

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

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

Предварительно просчитаем суммы для всех сегментов x[0..j], тогда для сегментов x[i..j] суммы можно будет рассчитывать как разность сумм сегментов x[0..j] и x[0..(i-1)]. Для сохранения результатов предварительной обработки нам потребуется вектор:

cumarr: ARRAY[-1..(n-1)] OF REAL;

cumarr[-1]:=0;

FOR j:=0 TO n-1 DO cumarr[j]:= cumarr[j-1]+x[j];

maxsofar:=0;

FOR i:=0 TO n-1 DO BEGIN

FOR j:=i TO n-1 DO BEGIN

// Рассчитываем сумму для сегмента x[i..j]:

sum:= cumarr[j]- cumarr[i-1];

maxsofar:=max(maxsofar,sum)

END

Аккуратный анализ показывает, что время работы этой программы O (n²), т.е. не лучше чем у предыдущей программы, и явных повторных вычислений не видно.

Может быть, мы получили алгоритм с наилучшим (по порядку) временем? Рассмотрим вопрос о нижней оценке для этой задачи. Казалось бы, необходимость просмотра всех пар значений границ [i..j] дает квадратичную оценку. Но доказать эту необходимость неясно как... можно указать лишь тривиальную нижнюю оценку W (n)=O(n). Она следует из того простого факта, что алгоритм должен обязательно просмотреть каждый элемент входного вектора, иначе именно он может оказаться основой для искомого максимума. Каких-либо вариантов повысить эту нижнюю оценку не видно...

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

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

Рассмотрим следующее сведение исходной задачи к подзадачам - сегмент с максимальной суммой находится:

либо в левой половине исходного вектора,
либо в правой его половине,
либо левый его конец находится в левой половине, а правый его конец - в правой.

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

Рассмотрим параметризированный вариант исходной задачи – найти максимальную сумму по всем сегментам в сегменте x[i..j], и оформим в виде рекурсивной функции maxsofar решение этого варианта исходной задачи. Будем считать, что у нас имеется функция maxsofar3, которая решает третью подзадачу.

Будем считать n степенью двойки, это позволит устранить технические детали, которые отвлекают от основных рассуждений, но не вносят каких-либо важных изменений в наши рассуждения. Тогда решение исходной задачи получим вызовом maxsofar(0,n-1).

FUNCTION maxsofar(i,j:INTEGER):REAL; BEGIN

IF i>j THEN maxsofar:=0 //сегмент пустой

ELSE IF i=j THEN maxsofar:=max(0,x[i])//сегмент одноэлементный

ELSE BEGIN m:=(i+j+1) DIV 2; //находим середину

max1:=maxsofar(i,m-1); //решаем левую подзадачу

max2:=maxsofar(m,j); //решаем правую подзадачу

max3:=maxsofar3(i,j,m); //решаем третью подзадачу

maxsofar:=max(max1,max2,max3)

END END

Теперь рассмотрим третью подзадачу maxsofar3(i,j,m) – найти максимальную сумму по всем сегментам {[l..u]/i≤l<m≤u≤j}.

Эта максимальная сумма равна сумме двух максимальных сумм:

по всем сегментам с правым концом (m-1): {[l..(m-1)]/i≤l<m}
и по всем сегментам с левым концом m: {[m..u]/m≤u≤j}

FUNCTION maxsofar3(i,j,m:INTEGER):REAL; BEGIN

maxL:=0; sum:=0; FOR k:=m-1 DOWNTO i DO

BEGIN sum:=sum+x[k]; maxL:=max(maxL,sum) END;

maxU:=0; sum:=0; FOR k:=m TO j DO

BEGIN sum:=sum+x[k]; maxU:=max(maxU,sum) END;

maxsofar3:= maxL+maxU END

Время работы этой программы T₃(j-i+1)= .

Теперь оценим время работы программы 7.3. Для алгоритмов, основанных на рассуждении сведением к подзадачам, оценка времени работы естественным образом описывается рекуррентными соотношениями. В частности в нашем случае:

T(n)= 2*T(n/2)+T₃(n),

где T(n/2) – время решения для первых двух подзадач (левой и правой), а T₃(n)= O (n) - время решения третьей подзадачи. Вообще-то надо еще добавить константу для вспомогательных действий и сборки общего решения, но можно считать, что это включено в T₃(n). Теперь остается решить это рекуррентное соотношение.

Техника решения подобных рекуррентных соотношений достаточно хорошо разработана. Общую ситуацию (охватывающую наш случай) описывает теорема

Теорема [4 п.4.3.]. Пусть и - константы, - функция, определена при неотрицательных формулой

Где под понимается или или . Положим . Тогда:

1) если для некоторого , то );

2) если , то );

3) если для некоторого и если для некоторой константы и достаточно больших , то ).

Как уже отмечалось разбиение задачи на подзадачи с соответствующим решением подзадач и последующей сборкой из результатов их решения общего решения исходной задачи довольно часто эффективно используемая техника. При этом общее время работы алгоритма обычно складывается из суммы времен решения каждой из подзадач T(з1) и T(з2) и времени на формирование общего результата Т(з1 з2). Как показывает эта теорема, выбором подходящего разбиения на подзадачи с соответствующими параметрами удается минимизировать общее время решения задачи.

Для случая нашей задачи имеем и , согласно пункту 2 получаем . Итого, мы получили алгоритм существенно лучше, чем предыдущие, причем из полученной оценки времени следует очень важное следствие - программа 5.3 решает исходную задачу, но просматривает не все сегменты входного вектора, поскольку общее количество этих сегментов O (n²).

Сейчас видимо было бы полезно проанализировать какие сегменты эта программа не просматривает и на каком основании относит их к бесперспективным. Но мы попытаемся проанализировать возможности исключения сегментов из рассмотрения, опираясь на несколько иное рассуждение. Дело в том, что «разделяй и властвуй» - это один из вариантов рассуждения сведением к подзадачам, при котором исходная задача сводится к двум (или нескольким) подзадачам и сборке общего решения, при этом исходная задача разбивается на две такие же, но примерно половинного размера. Сбалансированное разбиение обычно и дает хороший эффект по времени.

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

Программа 5.4. Воспользуемся рассуждением методом последовательных уточнений:

§ Пусть (префиксная) часть вектора x[0..j] уже обработана, и мы имеем maxsofar - максимальную сумму по всем сегментам этой части вектора (т.е. пока мы видим только эту префиксную часть вектора до j-го его элемента).

§ Теперь нам надо уточнить имеющееся решение до решения нашей задачи для части вектора x[0..(j+1)](т.е. теперь видим на один элемент дальше).

Сегмент с максимальной суммой либо полностью лежит в x[0..j] и тогда maxsofar – решение и для расширенного префикса вектора, либо (j+1) – правый конец этого сегмента, а значит надо рассмотреть все сегменты {[z..(j+1)]/0≤z≤(j+1)}. Кстати, такую подзадачу «по всем сегментам с фиксированным правым концом» мы уже рассматривали в предыдущей программе, но время для неё O (j+2), а в целом для такого алгоритма тогда мы получим O (n²).

Но более важным для нас является следующее наблюдение:

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

§ Но если уже вычислена MaxEndingHere – максимальная сумма по всем сегментам с правым концом j, то не представляет труда уточнить значение этой переменной по всем сегментам с правым концом (j+1) – это просто max(MaxEndingHere+x[j+1],0).

Фактически для уточнения значения maxsofar на расширенный префикс x[0..(j+1)] нам нужна была именно MaxEndingHere, а значит необходимость просматривать сегменты с правым концом (j+1) просто совсем отпала...

maxsofar:=0; MaxEndingHere:=0;

FOR j:=0 TO n-1 DO BEGIN

// Пересчитаем максимальную сумму для сегментов с концом j:

MaxEndingHere:=max(MaxEndingHere+x[j],0);

// Пересчитаем максимальную сумму

// для всех сегментов в x[0..j]:

maxsofar:=max(maxsofar,MaxEndingHere)

END

Время работы этой программы Q (n).

Задача эта (в двумерном варианте) возникла в рамках работ по распознаванию образов, при этом сегмент с максимальной суммой элементов отражает наибольшее соответствие между двумя цифровыми изображениями. Первая программа требует ориентировочно 15 дней на решение задачи с характерным размером 100000 элементов, тогда как последний вариант программы решает ту же задачу за 5 миллисекунд. И увеличение скорости компьютера даже в 100 раз не вносит ничего существенного в эту ситуацию с учетом того, что такую задачу приходится решать многократно в рамках реальной задачи распознавания образов.

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

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

§ В определении асимптотической оценки фигурируют две константы ($c>0 $n₀...). Если программа будет работать только с «малыми» входными данными, то степень роста времени выполнения (которая проявляется только для больших n>n₀) может иметь меньшее значение, чем мультипликативная константа (c), присутствующая в формуле времени выполнения. Например, известен алгоритм целочисленного умножения, асимптотически самый эффективный, но он не используется на практике даже для больших задач, потому что его константа пропорциональности значительно превосходит подобные константы других, менее «эффективных» алгоритмов.

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

§ В численных алгоритмах точность и устойчивость не менее важны, чем их временная эффективность.

§ Широко распространенное на практике семейство задач – обработка входного потока в префиксном режиме: на вход поступает последовательность, а программа должна выдавать результат для каждого текущего элемента до начала поступления очередного. Если известны ограничения на скорость поступления элементов входного потока, то естественно нет достаточных оснований заниматься разработкой программы, позволяющей обрабатывать такой входной поток со скоростью, во много раз превосходящей скорость поступления элементов на входе.

Труднорешаемые задачи и NP-полнота. [8, 4 гл.34.]

Различные задачи и алгоритмы их решения имеют различную временную сложность, и выяснение того, какие алгоритмы «достаточно эффективны», а какие «совершенно неэффективны», всегда будет зависеть от конкретной ситуации. Но возникает вопрос: Когда нужно считать, что задача действительно труднорешаема? В теории принято эту границу проводить между полиномиальными и экспоненциальными алгоритмами.

Полиномиальным алгоритмом (или алгоритмом полиномиальной временной сложности) называется алгоритм, у которого временная сложность равна O (p(n)), где p(n) – некоторая полиномиальная функция. Алгоритмы, временная сложность которых не поддается подобной оценке, называют «экспоненциальными».

Различие между двумя указанными типами алгоритмов становятся особенно существенными при решении задач большого размера, и проявляются еще более убедительно, если проанализировать влияние увеличения быстродействия ЭВМ на время работы алгоритмов. Например, для T(n)=2ⁿ увеличение скорости вычислений в 10 раз приводит лишь к тому, что размер наибольшей задачи, разрешимой за один час, возрастет только (ориентировочно) на 3,3, в то время как для T(n)= этот размер возрастет почти в 3,16 раза (ориентировочно).

Эффект десятикратного ускорения при последующем увеличении скорости вычислений.

Большинство экспоненциальных алгоритмов – это просто варианты полного перебора, в то время как полиномиальные алгоритмы обычно можно построить лишь тогда, когда удается более глубоко проникнуть в суть решаемой задачи. Имеется широко распространенное соглашение, согласно которому задача не считается «хорошо решаемой» до тех пор, пока для неё не получен полиномиальный алгоритм. Поэтому задачу принято называть труднорешаемой, если для её решения не существует полиномиального алгоритма.

Здесь надо зафиксировать несколько уточнений:

§ Временная сложность в этих рассуждениях разумеется как мера поведения алгоритма в худшем случае.

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

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

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

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

В связи с вышесказанным сделаем некоторые уточнения. Введем понятие абстрактной задачи: Определим абстрактную задачу (abstract problem) Q как бинарное отношение между множеством экземпляров (instances) задачи и множеством S решений (solutions). Например, экземпляр задачи Кратчайший путь состоит из трех элементов: графа и двух вершин. Решением этой задачи является минимальная по длине последовательность ребер графа между заданными вершинами; при этом пустая последовательность понимается как отсутствие такого пути. Сама задача Кратчайший путь представляет собой отношение, сопоставляющее каждому экземпляру графа и двум его вершинам кратчайший путь по графу, соединяющий эти две вершины. Поскольку кратчайший путь может быть не единственным, конкретный экземпляр задачи может иметь несколько решений.

Поскольку как было заявлено выше, число решений может быть может быть достаточно велико, а нас интересует максимальная по всем экземплярам сложность решения, мы будем рассматривать только задачи распознавания (decision problems), т.е. задачи, которые имеют только два возможных ответа – «да» или «нет». Обычно для кандидатов в труднорешаемые задачи естественным образом формулируются соответствующие задачи распознавания, которые решаются не труднее, но остаются при этом кандидатами в труднорешаемые. Например, задачу распознавания Путь, соответствующую задаче Кратчайший путь, может быть сформулирована следующим образом: Пусть — экземпляр задачи принятия решения Путь. Тогда равенство Путь (i) = 1 (да) выполняется, если количество ребер в кратчайшем пути из вершины в вершину не превышает ; в противном случае Путь (i) = 0 (нет). Ограничившись задачами распознавания, мы избавимся в постановках задач от многообразных вариантов типа вышерассмотренного и сконцентрируем внимание на наиболее существенных аспектах труднорешаемости.

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

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

Поиск самых коротких и самых длинных простых путей в графе. В дальнейшем мы убедимся, что поиск кратчайшего пути от некоторой вершины отдельно взятого источника в ориентированном графе G = (V, Е) можно найти в течение времени O(VE). Однако поиск самого длинного пути между двумя вершинами оказывается сложным. Задача по определению того, содержит ли граф простой путь, количество ребер в котором не меньше заданного числа, является труднорешаемой.

Эйлеров и Гамильтонов циклы. Эйлеров цикл (Euler tour) связанного ориентированного графа G = (У, Е) — это цикл, в котором переход по каждому ребру G осуществляется ровно один раз, хотя допускается неоднократное посещение некоторых вершин. Определить наличие Эйлерова цикла (а также найти составляющие его ребра) можно в течение времени О (Е). Гамильтонов цикл (hamiltonian cycle) ориентированного графа G = (V, Е) — это простой цикл, содержащий все вершины из множества V. Задача по определению того, содержится ли в ориентированном графе Гамильтонов цикл, является труднорешаемой.

2-CNF- и З- CNF-выполнимость. Булева формула содержит переменные, принимающие значения 0 и 1, булевы операторы, такие как & (И), V (ИЛИ) и (НЕ), а также скобки. Булева формула называется выполнимой (satisfiable), если входящим в ее состав переменным можно присвоить такие значения 0 и 1, чтобы в результате вычисления формулы получилось значение 1. Булева формула представлена в к-конъюнктивной нормальной форме (fc-conjunctive normal form), или fc-CNF, если она имеет вид конъюнкции (И) взятых в скобки выражений, являющихся дизъюнкцией (ИЛИ) ровно к переменных или их отрицаний (НЕ). Например, формула представлена в 2-CNF. (Для нее существует выполнимый набор ) Можно сформулировать алгоритм с полиномиальным временем работы, позволяющий определить, является ли 2-CNF формула выполнимой. Однако, определение того, является ли 3-CNF формула выполнимой — это труднорешаемая задача задача.

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

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

1. Это преобразование занимает полиномиальное время.

2. Ответы являются идентичными, т.е. в экземпляре ответ "да" выдается тогда и только тогда, когда в экземпляре тоже выдается ответ "да".

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

1. Заданный экземпляр задачи А с помощью алгоритма сведения с полиномиальным временем преобразуется в экземпляр задачи В.

2. Запускается алгоритм, решающий экземпляр задачи принятия решения задачи В в течение полиномиального времени.

3. Ответ для экземпляра используется в качестве ответа для экземпляра .

Поскольку для выполнения каждого из перечисленных выше этапов требуется полиномиальное время, это относится и ко всему процессу в целом, что дает способ решения экземпляра задачи в течение полиномиального времени. Другими словами, путем сведения задачи А к задаче В "простота" задачи В используется для доказательства "простоты" задачи А.

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

Именно эта (недетерминированная) «нереалистичная» модель вычислителя играет важную роль в постановке проблемы об NP-полноте. В дальнейшем нас будут интересовать труднорешаемые задачи, для которых имеется полиномиальный алгоритм решения, но для недетерминированного вычислителя (для которого надо ещё определить понятие – время работы).

Классическая модель недетерминированного вычислителя - это недетерминированная машина Тьюринга. Для программистов видимо более удобной является модель недетерминированной RAM-машины или можно воспользоваться любым процедурным языком программирования – убрать всё лишнее (что загромождает рассуждения, но не дает ничего нового с учетом полиномиальной сводимости), но добавить:

§ Оператор недетерминированного выбора: V ^boolean:=?

Этот оператор устанавливает значение логической переменной V, важный деликатный вопрос – как? Он может установить значение либо true, либо false, но не в вероятностном смысле, а в смысле альтернативных вариантов срабатывания. Можно рассмотреть вариант работы программы, когда при текущем выполнении он установит значение true, но можно рассмотреть альтернативный вариант работы программы, когда при текущем выполнении он установит значение false, и при каждом повторном выполнении он может альтернативно поступить независимо от предыдущих вариантов срабатывания.

§ Оператор «успех» – приводит к успешному завершению работы программы.

§ Оператор «неудача» – тоже приводит завершению работы программы, но неудачному.

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

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

Рассмотрим пример переборного решения задачи «Коммивояжер». В условии даны: множество городов, расстояния между ними и число В. Спрашивается: существует ли проходящий через все города маршрут длины, не превосходящей В. Полиномиальный детерминированный алгоритм решения этой задачи не известен, но можно предложить следующий полиномиальный недетерминированный алгоритм:

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

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

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

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

Имеется еще одно важное отличие «решения» задачи распознавания недетерминированным алгоритмом от решения детерминированным алгоритмом, а именно в первом случае отсутствует симметрия между ответами «да» и «нет».

Если задача: «Дано I; верно ли, что для I выполняется свойство X?» может быть решена полиномиальным (детерминированным) алгоритмом, то такое же утверждение справедливо и для дополнительной задачи; "Дано I, верно ли, что для I не выполняется свойство X?». Это следует из того, что детерминированный алгоритм останавливается при всех входах, поэтому достаточно поменять местами ответы «да» и «нет».

Совершенно не очевидно, что то же самое верно для всех задач, разрешимых за полиномиальное время недетерминированными алгоритмами. Например, дополнение задачи «Коммивояжер»: дано множество городов, расстояния между ними и граница В; верно ли, что нет маршрута, проходящего через все города и имеющего длину, не превосходящую В? Для выяснения, имеет ли поставленный вопрос ответ «да», не известен способ, который был бы короче, чем проверка всех (или почти всех) возможных маршрутов. Несмотря на интенсивные исследования в этой области, никому не удалось установить, замкнут ли класс NP относительно операции дополнения. Другими словами, следует ли из соотношения соотношение ? Можно определить класс сложности co-NP (complexity class co-NP) как множество языков L, для которых выполняется соотношение . Вопрос о том, замкнут ли класс NP относительно дополнения, можно перефразировать как вопрос о соблюдении равенства NP = coNP. Поскольку класс Р замкнут относительно дополнения, отсюда следует, что . Однако, опять же не известно, выполняется ли равенство , т.е. существует ли хоть один язык в множестве .

На рис. представлены четыре возможные ситуации. На каждой диаграмме одна область, содержащая другую, указывает, что внутренняя область является собственным подмножеством внешней. В части а) рисунка показана ситуация, соответствующая равенству Р = NP = co-NP.

Большинство исследователей считает этот сценарий наименее вероятным. В части б) показано, что если класс NP замкнут относительно дополнения (NP=coNP), не обязательно справедливо равенство Р = NP. В части в изображена ситуация, когда Р = NP co-NP, но класс NP не замкнут относительно дополнения. И наконец, в части г выполняются соотношения NP co-NP и Р NP co-NP. Большинство исследователей считают эту ситуацию наиболее вероятной.

Класс P (полиномиальных задач распознавания) – множество задач распознавания, для которых существует полиномиальный детерминированный алгоритм решения.

Класс NP (недетерминировано полиномиальных задач распознавания) – множество задач распознавания, для которых существует полиномиальный недетерминированный алгоритм решения.

Очевидно включение P Í NP, поскольку детерминированный алгоритм по определению является недетерминированным. Но есть много причин считать это включение строгим. Полиномиальные недетерминированные алгоритмы определенно оказываются более мощными, чем полиномиальные детерминированные, и не известны общие методы их превращения в детерминированные полиномиальные.

Если P не совпадает с NP, то различие между P и NP-P очень существенно. Все задачи из P могут быть решены (детерминированными) полиномиальными алгоритмами, а все задачи из NP-P труднорешаемы, и математическим уточнением понятия переборная задача распознавания служит задача из NP-P.

В исследованиях проблемы P ¹ NP важное положение занимает понятие полиномиальная сводимость, используя ранее введенное понятие (и обозначение) сводимости - задача A полиномиально сводима к задаче B, если A µ_p₍_n₎ B для некоторого полинома p(n). Задача A называется NP-полной, если A Î NP и для любой другой задачи B Î NP имеет место полиномиальная сводимость B к A.

Честь быть «первой» NP-полной задачей выпала на долю задачи распознавания выполнимости формул булевой логики. Рассмотрим язык L, образованный всеми цепочками, представляющими выполнимые булевы формулы (т. е. формулы, принимающие значение 1 на некотором наборе 0-1-значений переменных). Мы утверждаем, что L принадлежит NP. Недетерминированный алгоритм, распознающий L, начинает с того, что "угадывает" выполняющий набор 0-1-значений пропозициональных переменных во входной цепочке, если такой набор существует. Затем угаданное значение 0 или 1 каждой переменной подставляется вместо всех вхождений этой переменной во входную цепочку. Далее вычисляется значение полученного выражения, чтобы проверить его совпадение с 1. Это вычисление осуществляется за время, пропорциональное длине выражения, многими алгоритмами синтаксического анализа. Но даже и без них не трудно вычислить значение булевой формулы за шагов. Следовательно, некоторая недетерминированная машина Тьюринга допускает выполнимые булевы формулы с полиномиальной временной сложностью, и потому задача распознавания выполнимости булевых формул принадлежит NP. Снова отметим, что недетерминизм пригодился, чтобы "параллелизовать" задачу, поскольку "угадывание" правильного решения в действительности означает параллельную проверку всех возможных решений.

Кук С.А. показал как формулами булевой логики можно описать работу любой программы недетерминированного вычислителя и на этой основе доказал полиномиальную сводимость любой NP-задачи к задаче о выполнимости.

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

Если речь идет о NP-полноте, то здесь нельзя предположить, что для задачи А вообще не существует алгоритмов с полиномиальным временем работы. Однако методология аналогична в том отношении, что доказательство NP-полноты задачи В основывается на предположении о NP-полноте задачи А.

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

k-кликой в графе G называют k-узельный полный подграф (каждая пара различных узлов в этом подграфе соединена ребром) графа G. Задача о клике формулируется так: содержит ли данный граф G -клику, где k — данное целое число?

Пример задачи о клике для графа G на рис. при k=3 можно закодировать цепочкой

3 (1,2) (1,4) (2,3) (2,4) (3,4) (3,5) (4, 5). Первое число представляет значение k. За ним идут пары узлов, соединенных ребрами, причем узел представлен числом i. Таким образом, ребра в порядке перечисления выглядят так: .

Задача о клике принадлежит классу NP. Недетерминированная машина Тьюринга сначала может "догадаться", какие k узлов составляют полный подграф, а затем проверить, что любая пара этих узлов соединена ребром, при этом для проверки достаточно шагов, где — длина кода задачи о клике.

Для изучения важных NP-полных задач, касающихся неориентированных графов, нам понадобятся следующие определения.

Определения. Пусть G=(V, Е) — неориентированный граф.

1. Узельным покрытием графа G называется такое подмножество , что каждое ребро графа G инцидентно некоторому узлу из S.

2. Гамильтоновым циклом называется цикл в графе G, содержащий все узлы из V.

3. Граф G называется k-раскрашиваемым, если существует такое приписывание целых чисел 1, 2,..., k, называемых цветами, узлам графа G, что никаким двум смежным узлам не приписан один и тот же цвет. Хроматическим числом графа G называется такое наименьшее число k, что граф G -раскрашиваем.

Для представления важных NP-полных задач об ориентированных графах нам понадобятся следующие определения.

Определения. Пусть G—(V, Е) — ориентированный граф.

1. Множеством узлов, разрезающих циклы, называется такое подмножество , что каждый цикл в G содержит узел из S.

2. Множеством ребер, разрезающих циклы, называется такое подмножество , что каждый цикл в G содержит ребро из F.

3. Ориентированным гамильтоновым циклом называется цикл в ориентированном графе G, содержащий все узлы из V.

Теорема 10.2. Следующие задачи принадлежат классу NP

1. (Выполнимость) Выполнима ли данная булева формула?

2. (Клика) Содержит ли данный неориентированный граф k- клику?

3. (Узельное покрытие) Имеет ли данный неориентированный граф узельное покрытие размера k?

4. (Гамильтонов цикл) Имеет ли данный неориентированный граф гамильтонов цикл?

5. (Раскрашиваемость) Является ли данный неориентированный граф k-раскрашиваемым?

6. (Множество узлов, разрезающих циклы) Имеет ли данный ориентированный граф k-элементное множество узлов, разрезающих циклы?

7. (Множество ребер, разрезающих циклы) Имеет ли данный ориентированный граф k-элементное множество ребер, разрезающих циклы?

8. (Ориентированный гамильтонов цикл) Имеет ли данный ориентированный граф ориентированный гамильтонов цикл?

9. (Покрытие множествами) Существует ли для данного семейства множеств такое подсемейство из k множеств , что

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

Теорема. Задача о клике полиномиально трансформируема в задачу об узельном покрытии. Поэтому задача об узельном покрытии NP-полна.

Доказательство. Пусть дан неориентированный граф G - (V, E). Рассмотрим его дополнение , где . Множество является кликой в G тогда и только тогда, когда V\S является узельным покрытием графа . Действительно, если S — клика в G, то никакое ребро в не соединяет никакие два узла в S. Поэтому всякое ребро в инцидентно по меньшей мере одному узлу из V\S, откуда следует, что V\S есть узельное покрытие графа G. Аналогично, если V\S есть узельное покрытие графа , то каждое ребро из инцидентно по меньшей мере одному узлу из V\S. Поэтому никакое ребро из не соединяет два узла из S. Следовательно, каждая пара узлов из S соединена в G, и, значит, S — клика в G.

Чтобы узнать, существует ли -клика, построим граф и выясним, содержит ли он узельное покрытие размера ||V||—k. Разумеется, поданному стандартному представлению графа G=(V, E) и числа k можно найти представление графа и числа ||V||—k за время, полиномиально зависящее от длины представления G и k.

Оригинальные идеи Кука оказались удивительно плодотворными. Они позволили свести много разнообразных вопросов о сложности в единый вопрос: «Верно ли, что NP-полные задачи труднорешаемы?»

⇐ Предыдущая 2 3 4 5 678 9 10 11 Следующая ⇒