Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 237
Текст из файла (страница 237)
Согласно сформулированной ниже теореме, существование быстрого алгоритма для решения задачи о коммивояжере маловероятно. Теорема 34.14. Задача о коммивояжере (ТЗР) является ХР-полной. Доказалгельслгво. Сначала докажем, что ТБР принадлежит классу ХР. В качестве сертификата для заданного экземпляра задачи будет использоваться последовательность и вершин, из которых состоит тур. В алгоритме верификации проверяется, что в этой последовательности все вершины содержатся ровно по одному разу, а также суммируются стоимости всех ребер тура и проверяется, что эта сумма не превышает /с. Очевидно, что этот процесс можно выполнить в течение полиномиапьного времени. Чтобы убедиться в том, что задача ТЯР ХР-сложная, покажем, что Нам Сусли <р ТЯР. Пусть С = (У, Е) — экземпляр задачи Ням Сусг.н.
Экземпляр ТИР конструируется следующим образом. Сформируем полный граф С' = (У, Е'), где Е' = ((г,у'): 1,7' Е У и 1 ф Я. Определим также функцию стоимости с: (О если (1,3) Е Е, с(т',3) = (1 если (1,3) 1е Е. (Заметим, что поскольку граф с' неориентированный, в нем отсутствуют петли, поэтому для всех вершин п е У выполняется равенство с (и, п) = 1.) Тогда в качестве экземпляра ТЯР выступает (С', с, 0), который легко составить в течение полиномиального времени. Часть ЧП.
Избранные темы 1140 Теперь покажем, что граф С содержит гамильтонов цикл тогда и только тогда, когда граф С' включает в себя тур, стоимость которого не превышает О. Предположим, что граф С содержит гамильтонов цикл Ь. Каждое ребро цикла 5 принадлежит множеству Е, поэтому его стоимость в графе С' равна О. Таким образом, стоимость цикла Ь в графе С' равна О. И обратно — предположим, что граф С' содержит тур К стоимость которого не превышает О.
Поскольку стоимости ребер графа С' равны 0 или 1, стоимость тура Ь' равна О, и стоимость каждого ребра из тура должна равняться О. Таким образом, тур 5' содержит только ребра из множества Е. Можно сделать вывод, что тур 6' — это гамильтонов цикл в графе С. 34.5.5 Задача о сумме нодмпожества Слелующая ХР-полная задача, которая будет рассмотрена, принадлежит к разряду арифметических. В задаче о сумме подмножества (зиЬзе1-зшп ргоЫеш) задается конечное множество Я С Х и целевое значение ([агйе1) г Е Х.
Спрашивается, существует ли подмножество У С Я„сумма элементов которого равна ~. Например, если Я = (1,2,7,14,49,98,343,686,2409,2793,16808,17206,117705,117993), а ~ = 138 457, то решением является подмножество У = (1,2,7,98,343,686,2409,17206,117705). Как обычно, определим язык, соответствующий задаче: Бивзнт 8им = ((Я,~): существует подмножество У С о такое, что 4 = ''з в). ~-~вез' Как в любой арифметической задаче, важно помнить, что в нашем стандартном коде предполагается, что входные целые числа кодируются бинарными значениями. При этом предположении можно показать, что вероятность наличия быстрого алгоритма, позволяющего решить задачу о сумме подмножества, очень мала.
Теорема 34.15. Задача о сумме подмножества является МР-полной. Доказаюлельснгво. Чтобы показать ХР-полноту задачи Бодает 8им для экземпляра (Я,1), выберем в качестве сертификата подмножество У. Проверку равенства Ф = 2 ', з, в в алгоРитме веРификации можно выполнить в течение полиномиального времени. Глава 34. ИР-полнота 1141 Теперь покажем, что 3-С)чг БАт <р Бивзнт Бим. Если задана 3-СНЕ формула ф, зависящая от переменных хы хз,..., х„н содержащая подвыражения в скобках Сз, Сз,..., Сы в каждое из которых входит ровно по три различных литерала, то в алгоритме приведения строится такой экземпляр (5, г) задачи о сумме подмножества, что формула ф выполнима тогда и только тогда, когда существует подмножество Я, сумма элементов которого равна 1.
Не теряя общности, можно сделать два упрощающих предположения о формуле ф. Во-первых, ни в одном подвыражении в скобках не содержится одновременно и переменная, и ее отрицание, потому что такое выражение автоматически удовлетворяется при любых значениях этой переменной.
Во-вторых, каждая переменная входит хотя бы в одно подвыражение в скобках, так как в противном случае безразлично, какое значение ей присваивается. В процессе приведения в множестве Я создается по два числа для каждой переменной х; и для каждого выражения в скобках С . Эти числа будут создаваться в десятичной системе счисления, и все они будут содержать по и + й цифр, каждая из которых соответствует переменной или выражению в скобках. Основание системы счисления 10 (и, как мы увидим, и другие основания) обладают свойством, необходимым для предотвращения переноса значений из младших разрядов в старшие. Как видно из табл.
34.2, множество Я и целевое значение 1 конструируются следуюшим образом. Присвоим каждому разряду числа метку, соответствующую либо переменной, либо выражению в скобках. Цифры, которые находятся в й младших разрядах, отвечают выражениям в скобках, а цифры в и старших разрядах отвечают переменным. ° Все цифры целевого значения 8, соответствующие переменным, равны 1, а соответствующие подвыражениям — равны 4.
° Каждой переменной яч в множестве Я сопоставляются два целых числа,— и; и п,'. В каждом из этих чисел в разряде с меткой х; находится значение 1, а в разрядах, соответствующих всем другим переменным, — значения О. Если литерал яч входит в подвыражение С, то цифра с меткой С в числе и; равна 1. Если же выражение в скобках С содержит литерал -х;, то 1 равна цифра с меткой С в числе и,'. Все остальные цифры, метки которых соответствуют другим выражениям в скобках, в числах кч и о1 равны О. Значения о; и о,' в множестве 5 не повторяются.
Почему? Если 1 ф г', то число, содержащееся в и старших разрядах значений ц или о', не могут быть равны соответствующим числам из значений и; или о,'. Кроме того, согласно сделанным выше упрошающим предположениям, такое равенство невозможно для чисел, содержащихся в Й младших разрядах значений о; и и,'. Если бы числа ка и о,' были равны, то литералы яч и ~х, должны были бы входить в один и тот же набор подвыражений в скобках. Однако, Часть ЧП. Избранные темы 1142 согласно предположению, ни одно подвыражение не содержит одновременно и х;, и х;, и хотя бы один из этих литералов входит в одно из выражений в скобках. Поэтому должно существовать какое-то подвыражение С, благодаря которому числа те и п,' различаются.
° Каждому подвыражению С в множестве Я сопоставляются два целых числа л и л'. Каждое из них содержит нули в разрядах, метки которых отличаются от С. В числе л цифра с меткой С равна 1, а в числе л' эта цифра равна 2. Такие целые числа выступают в роли "фиктивных переменных", благодаря юторым в суммарном значении каждая цифра, соответствующая выражению в скобках, равна 4.
Простая проверка для примера, проиллюстрированного в табл. 34.2, показывает, что никакие значения л и л' в множестве Я не повторяются. В приведенном примере рассматривается 3-С1чр формула ф = Сз Л Сз Л Сз Л С4 где Сз — — (хзч хач хз), Сз = ( хт ч хзч хз), Сз = ( хз ч хачхз) и Са = (хз Ч хз Ч хз). Выполняющий набор для формулы ф имеет вид (хт = О, хз = О, хз = 1). Множество Я, полученное в процессе приведения, состоит из представленных в таблице чисел в десятичной системе счисления; считывая их сверху вниз, находим, что 5 = (1001001,1000110,100001,101110,10011,11100,1000,2000,100,200,10,20,1,2); целевое значение 8 = 1114444.
Подмножество У С Я выделено светлой штриховкой и содержит пгы пз и цз, соответствующие выполняющему набору. В него также входят помеченные той же штриховкой фиктивные переменные, обеспечивающие получение значений 4 в цифрах целевого значения, помеченных подвыражениями. Заметим, что максимальная сумма цифр в каждом из разрядов равна б. Это возможно в цифрах, метки которых соответствуют выражениям в скобках (трн единицы от значений хч и п,' плюс 1 и 2 от значений л3 и л'). Поэтому этн значения интерпретируются как числа в десятичной системе счисления, чтобы не было переноса из младших разрядов в старшие".
Такое приведение можно выполнить в течение полиномиального времени. Множество Я содержит 2гз+ 2/с значений, в каждом из которых по за+ 1с цифр, поэтому время, необходимое для получения всех цифр, выражается полиномиальной функцией от и + 1с. Целевое значение 1 содержит и + и цифр, и в процессе приведения каждую из них можно получить в течение фиксированного времени. Теперь покажем, что 3-СХг формула выполнима тогда и толью тогда, когда существует подмножество Я' С Я, сумма элементов которого равна 1.
Сначала Фактически, подошло бы любое основание 6 > 7. Так, экземпляр задачи, который рассматривается в начале этого подраздела, представляет собой множество Я и целевое значение г из табл. 34.2, где все значения рассматриваются как числа в семеричной системе счисления, отсортированные в порядке убывания.
Глава 34. МР-полнота 1143 Таблица 34.2. Процесс вриведсвна аалавн 3-СХР оАг к еалавсв~лл1 бп~ л, т, хз С, Сс Сз С~ иг~,.:, .:,,.'.,':-','.,';: '.": 1',:: "О: -;;:.:",0 '":;:,':-'.;.,:О, '::;;:.1.., '.' в:1-~:,:::,.' ' О изо ';"„'=,,',,'';,' ' О ' ', ' 1; '; ', О:::,с::.; '.1' ' . 1 "'' 1'''' О из ',—— :... О... О,. 1.;.",'.,О, ....' 0: ' 1 ... 1 а1: ..",:':= ., к, 0:"' ' 0";:.:: ' „'О .:"'::::-'.;":, 1: -:.': 0':::,-О:, 0 з1, '.':: '='":,.
'"". О ' О! ' ' 'О":.' ' ''2' ''.',.": О '."0:;"' ' О . "а~~,,''.:„'...,',=.,,'.'1;,::...::,.",':О,",,' О „'',' " О';..;„.;;:„.:,О,';",;.2"';,::,:О,-.:.: о:. О 83 ' с,!г:.!,",,*: '0:, ': О '. '':,',а 0 ";:,:'" .'„"%'„О ' °,: О' '" ",1:," ' О ' ь~~'','. ':::,"=-":: ":: О, ":;, О';::; ':О;;;:.-'!:::::.;О'::„::.:':: О,::;::;:::::.О:"':-': "'2 1 1 1 4 4 4 4 предположим, что у формулы ф имеется выполняющий набор. Если в нем х; = 1 (где 1 = 1, 2,..., и), то число ти включается в множество 8'. В противном случае в это множество включается число е;'. Другими словами, в множество 8' включаются именно те значения кч и ц,', которым в выполняющем наборе соответствуют литералы, равные 1.
Включая в множество У либо число о;, либо число е,', но не оба этих числа для всех а, и помещая в значениях а и а' нули во все разряды с метками, соответствующими переменным, мы видим, что сумма цифр в этих разрядах по всем значениям множества У должна быть равной 1, что совпадает с цифрами в этих разрядах целевого значения $. Поскольку все подвыражения в скобках выполняется, в каждом таком подвыражении имеется литерал, значение которого равно 1. Поэтому каждая цифра, соответствующая подвыражению, включает единицу, вносимую в сумму благодаря вкладу значения сч или значения ц,' из множества Я'. В действительности в каждом выражении в скобках единице могут быть равны 1, 2 или 3 литерала, поэтому в каждом разряде, соответствующем выражению в скобках, сумма цифр по значениям сч и о,' множества У равна 1, 2 или 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
