(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) ((см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010).pdf), страница 3

е. объем входных данных,требуемых для описания задачи. Такой подход удобен, т.к. вдальнейшемсравнительнаясложностьзадачбудетоцениваться через их размеры. Часто размер задачиизмеряется неформально. В задаче о коммивояжере для этойцели обычно используется число городов. Однако в задаче с тгородами кроме номеров этих городов на объем входнойинформации влияют также т(т—1)/2 величин, определяющихрасстояния между городами.

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

Предположим, что заранее выбраннекоторый определенный способ и что с каждой массовойзадачей связана некоторая фиксированная схема кодирования,котораяотображаетиндивидуальныезадачивсоответствующие цепочки символов. Входная длинаиндивидуальной задачи I из П определяется как числосимволов в цепочке, полученной применением к задаче Iсхемы кодирования для массовой задачи П. Именно это число,т. е. входная длина, и используется в качестве формальнойхарактеристики размера индивидуальной задачи.Например,различныеконкретныезадачиокоммивояжере можно описать с помощью алфавита {с, [, ], /,О, 1, 2, 3, 4, 5, 6, 7, 8, 9}, при этом предыдущий пример будетзакодированввидетакойцепочкисимволов:с [1] с [2] е [3] с [4]//10/5/9//6/9//3_ Кодирование индивидуальныхзадач аналогично.

Данная кодирующая схема для задачи окоммивояжере дает входную длину 32.Временная сложность алгоритма отражает требующиесядля его работы затраты времени. Это функция, котораякаждой входной длине п ставит в соответствие максимальное(по всем индивидуальным задачам данной длины) время,затрачиваемое алгоритмом на решение индивидуальных задачэтой длины.Эта функция не будет полностью определена до тех пор,пока не зафиксирована схема кодирования, определяющаявходную длину индивидуальной задачи и не выбрановычислительное устройство (или его модель), определяющеевремя работы. Однако, как будет видно из дальнейшего,подобные детали окажут незначительное влияние на различиямежду классами, возникающими в теории NP-полных задач.Поэтомувдальнейшемчитателюрекомендуетсязафиксировать мысленно какую-либо конкретную схемукодирования для каждой задачи, выбрать некотороеконкретное вычислительное устройство или его модель ирассматривать затем временную сложность алгоритмов всоответствии с получающимися входнымисоответствующими затратами времени.длинамииПОЛИНОМИАЛЬНЫЕ АЛГОРИТМЫ ИТРУДНОРЕШАЕМЫЕ ЗАДАЧИРазные алгоритмы имеют различную временнуюсложность и выяснение того, какие алгоритмы достаточноэффективны, а какие совершенно неэффективны, всегда будетзависеть от конкретной ситуации.

Однако теоретики,занимающиеся разработкой и анализомалгоритмов,предлагают для сравнения эффективности алгоритмов одинпростой подход, позволяющий существенно прояснитьситуацию. Речь идет о различии между полиномиальными иэкспоненциальными алгоритмами.Будем говорить, что функция f{n) есть 0(g(n)), еслисуществует константа с, такая, что \f[n)\ < c|g(n)| для всехзначений п>0.

Полиномиальным алгоритмом (или алгоритмомполиномиальной временной сложности) называется алгоритм,у которого временная сложность равна 0(р(п)), где р(п) полином, а п - входная длина. Те алгоритмы, временнаясложность которых не поддается подобной оценке,называются экспоненциальными (это определение включает итакие функции, как nlogn, которые хотя и не являютсяполиномиальными, но и не считаются экспоненциальными).Различие между двумя указанными типами алгоритмовстановится особенно заметным при решении задач большогоразмера. Таблица на рис. 1.2 позволяет сравнить скоростиростанесколькихтипичныхполиномиальныхиэкспоненциальныхфункций(обратитевниманиеначрезвычайно быстрый рост двух приведённых экспонент).Р язм ерпФ унт ря1рслнпШелт т ет ип„1я5п*г*3*100,00001сек20304050600,000020,0000.50,000040,00005ССКШсек0,00006т*0,00160,0025Ц0036№(ЩcmССК0,00040,000!е&сшОДОМотсск0,1сек0,00!ш'0,00090,02?0,064с екахт3,224,3сексекаш0,216с сксек1,75,213,0м инлш нм ин1.017,912,735,7366CSKМЧИднейлетст олет ий38552x10*«годен»?апат ий0,05953CSXли т6,5летат т т ий1,3x101»Рис.

1,2. Сравнение нескольких полиномиальных к акспонеициалышх функ­ций временной сложности.Различиемеждуполиномиальными иэкспоненциальными алгоритмами проявляется еще болееубедительно, если проанализировать влияние увеличениябыстродействия ЭВМ на время работы алгоритмов. Рис. 1.3показывает, насколько увеличатся размеры задач, решаемыхза один час машинного времени, если, благодарясовершенствованию технологии, быстродействие ЭВМвозрастет в 100 или 1000 раз по сравнению с современными(на 1980 год) машинами. Заметим, что для функции fin) = 2"увеличение скорости вычислений в 1000 раз приводит лишь ктому, что размер наибольшей задачи, разрешимой за один час,возрастет только на 10, в то время как для функции fin) = п~этот размер возрастет почти в 4 раза.Ромеры наибольшей задачи,разрешимой за един vetoФутция(ременнойметжсяшИисе$ремен/шх Ha sen, t m разЗВНболе» быстрыхНа т п, б \ т разSexes йитрыхЯ:Н<гсо мГОООя*Hi10 №31,6 №«3№4,64 Н,Ю Нзп*Mi« А2яHiМу+ 6,64iV j+9,973яHi№ * * ,1 9№ * 6,393.9S №Рис.

