Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 75
Текст из файла (страница 75)
Т является объединением троек следующих трех типов (пастрое. ние проиллюстрировано на рис. 15.12). 1. Тройки (а'„Ь,', х',), 1 1, ..., п, / 1...,, т, и (а',", Ь!, х,'), / 1, ..., п, / 1, ..., т (здесь аT+' а,'). Вер- Гл. И. гуР-полные нгдочи шины типа а и Ь не входят ни в какие другие тройки. Поэтому для каждого 2' эти тройки будут требовать, чтобы в М с а и Ь обьединялись либо все х', (это означает, что х, имеет значение истина) или все х',(хг имеет значение ложь), 2. Второй тип троек в Т образует множество ((оу, го,н М); 1=- 1, ..., пг, )ь — литерал дизъюнкта С,. Вершины тйпа о и иг входят только в эти тройки.
Так как, согласно принятому выше нг ег Ю2 Ег Г=(к,+ хз)(хг е хт) Вершины типа с и гг не показаны О )г Х; показанные треугольники Покаэанное сочетание соответствует набору: Г (х ) =еаеехл г г(хз) Рнс. !б.иь соглашению, к этому моменту свободны только литералы со значением истина, то вершины о и иг должны объединяться с литералами соответствующих дизъюнктов, имеющими значение истина; следовательно, все дизъюнкты должны выполняться при данном наборе значений истинности. И.г.
Еще неокол»ко Гч'Р-аолнззх задач 3. Назначение вершин типа с н д, так же как троек последнего типа (троек «сбора мусора» в элегантной терминологии из (О3!),— «подобрать» оставшиеся копии различных литералов. Эти тройки образуют множество ((с';, д!, Хн); |=1,..., и, |=-1, ..., и, й= =1, ..., т, 1. — литерал). Из приведенных выше рассуждений следует, что в том случае, когда существует совершенное сочетание М, формула Р выполнима. Обратно, если формула Р выполнима на наборе значений истинности |, то можно объединить вершины а и Ь с лите(залами в соответствии с |; затем можно объединить каждую из вершин о и зв с одним истинным литералом нз соответствующего дизъюнкта. Так как по предположению | выполняет Р, такой литерал всегда найдется. Наконец, остальные литералы подбираются вершинами сид.
П Следующий вариант задачи 3-МЕРНОЕ СОЧЕТАНИЕ исключительно полезен как отправная точка для доказательства многих результатов об УР-полноте. ТОЧНОЕ ПОКРЫТИЕ 3-МНОЖЕСТВАМИ Дано семейство Р= (Ян ..., Зн), состоящее из и трехэлементиых подмножеств множества 5=(а„..., и,„). Спрашивается, существует ли в Р подсемейство, содержащее т подмножеств и покрывающее 5. Следствие. Задача ТОЧНОЕ ПОКРЪ|ТИЕ 3-МНОЖЕСТВАМИ ЫР-полна.
Доказательство. Достаточно заметить, что задача 3-МЕРНОЕ СОЧЕТАНИЕ является частным случаем задачи ТОЧНОЕ ПОКРЫТИЕ 3-МНОЖЕСТВАМИ с Я=НО Г11 Ю' и Р=((а, Ь, с): (а, Ь, с)ЕТ). Д Под задачей о рюкзаке обычно понимается следующая задача целочисленного линейного программирования с матрицей, имеющей одну строку: максимизировать Х сух| ~=1 н при условии ~ н|х,( К, х,— целые (или 0-1), /=! Это название напоминает, что такая задача максимизации возникает, когда мы хотим заполнить рюкзак вместимости К предметами, имеющими наибольшую возможную пользу.
Мы будем рассматривать здесь вариант распознавания для частного случая, в котором с|=шъ /=1,..., и. Возможны два варианта. 13 м зозз звв Гл. !5. 1«'Р-полнее задачи ЦЕЛОЧИСЛЕ1-1Н ЫЙ РЮКЗАК Даны целые числа с, 1 = — 1, ..., и, и К, Спрашивается, существуют ли такие целые числа х, ) О, 1 = 1, ..., а, что ~ч '1, с,х, = К. 0-1-РЮКЗАК Даны целые числа с, 1= 1, ..., и, и К. Спрашивается, существует ли такое подмножество 5 множества (1, ..., п), что Теорема 15.8. Задача 0-1-Р!ОКЗА К 1«' Р-полна, Доказательство. Очевидно, эта задача входит в 1«' Р; кроме гого, можно показать, что задача ТОЧНОЕ ПОКРЫТИЕ 3-МНОЖЕСТВАМИ полиномиально преобразуется в задачу О.|-РЮКЗАК, По данному семейству Р, состоящему из и трехэлементных множеств, мы построим такие целые числа с„..., с„и К, что среди с„..., с„можно выбрать подмножество с суммой К тогда и только тогда, когда в Р существует семейство, образующее точное покрытие основного множества 5=(и„..., и„„).
Можно представлять себе все множества из Р как двоичные век. торы длины Згп; например, (ио и„, и«) и (и.„и,, и„) принимают соответственно вид 100011 и 010!01. Будем интерпретировать эти двоичные векторы как ислыг числа, записанны; в системе с основа. нием (а+1). Другими словами, множеству 5, соответствует целое число с!='Ь'««, (а+!)' ', Кроме того, пусть К вЂ” целое число, соответствующее ! !...1: зт К= Х (и+1)'. Утверждается, что в Р существует подсемейство, точно покрывающее (и„., .,и«„,) в том и только в том случае, если среди сз существует подмножество с суммой К Докажем достаточность. Предположим, что существует такое множество 5«:-(1, 2,..., и), что ~нас!=К Вычисляя эту сумму в системе счисления с основанием и+1, замечаем, что ~ слагаемых встречаются только разряды О и 1 и, кроме того, число слагаемых меньше, чем основание а+1.
Следовательно, при ~яком сложении нет «переносов«. Поэтому если ~„,с,=К, то это означаез, что в каждой из Зт позиций существует ровно одна единица или, другими словами, что подсемейство С=(5,: 1Е5) точно покрывает (и„и„, и„„,). Докажем теперь необходимогдпь. Если С вЂ” точное покрытие /о.7. Еще несколько 77Р-полках эооач множества (и„..., и, ), то сразу же получаем, что ~зв, с = =К. Этим завершается доказательство, (1 Можно показать также, что задача 0-1-РЮКЗАК А/Р-полна даже тогда, когда К выбирается равным ~„",с/72.
Эта задача более известна как РАЗБИЕНИЕ Для данных целых чисел с„..., с„выяснить, существует ли такое подмножество Зс:-(1, 2,..., и), что ~,,с/ — — ~.® с/. /'е Ь //й5 Следствие 1. Задача РАЗБИЕНИЕ НР-полна. Доказа/цельс///во. Преобразуем полиномиально задачу 0-1-РЮКЗАК в задачу РАЗБИЕНИЕ. Пусть дана произвольная индивидуальная задача с„..., с„, К для задачи 0-1-РЮКЗАК. Построим следующую индивидуальную задачу РАЗБИЕНИЕ: с„..., с„, с„„=2М, сн,е=ЗМ вЂ” 2К, где М= У',с ) К. Утверждается, что в множестве (1, 2... п) существует подмножество 3, такое, что ~'ч.нс/=К, тогда и только тогда, когда в множестве (1, 2, ..., и+2) существует подмножество Б', такое, что ~~з ~с/ = ~/ с/.
ыв /лв Докажем достаточность. В любом допустимом разбиении 3' множества (с,, ..., с„„) числа с„„, и с„+е должны быть разделены, так как их сумма 5М вЂ” 2К )~ч"; /с . Поэтому для 3 = = 3' — (п+ 1, п+ 2) имеем ~/ с/+ с„„= /ез с +с„„ /ч в /~пь/. /ь2 Непосредственные вычисления показывают, что ~яр/евс/ — — К, Докажем теперь необходимость, Предположим, что ~/евс =К для некоторого Яя (1, 2, ..., п). Тогда ~~р„с/+ с„ь е = ~~р„с/+ сн.ь/ П /ез ма Следствие 2. Задача ЦЕЛОЧИСЛЕННЫЙ Р10КЗА К 11Р-полна, 13* Доказательство. Задача ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК входит в НР, так как она является частным случаем задачи ЦЛП, Для доказательства А/Р-полноты полиномиально преобразуем задачу 0-1-РЮКЗАК я задачу ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК. Пусть дана индивидуальная задача (с„..., с„, К) для задачи 0-1-РЮКЗАК.
Естес/венка, можно считать, что 1 с/~К для 1=-1,..., п Гз. /д. Д/Р-лолилге задачи и К)0. Построим индивидуальную задачу (/1„...,/(2„, 1) для задачи ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК, такую, что целые числа у„... ..., !/,„)О, для когорых ч~"/",г(/у/ — — 1., существуют тогда и только тогда, когда существуют х„...,х„Е (О, !г/, такие, что ~/; гс/х/=— = — К. Пусть М=2л(л+1)-К. Числа г(/ определим следующйм образом: ! Мл" +/И/+с,, если / < л (Мл+г+М/ в противном случае. Кроме того, положим Е=л Ми+!+~/ г/И/г РК. Этим завершается построение индивидуальной задачи ЦЕЛОЧИСЛЕННЫЙ РК)КЗАК по данной индивидуальной задаче 0-1-РЮКЗАК. Предположим, что построенная индивидуальная задача ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК имеет решение (у„..., уч„); другими словами, ~., г(уу, =-1. или 2Л Л Л М"' 2 ру+ ХМ'Ьг+ут..)+ Хс,ут= /=! /=! /=! Л = и М"' ! + 2', Мг+ К.
(15, 1) /=! Каждое у/ должно быть меньше, чем д М вЂ” < и+1 .= —. 2лК' Поэтому Х у,, р,+ут... Х с,р,СМ. Следовательно, в равенстве (!5.!) участвуют положительные линейные комбинации степеней большого целого числа М, все коэффициенты которых меньше, чем М.
Отсюда сразу же получаем, что коэффициенты, соответствующие одинаковым степеням М, должны быть равными. Поэтому 2Л Л Ху/=/г, уу+у,,л=-1 для всех /' и Хс,уу=Ф. /л! /=! Первые два равенства показывают, что для всех 1' ровно одно из чисел у/, уу,„должно быть равно 1, а другое должно быть равно О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
