Алгоритмы - построение и анализ (1021735), страница 237
Текст из файла (страница 237)
В числе л цифра с меткой С равна 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;,"'' ' О .
"а~~,,''.:„' „'.,=,„,'.'"'::в",',0 .",.,' О.'„;',; "О,';.;;;!:,';,,::.'.':О,:,";.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. (Например, в примере, проиллюстрированном в табл. 34.2, в выполняющем наборе единице равны литералы - км - хз и хз. Каждое из выражений в скобках Часть ЧП. Избранные темы 1144 С1 и С4 содержит ровно по одному из этих литералов, поэтому числа п', пз и пз в совокупности дают единичный вклад в цифры, соответствующие выражениям Сг и С4. Подвыражение Сз содержит по два этих литерала, поэтому числа о', пз и пз в совокупности дают вклад 2 в цифру, соответствующую Сз. Подвыражение Сз содеРжит все тРи пеРечисленных литеРала, и числа пгы пз и оз дают вклад 3 в цифру, соответствующую выражению Сз.) Целевое значение, равное 4, достигается в каждом разряде с меткой, отвечающей подвыражению в скобках, путем добавления в множество У непустого множества из соответствующих фиктивных переменных (вз, в' ).
(В примере, проиллюстрированном в табл. 34.2, множество У включает значения (вы в'„вз, зз, в4, в4).) Поскольку сумма цифр по всем значениям множества У во всех разрядах совпадает с соответствующими цифрами целевого значения 1, и при суммировании не производится перенос значений из младших разрядов в старшие, то сумма значений множества У равна 1. Теперь предположим, что имеется подмножество У С Я, сумма элементов которого равна 1. Для каждого значения 1 = 1, 2,..., п это подмножество должно включать в себя ровно по одному из значений п; или о,', потому что в противном случае сумма цифр в разрядах, соответствующих переменным, не была бы равна 1. Если о; е У, то выполняем присваивание х; = 1.
В противном случае о1 е У, и выполняется присваивание х; = О. Мы утверждаем, что в результате такого присваивания выполняется каждое подвыражение С, з = 1, 2,..., /с. Чтобы доказать это утверждение, заметим, что для того, чтобы сумма цифр в разряде с меткой С была равна 4, подмножество У должно содержать хотя бы одно из значений п; или и,'э в ютором 1 находится в разряде с меткой С, так как суммарный вклад фиктивных переменных в и в' не превышает 3. Если подмножество У включает в себя значение п;, в котором в этом разряде содержится 1, то в подвыражение Сз входит литерал х;. Поскольку при п; Е У выполняется присваивание х; = 1, то подвыражение Сз выполняется. Если множество У включает в себя значение п1э в котором в этом разряде содержится 1, то в подвыражение С входит литерал - хь Так как при п,' Е У выполняется присваивание х; = О, то подвыражение Сз снова выполняется. Таким образом, в формуле ф выполняются все подвыражения в сюбках, и на этом доказательство теоремы завершается.
В Упражнения 34.5-1. В задаче об изоморфизме нодграфу (зпЬягарЬ-1зотогрЬ)зт ргоЫеп1) задаются два графа (С1 и Сз) и спрашивается, изоморфен ли граф С1 какому-нибудь подграфу графа Сз. Покажите, что эта задача Хр-полная. 34.5-2. В задаче 0-1 целочисленного программирования (0-1 т1ейег-ргойгатт1пя ргоЫет) задается целочисленная матрица А размером т х п и целочисленный т-компонентный вектор Ь и спрашивается, существует ли Глава 34. МР-полнота 1145 целочисленный гс-компонентный вектор х, элементы которого являются элементами множества 10,1), удовлетворяющий неравенству Ах < Ь. Докажите, что задача 0-1 целочисленного программирования является ХР-полной. (Указание: приведите к этой задаче задачу 3-СХР БАт.) 34.5-3. Задача целочисленного линейного нроераммированил (шсеяег 1шеагргойгапппшя ргоЫеш) похожа на задачу 0-1 целочисленного программирования, описанную в упражнении 34.5-2, но в ней компоненты вектора х могут быть любыми целыми числами, а не только нулем и единицей.
Исходя из предположения, согласно которому задача 0-1 целочисленного программирования является ХР-полной, покажите, что задача целочисленного линейного программирования также ХР-полная. 34.5-4. Покажите, что задача о сумме подмножества разрешима в течение полиномиапьного времени, если целевое значение С выражено в унарной системе счисления, т.е. представлено последовательностью из С единиц.
34.5-5. В задаче о разделении множества (зес-рагййоп ргоЫегп) в качестве входных данных выступает множество чисел Я. Спрашивается, можно ли это числа разбить на два множества А и А = Я вЂ” А таким образом, чтобы ',> А х = 2 А х. Покажите, что задача о разделении множества является ХР-полной. 34.5-6. Покажите, что задача о гамильтоновом пути ХР-полная. 34.5-7. Задача о самом длинном простом цикле (1опйезг-зсшр)е-сус)е ргоЫеш)— это задача, в которой в заданном графе находится простой цикл (без повторения вершин) максимальной длины. Покажите, что эта задача— ХР-полная. 34.5-8.
В половинной задаче о 3-СИР выполнимости (Ьа!Г 3-СХР зассзбаЬйссу ргоЫеш) задается 3-СХР формула ф с гс переменными и гп подвыражениями в скобках, где гп — четное. Нужно определить, существует ли набор значений переменных формулы ф, при котором результат ровно половины выражений в скобках равен О, а результат второй половины этих выражений равен !. Докажите, что половинная задача о 3-СХР выполнимости является ХР-полной. Задачи 34-1. Независимое множество Независимым множествам (1пберепгсепс зес) графа С = (Ъ; Е) называется такое подмножество вершин Ъ" С У, что каждое ребро из множества Е инцидентно хотя бы одной вершине из множества У'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
