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