Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 76
Текст из файла (страница 76)
Поэтому третье равенство показывает, что (уг,..., у„) — решение исходной 0-!-задачи, Обратно, по решению (х„, хл ) индивидуальной задачи 0-1-Р!ОКЗАК можно построить решение (у„, уг„) для задачи ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК, положив д/=-х;, 1==1,, и, и г//=.! — хг „, 1=-л+1, ..., 2/г. Поэтому построенная индивидуаль- 389 ная задача ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК имеет решение тогда и только тогда, когда имеет решение исходная индивидуальная задача 0-1.РЮКЗАК Следовательно, задача ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК А(Р-полна. Задачи 1. Сформулируйте задачу о максимальном паросочегании для взвешенных графов как задачу оптимизации, описав соответствующие алгоритмы бг и ыуы 2. Докажите, что если бы у нас был полнномиальный алгоритм для аьжисления длины кратчайшего обхода в ЗК, то у нас был бы полиномнальный алгоритм для нахождения кратчайшего обхода в ЗК, 3.
Рассмотрим следующую задачу. РЛСКРАСКА ГРАФА Для данных графа 6=(г', Е) и целого числа й выяснить, существует ли отображение уд )г жь (1, 2,..., 4), такое, что из (о, и1ЕЕ следУет х(о)ФХ(и). Покажите, что задача РАСКРЛСКЛ ГРЛФЛ входит в (УР, дав детальное описание удостоверения и алгоритма проверки удостоверения. 4. Приведите прямое доказательство того, что задача ЦЛП ЖР-полна, показав, что любая задача из )тР полиномиально преобразуется в задачу ЦЛП.
5. Покажите, что задача ВЫПОЛНИМОСТЬ МР.полна даже в том случае, если каждая переменная может появляться только один раз с отрицанием и один или два раза без отрицания (решение приведено в следующей главе), 6. Пусть Š— формула, состоягцая из дизъюнктов, содержащих по два литерала. Построил~ по Р ориентированный граф 0(Р)=(Х, А) следующим образом: х — зто множество переменных, появляющихся в Р, и их отрицаний. Дуга ()ч, Лз) ЕА тогда и только тогда, когда дизъюнкт ()ь,+йз) входит в Р.
а) Г1ока ките, что если х и х для некоторой переменной х входят в одну к ту же сильно сзятнпю компоненту (см. задачи 4 и 5 из гл. 9) орграфа 0(Р), то формула Р невыполнима. б') Докажите утверждение, обратное утверждению а). в) Приведите алгоритм со сложностью 0(л) для решения задачи ВЫПОЛНИМОСТЬ, ограниченной на формулы с двухбуквенными дизъюнктами. 7. Приведите явную конструкцию алгоритма проверки удостоверения (в соответствии с определением из 915.5), принимающего строки вида 00...0 ь 11...1 для л) !. зч В. Приведите последовательность команд в нашей модели алгоритмов проверки удостоверения для моделирования каждой из следующих более сложных команд. а) (: И и !Ьеп(п'; о'; Г) е!ае (о"; о', !"), б) 1: бо следующую команду мй(!е обозреваемый символ отличен от ь.
в) 1: йо 1о !'. О. Покажите, как предотвратить возможность иыхода головки в алгоритме проверки удостоверения за границы, выполняя подходящий первый сдвиг, а также предполагая, что с(х) имеет специальный вид. 10*. Покажите, что задача РАСКРЛСКЛ ГРАФА (задача 3] йР.полна. 11. Покажите, что следующие шесть задач Л(Р.полны (сравните (а) и (б) с задачей 12 из гл. !2). даны граф о=-()г, Е), множество Ес=р н целое число й. Спрашивается, существует ли в 0 такое остовиое дерево Т, что а) множество листьев дерева Т совпадает с !.; б) все листья дерева Т входят в !.; в) в Т имеется й листьев; г) в Т имеется не более й листьев; д*) в Т имеется не менее й листьев; е) степени всех вершин в Т не превосходят Д.
Гл. 15. Ь)Р-полнив задачи 390 (Указание: во всех случаях, кроме (д), полезно рассмотреть задачу ГАМИЛЬТОНОВ ПУТЬ.) 12*. Покажите, что следующие задачи )у Рчголны а) М1ЮЖЕСТВО ВЕРШИН. РАЗРЕЗАЮЩИХ КОНТУРЫ Даны орграф ()=((л, А) и целое число й Спрашивается, существует лп в Р такое подмножество Е, что (р! <Ь н орграф, получающийся из Гл выбрасыванием вершин, входящих в Е, ациклический. б) МНОЖЕСТВО ДУГ, РЛЗРЕЗЛЮЩИХ КОНТУРЫ Это такая же задача, как (а), за исключением того, что теперь Š— множество дуг. (Указание. в качестве исходной используйте задачу ВЕРШИННОЕ ПОКРЪ|ТИЕ ) 13*. Покажите, что следующая задача Фр.полив.
МАКСИМЛЛЬНЪ|Й РЛЗРЕЗ дань1 граф 6 —. ((л, Е) и целое число й. Спрашивается, существует ли такое разбиение множества () на подмножества г"л и Ра что в Е имеется не менее й ребер, соединяющих Ул и 14. |!окажите, что следующая зада и МР-полили СМЕШАННАЯ ЗАДАЧА О КИТАЙСКОМ ПОл|ТАЛЬОНЕ Даны смешанный граф Л1.—. (У, Е, А) (где Š— множество ребер и А — множество дуг на г), пелос число Е и веса ш Е() А -л Ел.
Спрашивается, существует ли в М маршрут, включающий в себя каждое ребро и каждую дугу, общий вес которого не превосходит 1., Сравните эту задачу с задачами 8 и 9 нз гл. 11. 13. Покажите, %то следующая задача Лгр-полна. МНОГОПРОДУКТОВ ЫЙ ПОТОК Даны орграф 0 — (Р, А) и 2Ь вершин зо зл..., за, (л, |м ., ., 1э из И Сира. шиваетси, суцлествуктгли непересекающиеся по вершинам ориентированные пути изз,в(,, излав|,, ..., иззлвга. 16*. а) Г|окажите, что следующин упрощенный вариант задачи квадратичного програииировинпя не проще, чем задача ВЫПОЛНИМОСТЬ. КВЛДРАТИЧНОЕ ПРОГРЛММИРОВАНИЕ Даны целочисленные матрицы А и () и целочисленный вектор Ь.
Требуется найти такой действительный вектор х, что к'()х = шах, Ак юк ь. б) Приведите полиномиальный алгоритм для задачи из п. (а) в частном случае, когда ллатрица О положительно определена (Указание. воспользуйтесь алгоритмом эллипсоидов из 4 8.7 ) 17. Интересным частным случаем ЗК является геометрический (или евклидов) случай, в котором даны л точек иа плоскости с целочисленными координатами и требуется найти кратчайший обход при условии, что йΠ— евклидова расстояние рг(х,— х,)л+((гг — рт)'. а) Пусть этот случай ЗК сформулирован как задача распознавания, называемая ЕЗК.
Объясните, почему непросто доказать, что ЕЗК~ МР. (Указание вычислите длину периметра приведенного ниже треугольника с пятью, а затем семью значащими разрвдамн.) (5, 9) (-10, (О, О) Коммен«порка и ссылка б') Положим бг ='Ь йс(хг — х )'+(уг — у )з ). Покажите, что в этом случая задача ЕЗК 74Р-полна. 18. Рассмотрим задачу нахождения кратчайцзего пути из з в 1 во взвешенном орграфе при условии, что допускаются отрицательные веса (см.
гл. 6). а) Покажите, что для этой задачи имеется полиномиальный алгоритм, если известно, что в графе не существует циклов с отрицательным суммарным весом. б) Покажите, что без этого ограничения задача является ДГР-полной. (Ука. аание: используйте ЗК.) 19. Следующая заметка была опубликована и «Ньзо-Парк таймс» 27 ноября !979 г Для каждого утверждения определите, если возможно, является лн оно а) истинным, б) ложным, в) вводящим в заблуждение, г) эквивалентным хорошо известной гипотезе, решение которой, возможно, не была известно -ну Брауну. Об одном подходе я трудным задачам Хотя практическая применимосзь нового метода Леонида Х зчняна вызывает споры среди мазематиков, нее сходятся ао мнении, что зто важное теоретическое достижение. Многие полагают, что метод Хачияна позволяет решать на ЭВМ зак называемые задачи «коммивояжера».
Такие задачи относятея к разряду наиболее труднорешаемых задач математики. В них, в частности, требуется найти кратчайший маршрут, прн котором коммивояжер мог бы посетить некоторое число городов, не посещая дважды один и тоз же город. Каждый раз, когда н маршруту добавляется новый город, задача значительно усложняезгя Используя систему линейного программирования, нужно нхй~и из болыього числа уравнений очень большое число переменных.
В неко~орый момент система так усложняезся, что вычислительной машине для нахох.;гния решения потребовались бы миллиарды лет. В прошлом задачи «коммивояжера», в том числе и задача зффектявного со. ставлення расписанкя для экипажей самолетов или штата медицинских «есг«р, решалигь на ЭВМ с использованием симплекс-метода, предложенного Джорджем Б. Данцигом из Станфордского университета. Как правило, снмплекс-метод работает хорошо, однако он не гарантирует, что после определенного числа шагов вычислительной машины будет найден отвез. Подход Хачияна позволяет с самого начала сказать, будет ли задача разрешена за данное число шагов.
Двое станфордских математиков ужв примеиилн метод Хачияна в программе для карманного иалькулятора. При помощи этой программы удалось реши гь задачи, которые невозможно было бы решить аналогичной программой с симплекс. методом. Подход Хачияна, если его сформулировать в математических терминах, использует уравнения для порождения воображаемых эллипсоидов, содержащих ответ внутри себя, тогда как в симплекс-методе ответ представляется пересеченинми граней многогранников. Чем меньше становятся эллипсоиды, тем более точный ответ имеется в нашем распоряжении. Малькольм У.
Браун © 1979 Ьу 1Ье )(пн «Уогй Т!вш Соврапу. Перепечатано о разрешения Комментарии и ссылки Следующие работы — одни из самых ранних работ, связанных с классами Р, УР и близкими понятиями. [Со] СоЬЬав А. ТЬе !п1г!пз!с Соврц1а1юпа) 01!!!сц11у о) Ецпснопз, рр. 24 — ЗО зп Ргос. 1964 1п(. Сопйгезз 1ог Еой)с Ме!Ьобо(ойу апб РЬ!1. о1 Зс(епге, еб. У. Ваг.Н61е(. Авз(егбав: Ыог!Ь Но!)апб, 1964 (Е81[ Ебвопбз д.
Ра((зз, Тгееь апб Г!озуегз, Сапад. 3 Майа 17 (!ОЬ81, 449 — 467. [Ег!2[ Ебгпопбз з. М!п)пшв РагЕНюп о1 а Ма!го(б зп )пберепдеи! ЗаЬ«ейь 3 Вез, ИВЗ, 69В (1975), 67 — 72. Гл. !5. Л(Р-полные задачи В последних двух статьях Эдмондс неформально определяет классы Р и Л(Р и высказываег гипотезу, что РФМР и, более того, что ЗК~ АР— Р.
Метод сведения, Гез временных оценок, хорошо известен в теории вычислений с 30.х годов нашего столетия. 1|олииомиальные относительно времени сведения использовались также в комбинаторной оптимизации. но только для демонстрации того, что некоторая задача проста, а не сложна. Одно нз первых использований сведения в др)гом направлении имеется в работе [Г)ВВ) Оапшгй О.
В., В|ацпег %. О., йао М. Я. АП ЗЬог|ез1 Вон1ез 1гогп а Ргхед Ог|дю .п а Огарц, рр. 85 — 90 )п ТЬеогу о1 Огарйж Ап |п1егпа|юпа| Зутроэ)нш. Мех г'огй: Оогбоп й ВгеасЬ, 1пс., !967. Теория Лгр-полноты восходит к статье [Спой) Соо!г 5. А. ТЬе Согпр|ехйу о1 ТЬеогет Ргошпй Ргосеснгеэ, Ргос. Згб АСМ Бушр. оп 1Ье Т|геогу о1 СогпрцВпй, АСМ (1971), 15! — 158. (Имеется перевгд; Кук С. А. Сложность процедур вывода теорем.— В сбл Кибернетический сборник, новая серия, аып. 12.— Мл Мир, !975, с. 5 — 15[, где были доказаны теоремы 15.1 и 15,2. Однако богатство следствий' из работы Кука и ее близкая связь с комбянаторной оптимизацией стали очевидными после классической работы Карпа: [Ка|! Кагр )!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
