Ш.И._Галиев_МЛ_и_ТА_2004
.pdfИзтабл. 12 вилка, чта удлинение быстродействия в 10 раз лист рочмпжностъдля алгоритма.41 увеличить размер входа в 10 раз, а для ингоротма А5 увеличение размера вхпцд практически не произошло. Таким обратом, чем большую временную сложность имеет алгоритм, тем меиыиее улучшение дает увеличение быстридейотвии.
§3, Полиномиальные алгоритмы и задачи. КлассР
миомную временную спокиост, если существует полином р(х) та-
лепия после выполнения не более чемр(п) операций.
Ясно, что алгоритмы А\ и А2, временные сложности которых равны, например, 0 (^ ) и (X^logn), будут счигаться полиномиальны ми. ибо их сложности ограничены полиномами, т.е. имеют порядак не иыше, чем 0(гГ) и ftV) соответственно.
Говорят, 'по задачи рязрешима за палшолтмыюс прет или полиномиально разрешима, еслидля нее существует полиномиальный алгорэтм. При этом считается, что задача является «хорошей».
Множество всех заддч, для каждой из которых существует полиномиальный алгоритм, называется классомР.
Среди полиномиальных алгоритмов быстрыми являются линейные алгоритмы, которые обладают сложностью порядка л, где к - размерность входных данньи. К линейным алгоритмам относится школьный алгоритм нахождения суммы десятичных чисел, каждое из
В класс Р, кроме линейных задач, попадают, нопример, сле дующие задачи.
Умножение целых чисел. Школьный метод умножение двух ч-рязрядных чисел имеет временную сложность поредка 0(я). Существует алгоритм Шенхагс -Штрассена умножения чисел (задан ных в двоичной системе счислении) с- меньшей сложностью, именно
281
СОслоакостыо парадка 0(л logj п log] 1а& л). Подробнее будет иэг.о-
Умножекие матриц. Обычкын метод имеет порядок сложности 0(«J). Существует более быстрый алгоря-uумножения матрицалго ритмILl-грассема12), который имеетсложность порядка 0(л|!*!').
Найти кратчайший путь на графе, состоящем из л вершин и т ребер. Сюжность алгоритма0(«я) (28].
Быстрое преобразование Ф>-рье требует 0(и log; я) арифмети ческих операций [2].
Задача Прима - Крвсвала - Кзли. Даиа п городов. Нужно
кабеля была минимальной. Эта задача решается с ппмощыо жвдного алгоритма сложности Wnlogin) 126].
Нахождение эйлерова цикла is графе с т ребрами. Алгоритм нахождения эйлерова цикла имеет сложность порядка Olm), см., на пример, [22].
Задачи, для которых ие существует полиномиального алго ритма, считаются трудно разрешимыик.
Рассмотрим пример определения сложности вычислений (алго ритма) на примерам.
Требуется найти наибольшийи наименьший элементы иъS. Положим, что каждое одно сравнениедвух любых чисел осуществляется за оди наковоевремя.
Олин га втможных методов отстоит * поиске сначала наибольшего элемента изS, а яатем - наименьшего. Наибольший элемент можно найти, проводя я-1 сравнений, например, rio следующему алго-
МАХ«-произвольныйэлемент из£; for все другее элементых ияS do
ifje>MAXIhcn MAX<-x;
гп CD(I.
В результате н-1 сраниенмй найдется наибольший элемент. Заметим, что не учитывается время на выборку элемента. Далее начи нается поиск наименьшего элемента по аналогичному алгоритму, Вели считать ага процедуры независимыми, то вновь потребуется ч-1 сравнений. В атогс для нахождения наибольшего и наименьшего элеменгов из S потребуется1п-2сравнений
Число необходимых сравнений можно уменьшить, если исполмовпть принцип «]шдел»й и властвуй», который в теории micaритмов называют ещестратегиейдублирования.
Стратегия дублирования состоит » следующем. Пусть размер ■адачи (размер входных данных задачи) равен и. Разобьем задачу иа две подзадачи размера и/2 той же структуры, что н исходим задача. Если решения этих задач можно скомбинировать в решение исходнойзадачи, го получитскэффектавный алгоритм.
Рассмотрим, как стратегия ауЭлирсваннх ддет ускорение для ре шения предыдущая задачи. Положим, чта числа элементов множесгаа-З1 являетсястепеньючисла2,т.е. и“21.ди« некоторогоКtel.
Реализуем рекурсивный поиск, при котором чножество 5 разби вается последовательно надва годмиожесгаа по следующей процеду ре MAXMTR
procedure MAXMIN(.S): 1) if I S1-2 then
2)nyecbS=|cr,i};
3)relur»(MAK(ai),MIN(a,b))
4)разбить S на дваралны» подмножестваS| и Si,
5)(maxi, mmi)«-MAXMIN{iSi);
й) (max2, niin2j'-MAXM[N(i'ij;
7) r*4nm(MAX(ma<l, aiax2J. MINQitinL, min2)) end
Вэтой процедуре сравнения происходят только fa третьем ша-
,где ора.впиваются два элемента множества 5, из которых оно
состоит, и на шаге 7, где срапнипаю/с» mail с тах2 и mini min2. Пусть Tin) - число сравнений элементов множества S. Ясно, >Д2)=1. Если п>2, то Г(ч) - общее число сравиений, произведен-
.IX в двух вызовах прицедуры MAXMIN (строки S и 6), работающих 1множествах размера пИ и еще два сравнения встроке 7.
Таким образом, |
|
если п =2; |
¢7.1) |
Г (" Н 0 |
|
|_2Т(л/2)+ 2, если и >2. |
|
Решением рекурренгных уравнений (7.1) олужиг функции 7Хп)=(3/2)я-2.Таким образом, вместо 2я-2 сравнений получили (3/2)и-2 сравнений чисел, т ена (п/2) сравнений меньше.
Рассмотрим второй пример. Пусть требуется умножить два л разрядныхдвоичных чисел. Притрадиционном (школьном) алгоритме требуется 0(/12) битовых операций. Применим стратегию дублирошь
Счипем, что я есть степень ‘осла 2. Тогда |
|
■jy^(a2"r‘+t)(c2“r‘+<f)--ac2"+(ai/+bc)2"'>+id |
(7.2) |
Равенство (7.2) лает способ вычисления ху с помощью четырех умножений (п/2) разрядных чисел и нескольких сложений и сдвигов (умножений на степень числа 2). Можно нолучоть, fro вместо О(я') битовых операций нужно 0(м1ч,(>,)« 0(и|,я) битовых операций. Здесь число разбивалось на два блока. Разбивая эти числа на большее число блоков, можно получить, *гто умножение дпух чисел имеет сложность 0(/1 bgj« iogi logifl) дла алгоритма Ш&скаге-Штрассена L2].
Абстрактной моделью полиномиального алгоритма является та* называемая детерминирсвпннаи машина Тыоринге. Эта метина в каждый данный момент времени находятся в строго определенном состоянии, за один шаг она совершает одно из некоторого конечного инсж&ства действий. Чатем она переходит а следующее состояние и все начиняется вновь, тюка не придет к ситуации останова.
§< t,№ класс
Наиболее простыми считаются полиномиальные задачи,
Другим, возможно, более широким, «сложностнын классом» является класс ОТ. Эта аббревиатура обозначает выражение «разре шимых на Недетерминированной машине Тьюринга за Полиномиаль ное время». Класс ИР стали впервые изучать Эдмонде, Кук и Кири
Вобычных матннлх Тьюринга (их нялывают детерыикироаанными, чтобы отлнчатъ от недетерминированных) новое состояние,
вкоторое машина переходит на очередном таге, полностью опреде ляется текущим состоянием и тем символом, который обозревает го-
Внедетерминированных машинах Тьюринга для каждого состояния может быть несколько следующих состояний, в соответстеии с функцией перехода. И в кяадом следугсщгч состоянии может запускаться новая копия данной машин-Ы Тьюринга.
Недетерминированность лучше всего понять, рассматривав ал
горитм, который производит пыяислеиия да чек пор, попа нв доходит до места, в котором должен быть сдеиан выбор из нескольких альтер натив. Детерминированный алгоритм исследовал бы сначала одну альтернативу, а потом вернулся для рассмотрения следующей альтер нативы. Недетерминированный алгоритм может исследовать все аль тернативы одновременно, «копируя», в сущности, самого себя для каздой альтернативы. Вс» копии работают независимо, Вели копия
285
обнаруживает, чти данный путь безрезультатный, то
выполняться Если копна находит требуемое решение, add о&ьявляет об этом, и act копни прекращают работать.
Определим NP-ыасс как класс задач, которые можно решить недетерминированными алгоритмами, работающими в течение
Чтобы доказать, тгп некоторая чцлдча принадлежит' классу NP достаточно построить недетерминированный алгоритм (алгоритм недетерминированием машины Тьюринга), который решает эту задачу а* полиномиальное время.
Пусть имеем, например, залдчу выяснения существования в ориентированном графе гамкдьтокового цикла, длина которого
Рассмотрим следующий алгоритм.
v,« -l |
{Пункт отправления} |
.9 ¢- (2.3,...,л] |
{Мнпжестпп вершин, которые |
|
нужно лосетшъ} |
Длина пути ч—0 |
{Общая ятина пути} |
nv*- ! |
{Число пройденных вершин} |
|
{Пусть преемник(v,„) обозначает |
|
паразжиых циклов) множество |
|
вершин, г которце можно |
TVliile преемник (v„) * 0 |
do |
begin |
|
v№l *-BbIbOP(npeeMiimc<vOT)); |
|
Длина пути <- Длина пути +• длина дуги (vm.i, v,lv) if ti'i=n and Длина путиS М then успех
D этом алгаретгмг рассмотрение каждого варианта, т.е. последо вательности соединенны)! дугами вершин Vi, Чд, v,j,...v,„ требует и шагов. Следойптельпо, каждая процедура ВЫБОР (иначе каждая копия алгоритма просмотра одного пути) работает не более, чем по линомиальное время, точнее имеет сложность порядка Таким образом, задача выяснения существования в ориентированном графе гамильтонового чикла, длина которого меньше или равна М, яяляетог NP задачек.
Детерминированная машина Тьюринга является частным случа ем недетерминированной машины Типрииа (которая не имеет ко пий), поэтому имеем, что PQNP
Вопрос о том, будет ли P=NP, является открытой проблемой теории сложности. Широко распространено мнение, что Р г-ЫР, сле довательно, PC.NP.
Примеры задач из класса АР:
записанной пк-кф.;
2)нахождение целочисленных решений системы линейных
3)задача рвепозналалиа простого числа;
4)выяснение гамильтоновоста графа;
5)задача коммивояжера;
6)разнесение обслуживающих центров (телефон, телевиде ние, срочные службы) дня максимального числе клиентов при мини мальном числе центров,
1)оптимальный раскрой (бумага, стальной прокат, отливка опшмизация маршрутов в воздушном пространстве, инвестиций, ста-
287
10) динамическое распределение гтачтги. Раекрием :пу пробле му. Пусть заданы А - множество элементов данных, размер s(a)6T, ^-(1,2,3,.. ), каялого элемент данных аеЛ, время Поэтуиленш
r(a)eZ5", 7-1 =(0,1,2,3,...) и према J(u)e2 оконтанИЯ работы с 5Пг-
.четом данных очЛ, положительное целое число D - размер области памяти Существует ли для множества элементов данных допустимое распределение памяти? Иначе roRops, существует ли такая функция <т. А->[ 1,2,3,...}, что для каждого элементааеА интервал
/(о)=[о(я), a(o)+.s(a)-ll
содержшсх о (1, D], причем дл« любых а. а'еА. если /(t?)n tla'jrZ,
то либо dfii)S г(л*). либо |
г(а) |
|
|
В случае, когда размеры исех элементов данных одинаковы, |
|||
задача решается за полиномиальное время [10); |
|
||
11) организация памяти в виде корневого дерева. Задача состой |
|||
в следующем [10). |
Заданы конечное |
множество X, набор |
|
ло К, Сушествует ли такой набор С=[Х,*, |
|
подмножеств |
|
множествах, что Х,^.Х* при всех i, Is isn , |
£ |
\Х,’ \Х, I&Кн суще |
|
ствует ли ориентрованное корневое дерево ДтД), в котором элемен ты каждого из подмиояагтв X,*, Is i £ и, образуют ориентированный путь?
12) достаточность числа регистров дли реализации циклив. За дача состоит в следующем. Заданы множество V параметров циклов, длина цикла Л’ёZ*. для каждого параметра v начальное преыя S(v')e Z ' н продолжительность /fv)eZ*, целое положительное число К.
Достаточно ли К регистров для запоминания параметров циклов? Иными словами, существует ли тахое назначение регистров / И-»{1,2,3,...Д:}, Что если /(и)—Д?) лля некоторых ii.vsK то из нера венства s<u) sls(v> следует, что «(к)+((и) S sly) и s{v)+i(vXcaodA) s ,т(к)?
Вопи число К заранее фиксировано, то задача разрешима за полиномиальное время (10].
Ш
8 5. .YP-полныс я W -трудные задачи
Рассмотрим смдичость задачХоти сведение одних задач к другим является традиционной математической деятельностно, оно до работ С. Кука не было поанержепо самостоятельному исследова нию. Имении С. Куку принадлежит честь аыдеионка этого понятия как цетршишго в теории полиномиальной сводимости.
Говорет. что задачам сводится к задаче Zi, если истод решения задачи Zi можно преобразовать в метод решенвд задачи Z\. Своди мость называется полиномиальной, если указанное преобразование можно осуществить за полияомиальиСюиремя.
Если одновременно задача 1 \ полиномиально сводится к задаче Z, И Z; полиномиально сводится к задаче Z\, то задачи 7.\ и Zj потномиаяьно знвивапентны.
Задача называется NP-трудной, если каждая задача из N? полиноыиальяо сводится к ней.
ЛР-трудна* задача имеет тот смысл, что эта задача не проще, чем «самая трудная вNP».
В классе NP выделяются МР-по;»гые задачи. Задача называется NP-полной, если они вводит в NP и каждая задача из NP полиномиаль на сводится к ней (т.е. явлаегся ЛР-трудной). ЛУ-полные задачи нопвмаютсв как самые трудные задачи hj kjucch NP.
Класе NP- ттолныхаадач айладает следующими свойствами.
1.Никакую .VP-полкую задачу нельзя решить никаким извест ным полиномиальным алгоритмом, несмотря на настойчивые усилия многих блестямихисследователей.
2.Если бы удалось построить полиномиальный алгоритм для какой-нибудь А'Лпошюй задачи, то это бы означало полиномиальную разрешимость каждой №“-пслкой задачи.
Основываясь на этих двух свойствах, многие высказывают ги
потезу, что P+NP. Практическое значение понятия Л'Р-попнай чадами лежит именно в широко распространенном млении, что такие задачи по существу труднорешаемы. Следовательно, при их решении в худ-
2S9
шем случае потребуется экспоненциальное количеств |
времени и не |
5улет иозможчости решить на практике такие задачи, э |
исключением |
очень малого числа индивидуальных задач. |
|
Первой задачей, для которой было доказано, что она Шлется
.VP-полной, была проблема о вьшолиичостн (си. задачу 1 в § 4). Имеет место слсдуюшая теорема.
Теорема 7.) (теорема Кука). Задача вбшснсния выполнимости формулы логики высказываний, предсталленнай в к к.ф., является /УР-лолноН
Все приведенные ранее примеры NP-згдач (задачи 1-12) йлляются Л?'-полными задачами. Список .№-полних адач в настояШее время содержит несколько сотен задал и продолжает попол няться, Многие вивчъ установленные W -полныс задачи печатаются в журнале Journo] of Algorilhras. В действотельностио большей части задач комбинаторной оптимизации известна либо полиномиальная разрешимость, либо '■'Р-по.тнота, что является еще одним подтвер ждением гипотезыР* NP.
§6. Класс £
Как уже указано, считается, что алгоритм имеет полиномиаль ную временную сложность, если существует полином р(я) такой, что на любом входном слове длины п алгоритм завершает вычисления после вьтолпгнкя не более чем р(п) операций. Если такого полинома не существует, пргмени/ы сложность считается экспоненциальной.
Таким обрами, для них число операций возрастает быстрее значений
Кроме этого определения, существует н второе определение: алгоритм имеет жепонвпциальную лреметиук» сложность, если его временная сложность имеетпорядоккг меньше, чемси", гдеt а(а> 1)- пастоинные. Другими столами, временная сложность f(n) является