Алгоритмы - построение и анализ (1021735), страница 236
Текст из файла (страница 236)
Включаются также ребра, содержащиеся в этих структурных элементах, как показано на рис. 34.15б-г, в зависимости от того, покрывается ли ребро одним или двумя вершинами множества Ъ'". Гамильтонов цикл также включает в себя ребра ((аз, [из,и-,1]): 1 < з < ЦО 0 ((л;+м ~из, и. ~ ', 6] ): 1 < 7' ( Й вЂ” 1) 0 "(( [- ."'" '"" 6]И Ознакомившись с рис. 34.16, читатель может убедиться, что эти ребра действительно образуют цикл. Этот цикл начинается в вершине лт, проходит через все структурные элементы, соответствующие ребрам, инцидентным вершине иц затем направляется к вершине из, проходит через все структурные элементы, соответствующие ребрам, инцидентным вершине из, и т.д., пока снова не вернется к вершине л1.
Каждый структурный элемент проходится однократно или дважды, в зависимости от того, одна или две вершины множества Ъ'* покрывают соответствующее ему ребро. Поскольку 1г" — вершинное покрытие графа С, каждое ребро из множества Е инцидентно некоторой вершине множества Ъ'", поэтому цикл проходит через все вершины каждого структурного элемента графа С'.
Поскольку он также проходит через все переключающие вершины, то этот цикл— гамильтонов. зтехнически определение цикла формулируется в терминах вершин, а не ребер (см, раздел Б.4). Для ясности здесь зти обозначения видоизменяются, а гамильтонов цикл определяется в терминах ребер. Часть Ч11. Избранные темы 113Е Проведем рассуждения в обратном направлении. Предположим, что граф С' = = (Ъ", Е') содержит гамильтонов цикл С С Е'. Утверждается, что множество Ъ" = (иЕ У: (в;, ~и,и(11,1]) Е С для некоторого 1 < у < Й~ (34.4) является вершинным покрытием графа С. Чтобы убедиться, что это действительно так, разобьем цикл С на максимальные пути, которые начинаются в некоторой переключающей вершине в,, проходят через ребро (в;, '(и, и(1),11) для некоторой вершины и Е к' н оканчиваются в переключающей вершине в, не пересекая при этом никакие другие переключающие вершины.
Назовем каждый таюй путь "покрывающим". По способу построения графа С', каждый покрывающий путь должен начинаться в некоторой вершине во включать в себя ребро (в,, (и, и(~1, 1~ ) для некоторой вершины и Е Р, проходить через все структурные элементы, соответствующие ребрам из множества Е, инцидентным вершине и, и оканчиваться в некоторой переключающей вершине в .. Обозначим такой покрывающий путь как р„и, в соответствии с уравнением (34.4), включим вершину и в множество Ъ". Любой структурный элемент, через который проходит путь р„, должен быть структурным элементом Иг„„или структурным элементом И~„„для некоторой вершины и й Ъ'. О каждом структурном элементе, через юторый проходит путь р„, можно сказать, что по его вершинам проходит один или два покрывающих пути.
Если такой покрывающий путь один, то ребро (и, и) е Е покрывается в графе С вершиной и. Если же через структурный элемент проходят два пути, то олин из них, очевидно, путь р„, а другой должен быть путем р„. Из этого следует, что и е Р'*, и ребро (и, и) е Е покрывается и вершиной и, и вершиной и. Поскольку все вершины из каждого структурного элемента посещаются некоторым покрывающим путем, видно, что каждое ребро из множества Е покрывается некоторой вершиной из множества Ъ'*. а 34.5.4 Задача о коммивояжере В задаче о коммивояжере (1гаче1шд-за1езшап ргоЫеш), которая тесно связана с задачей о гамильтоновом цикле, коммивояжер должен посетить и городов. Моделируя задачу в виде полного графа с и вершинами, можно сказать, что коммивояжеру нужно совершитыиур (1опг), или гамильтонов цикл, посетив каждый город ровно по одному разу и завершив путешествие в том же городе, из которого он выехал.
С каждым переездом из города г в город з связана неюторая стоимость с(г,у), выражающаяся целым числом, и коммивояжеру нужно совершить тур таким образом, чтобы общая стоимость (т.е. сумма стоимостей всех переездов) была минимальной. Например, на рис. 34.17 изображен самый дешевый тур (и, и, и, х, и), стоимость которого равна 7. Вот как выглядит формальный язык Глава 34.
МР-полнота 1139 Рнс. 34.17. Экземпляр задачи о коммивояжере; выделенные серым цветом ребра представляют самый дешевый тур, стоимость которого равна 7 для соответствующей задачи принятия решения: ТБР = ((С, с, й): С = (У, Е) — полный граф, с — функция У х У -+ Е, гс е Е и С содержит тур коммивояжера со стоимостью, не превышающей Ц. Согласно сформулированной ниже теореме, существование быстрого алгоритма для решения задачи о коммивояжере маловероятно. Теорема 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 согласно предположению, ни одно подвыражение не содержит одновременно и х;, и х;, и хотя бы один из этих литералов входит в одно из выражений в скобках. Поэтому должно существовать какое-то подвыражение С, благодаря которому числа те и п,' различаются. ° Каждому подвыражению С в множестве Я сопоставляются два целых числа л и л'. Каждое из них содержит нули в разрядах, метки которых отличаются от С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
