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

Если удастся доказать, что хотябы какая-то одна NP-полная задача принадлежит классу Р, тотем самым было бы доказано, что Р = NP и можно в принципенадеяться на построение эффективных алгоритмов дляразличных классов дискретных задач. Если же классы Р и NPразличны, то придется разрабатывать эффективные алгоритмыдля все более узких классов задач. Возможна и такаяситуация, что гипотезу P^NP (принимаемую многимиматематиками) нельзя ни доказать, ни опровергнуть(аналогично к о н т и н у у м - гипотезе).Большой практический опыт решения дискретных задачдает основание считать, что NP-полные задачи и задачи из Рсильно отличаются по трудоемкости решения, но в строгомсмысле до сих пор это различие и, следовательно, различиемежду классами Р и NP, не доказано. Это объясняется тем, чтоклассы Р и NP определяются с помощью понятия времениработы вычислительного устройства с потенциальнонеограниченной памятью. Однако хорошо известно, что времявыполнения алгоритма на машине плохо поддается описаниюи анализу общематематическими средствами.Излагаемая ниже и ставшая уже классической теорияполиномиальной сводимости была построена для задачраспознавания свойств.

Но можно построить аналогичнуютеорию (полиномиальной) сводимости для экстремальныхдискретных задач. Более того, при построении указаннойтеории можно не пользоваться моделью вычислительногоустройства.Как уже отмечалось, настоящие пособие написано наоснове ряда переводных и отечественных книг и используетприводимые там результаты, давая в ряде случаев подробныедоказательства, которые при первом чтении можно опустить ирассчитано в первую очередь на слушателя-новичка визучении теории сложности алгоритмов и вычислений.ГЛАВА 1.

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИСЛОЖНОСТИНайдется немного научных терминов, так быстрозавоевавших широкую известность, как понятие «NP-полнаязадача». Возникшее в начале 70-х годов, оно стало символомгромадных трудностей, с которыми все чаще приходитсясталкиваться разработчикам алгоритмов по мере того, как ониберутся за решение задач постоянно возрастающейразмерности и усложняющейся структуры.

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

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

За подобное решение вы едва ли удостоитесьпохвалы шефа, поскольку перебор всех вариантов только дляодного набора технических характеристик потребуетнескольких лет машинного времени, а в Отделе машин уже потринадцати узлам машины наблюдается отставание отнамеченного графика. Естественно, что у вас нет желаниявозвращаться в кабинет шефа со словами:«Я не могу найти эффективного алгоритма, боюсь, что ядля этого слишком туп».Для вашего положения в компании было бы гораздолучше, если бы вы смогли доказать, что поставленная задача впринципе трудно решаема и что ни один алгоритм вообще нев состоянии решить ее быстро. В этом случае вы могли быуверенно шагнуть в кабинет шефа и заявить:«Я не могу найти эффективного алгоритма, потому чтотакого алгоритма не существует!»К сожалению, доказать, что задача труднорешаема, можетбыть не менее трудно, чем найти эффективные алгоритмы.Даже выдающиеся теоретики оказывались беспомощными впопытках получить подобное доказательство для трудныхзадач.

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

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

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

Можно быначать разработку эффективных алгоритмов, позволяющихрешать различные частные случаи поставленной общейзадачи. Можно заняться отысканием алгоритмов, хотя и негарантирующих быстрого решения, однако работающихбыстро в большинстве случаев. Можно даже ослабитьпостановкузадачииискатьбыстрыйалгоритмпроектирования машин, у которого заданным требованиямудовлетворяет большая часть характеристик. Короче говоря,основное предназначение теории NP-полных задач в том,чтобы помочь разработчикам алгоритмов и направить ихусилия на выбор таких подходов к решению задач, которыеприведут к практически полезным алгоритмам. Введем теперьосновные понятия теории сложности и рассмотрим ихприменимость.ЗАДАЧИ, АЛГОРИТМЫ И СЛОЖНОСТЬЧтобы в дальнейшем изучать такие понятия, как«труднорешаемые задачи» и «эквивалентные по сложностизадачи», необходимо договориться о значении несколькихосновных терминов, не давая формальных определений.Начнем с понятия задачи.

Массовой задачей (или простозадачей) называется некоторый общий вопрос, на которыйследует дать ответ. Обычно задача содержит ряд параметров,или свободных переменных, конкретные значения которых неопределены. Задача П определяется следующей информацией:(1) общим списком всех ее параметров и(2) заданием тех свойств, которым должно удовлетворятьрешение задачи.Индивидуальная задача I получается из массовой задачиП, если всем параметрам задачи П присвоить конкретныезначения.В качестве примера рассмотрим классическую задачу окоммивояжере. Параметры этой задачи состоят из конечногонабора «городов» C={cj,c^,...,cm} и «расстояний» d(chc,) междупарами c„Cj из С.

Решением является упорядоченный набор<cn(i),cn(2),...,cni-m)> заданных городов, который минимизирует)) + ^(ся(,я), гяш).величинуПоследнее есть длинамаршрута, начинающегося в городе сж(1), проходящегопоследовательно через все города и возвращающегося внепосредственно из последнего города сл(т). Индивидуальнаязадача о коммивояжере, показанная на рисунке 1.1 ниже,задается следующим образом:C = { £ j, c<i, Cj, c j ,с3} = Ш, d{ti, Сз)=5,d - ( c lt с 4} = 9 , d(Ci, C j)= 6 , d(ft, с 4) ~ 9 , d(cs, c j — 3.Последовательность <cl, c2, c4, сЗ> представляет собойрешение задачи, поскольку соответствующий маршрут имеетминимальную возможную длину, равную 27.Рис.

1.1. И вдиви д у а л ьн а я зад ача окоммивояжере и м арш рут минимальнойвозможной длин ы , равной Й7.Под алгоритмом будем понимать общую, выполняемуюшаг за шагом процедуру решения задачи (можно считать еепрограммой для ЭВМ, написанной на формальном машинномязыке). Будем говорить, что алгоритм решает массовуюзадачу П, если он применим к любой индивидуальной задаче Iиз П и обязательно дает решение задачи I. Термин «решение»понимается здесь строго в соответствии с данным вышеопределением. Нельзя сказать, например, что алгоритм решаетзадачу о коммивояжере, если он не выдаст маршрутминимальной длины хотя бы для одной индивидуальнойзадачи.Вообще говоря, нужен наиболее эффективный алгоритмрешения задачи.

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