1.3. Влияние технического совершепствопаипп ЭВМ ns полиномам»*ные и «кспонеациальные алгоритмы.Этитаблицыдемонстрируюттотфакт,чтополиномиальные алгоритмы обычно считаются болеепредпочтительными по сравнению с экспоненциальными.Такая точка зрения, различающая, с одной стороны,полиномиальные алгоритмы,а с другой стороны,экспоненциальные, и будет являться отправным пунктом внашем определении труднорешаемых задач и теории NPполных задач.Большинство экспоненциальных алгоритмов есть простоварианты полного перебора, в то время как полиномиальныеалгоритмы обычно можно построить Лишь тогда, когдаудается более глубоко проникнуть в суть решаемой задачи(см.

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

Различиемеждуэффективными(полиномиальными) алгоритмамиинеэффективными (экспоненциальными) алгоритмами можетпринять иной характер, когда размеры решаемых задачневелики. Функция J[n)=2n ведет себя лучше, чем /(«) = п прип < 20 по отношению к размерам наибольшей задачи,разрешимой за 1 час. Известны некоторые экспоненциальныеалгоритмы, хорошо зарекомендовавшие себя на практике.Дело в том, что временная сложность определена нами какмера поведения алгоритма в наихудшем случае, и тот факт,что какой-то алгоритм имеет временную сложность порядка2", означает только, что решение по крайней мере однойиндивидуальной задачи размера п требует времени порядка 2".Может оказаться, что большинство индивидуальных задачтребует для своего решения значительно меньших затратвремени, и такого рода ситуация имеет место для несколькиххорошо известных алгоритмов.

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

Однако исследователи не отказались от попыток найтидля соответствующих задач полиномиальные алгоритмы. Самфакт успешного применения экспоненциальных алгоритмовдавал основание предположить, что более глубокое ихисследование может привести к дальнейшему улучшениюметодов. В настоящее время не получено удовлетворительныхобъяснений, почему эти алгоритмы работают успешно, и неизвестны методы, позволяющие заранее прогнозироватьхорошую работу того или иного экспоненциальногоалгоритма в практической ситуации (возможно, что даннаяситуация уже исследована более подробно).С другой стороны, полиномиальные алгоритмы частопозволяют делать такого рода прогнозы, посколькуполиномиальные функции значительно более адекватнооценивают время работы алгоритмов. Хотя алгоритмы,имеющие временную сложность типа п,0° или 1099п , не могутсчитаться эффективными с практической точки зрения,естественно возникающие полиномиальные задачи обычнотребуют для своего решения времени порядка п2 или п ,причем коэффициенты при старших членах полиномов неслишком велики.

Такие алгоритмы можно считатьэффективными, и именно это свойство заставляет отдаватьпредпочтение полиномиальным алгоритмам как средствурешения задач.Определение трудно решаемой задачи создает базу длятеории, обладающей значительной общностью и большимивозможностями.Понятиетруднорешаемойзадачиоказывается по существу независимым от конкретной схемыкодирования и модели ЭВМ, используемых при определениивременной сложности.Схема'квдиройШ1Цента еом(ш (риф)ДлинаШтт(ершикupettyV{l)V[2]VMV{4KV{llVf2])(Vi2lVB3)36Стаж'<же№M2}){VWV(3})M2})()24СтремтюкщиищФшИ 0100/1010/0010/0000Рис.

1.4, Описания графа G■==(К, Я), где У «■»ц*Hs. гз}}, яри трех разам/. схемах кодирования.19в,},Рассмотрим сначала схемы кодирования. Предположим,что решаемая задача определена на графе G = (V, Е), где Vмножество вершин, Е - множество ребер и каждое ребропонимается как неупорядоченная пара вершин. Условия этойзадачи могут быть описаны (см. рис. 1.4) либо простосписками всех вершин и ребер, либо с помощью матрицыинциденций графа, либо составлением для каждого узласписка всех узлов, имеющих с данным общее ребро (списки«соседей»).

Эти схемы кодирования для одного и того жеграфа могут дать входы разной длины. Однако легкопроверить (см. рис. 1.5), что получаемые входы отличаютсядруг от друга не более чем полиномиальным образомСхема хсИщхймийШ ш кт ниЛСписок ст ЬИМя/п&щв щ ш кнцниН инт щ т+ Ше2v + 8с+с - 18 щ /т щенка4с + 10с + {c+leHlotovi+ 8е + 2e>[logi„v]и1+ 1»- 1Put. 1.5. Общие оценки длины входа для трех схем кодирования графа0**{Vt Е), представленных иа рис. 1,4, где fУj*=*о, ]£(>=(?. Поскольку£ < о-, эти оценки тошыазют, что длины входа отличаются друг от другане более чем паэдкомнзяышм образом (|л) обозначает наименьшее целоечисло, не меньшее, чем л).(проверьте!), т.е.