Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 79
Текст из файла (страница 79)
Это невозможно, если Р чы НР. П Таким образом, доказательство того, что некоторая задача сильно (УР-полна, исключает — с учетом гипотезы Р ~ ЧР— существование не только полиномиальных алгоричмов, но и псевдополиномиальиых алгоритмов. В ~аких задачах, как КЛИКА и ГАМИЛЬТОНОВ ЦИКЛ, в которых числа играют минимальную роль, этот более сильный вариант ФР-полноты появляется естественно.
Любопьпно, однако, чго существуют некоторые сильно й(Р-полные задачи, в которых целые числа играют центральную роль. Примером является следующая задача. 3-РАЗБИЕНИЕ Ланы Зп целых чисел (с„..., сз„). Спрашивается, существует ли такое разбиение этих целых чисел иа и троек Т„..., Т„, что Х... с!=~., с, для всех ! г еЧ Гл. !б. Ео<е об гс'Р-полно<по 402 Эта задача сильно !ч'Р-полна (см, залачу 4). В заключение этого параграфа мы должны принести извинение фундамен<алистам Наше «определение> <) ункции ппп;(!) для индивидуальной задачи ! было всего лишь указиниел< на то, что эта величина имеет ипрейеченное зниче<ше. Формально гоег! я, вход ! будет просто поспел< вательностью символов, и е общем сл) чае будет нелегко обнаруя:ить е ией части, представляющие целыь числа. Это, однако, не умепыпает важности введенных е этом параграфе понятий и доказанных резулыатов.
Лело в том, что наши результаты ос<аются справедливыми, если в ка есзее функции ппп< взять любие фиктприоинни (, ля данной задачи) < олннсхшельно вычислимое отображение множества инзн«сил<альных задач е мноя,ссзео полож<мельных целых ч<нс и, удое. е<еоршон,се углоеик< гпп<(!)=:. (2' '<. Чем «разумного бузе< наше опрслеленпе «ункцпп пспп лля данной задачи, тем большее значенце будет име<ь утверждение теоремы 16.4. 16.3 Частные случай и обоб !ения Л(Р-понных задач В этом параграфе мы подробно остановимся яа <ледующем очевидном утверя денни: чем бил< е общей яел петен задача, шеи труднее ее реп<шил.
Мы увпдих, <о это )теерждепие .о>кез быть очень полезным для локаза<ельстев резулглатов об Л<Р-пол<соте, В качестве другой его плл<сс<раппе мы покажем, что е некоторых случаях ограниченные ползалачи лля Л'Р-и< лных залач ах<дат в Р. 1.1акгпец, привелем примеры, в когорых частные случаи <ч'Р-полс<ых задач остаются трудными, несмотря на некоторые очень сильные ограничения, !6.3.1, Доказательство Л(Р-полноты сужением. Рассмотрим следующую задачу; МИНИМАЛЬНОГ ПОКРЫТИЕ Ланы семейство Р=5„..., 5, подмножеств конечного множества и пелое число !< и, Спра<ниеаегся, сущее<еуе< ли в Р .<акое подсемейство С, <олержащее (< множеств, что В з,«с5,—.(/.
! Какова сложность задачи МИ1 !ИМАЛЬНОЕ ПОКРЫТИЕй Легко видеть, что эта задача являе<с«ибиби(спиел: апачи ТОЧНОЕ ПОКРЫТИЕ 3-МНОЖ!=СТВАМИ, которая, как было показано в предыдущей главе, Л<Р-полна. Залача ТОЧНОГ Г1ОКРЫТИЕ 3- МНОЖ!лСТВЛМИ является всего лишь частным случаем задачи МИНГ!Л(АЛЬНОЕ ПО!:,РЫТИЕ, в котор<а<,'5,! — -3 для ! — — 1,...
...,и и й=)(/(<3. Следова<ельно, любую индивидуальную задачу ТОЧНОЕ ПОКРЫТИЕ 3-МГ!ОЖЕСТВАМИ мое:но тривиально преобразовать в индивидуальную задачу МИНИМАЛЬНОЕ ПО- 1й.й. Чиегиные случаи и абиаияения й'Р.иозныз задач 403 КРЫТИЕ. Таким образом, задача МИНИМАЛЬНОЕ ПОКРЫТИЕ А!Р-полна, так как она является обобщением АР-полной задачи. В качестве другого примера напомним, что мы доказали гчР- полноту задачи ОРИЕНТИРОВАННЪ|Й ! АМИЛЬТОНОВ ЦИКЛ, заметив просто, что она является обобщением неориентированной задачи ГАМИЛЬТОНОВ ЦИКЛ, Грубо говоря, это следует нз того, что в отношении гамильтоновых циклов неориентированные графы являются просто частными случаями орграфов, удовлетво„ряющими условию: если (и, о) ЕА, то и (и, и) Е А.
Аналогично, АСИММЕТРИЧНАЯ ЗК А'Р-полна, так как она является обобщением ЗК. Рассмотрим следующую задачу: ИЗОМОРФИЗМ ПОДГРАФУ Даны два графа 6 и 6 . Спрашивается, существует ли в 6 подграф, изоморфный (т. е, идентичный с точностью до перенумерации вершин) графу 6'. Эта задача Л'Р-полна, так как она в качестве частных случаев содержит задачи КЛИКА и ГАМИЛЬТОНОВ ЦИКЛ. Действительно, если 6' — полный граф с й вершинамн, получаем задачу КЛИКА. Если в качестве 6' берется гамилшонов цикл (т. е, связный граф с таким же числом вершин, как в 6, в котором степени всех вершин равны 2), то получаем задачу ГАМИ2!ЬТОНОВ ЦИКЛ.
Доказательство Г4Р-политы сужением не всегда так тривиально, как в рассм<лренных выше примерах. Рассмотрим, например, следующую задачу: ПОСТРОЕНИЕ НАДЕЖНОЙ СЕТИ Даны две симметричные (пх п)-матрицы, !бы! (матрица расстояний) и !гы! (мачриьа избыточносзи) и целое число А. Спрашивается, существует лп граф на и вершинах, стоимость козорого не превосходит 1, такой, что между 1-й и 1-и вершинами существует не менее гы непересекающихся по вершинам пу1ей. Покажем, что в действительности эта задача является обобщением задачи ГАМИЛЬТОНОВ ЦИКЛ.
Рассмотрим случай, в котором д„. равны либо 1, либо 2, ! г=п и гы —— -2 для всех 1 ~ 1. Тогда нетрудно понять, что единственным графом с и ребрамн, в котором между любыми двумя вершинами имеются два непересекающихся по вершинам пути, является цикл с и вершинами (что требует некоторого доказательства). Следовательно, этот частный случай задачи построения надежной сети имеет решение в том и только в том случае, если граф с и вершинами, в котором ребро ((, 1! присутствует тогда н только тогда, когда е(м= 1, гамильтонов.
Таким образом, задача ПОСТРОЕНИЕ НАДЕЖНОЙ СЕТИ является обобщением задачи ГАМИЛЬТОНОВ ЦИКЛ, и, следовательно, А'Р.полна. 16.3.2. Легкие частные случаи АГР-полных задач. Основным дидактически существенным моментом этого параграфа является 404 Гл. 16. Егце об 77Р-палногле то, что частные случаи Л Р-полных задач не обязоны быть трудньтлгн. Это соображение может быть очень важным на практике Предположим, что в практической ситуации нас интересует получение точных оптимальных решений для данной комбинаториой задачи оптимизации. К сожалению, мы вскоре осознаем, что эта задача Л)Р-полна и, счедовательио, нет надежды решать общую задачу эффективно.
Должны ли мы сдаться? Не сразу. Возможно (на самом деле вероятно), что мы оказались жертвами ненужной оби(ности — подобно многим исследователям, которые формулируют каждую дискретную задачу оптимизации в виде задачи целочисленного программирования, а каждую задачу упорядочения в виде ЗК лишь для того, чтобы отказаться от ее решения, как только они поймут, что для этих общих задач очень трудно найти точное решение Гораздо лучше формулировать задачи в наименее общем виде и пытаться использовать любые специальные свойства интересуюших нас индивидуальных задач. Например, если мы рассматриваем задачу о маршрутах, в которой участвуют графы, то может оказать. ся, что интересуюцтие нас графы обладают некоторыми приятными своиствами, такими, как п.танарность, ограниченные степени вер!нии и т.
д С другой стороны, при доказательстве ЛгР-полноты этой задачи, возможно, использова.чись — что часто бывает — сведения, в которых строятся графы, сильно непланариые и имеющие очень большие с~висни. Поэтому остается надежда, что существует эффективный алгоритм для решения данной задачи в частном случае, когда граф п.танарен и степени малы. Конечно, нельзя сказать, что Л!Р-полнота общей задачи в этом случае не имев~ никакого значения. Если такой результа~ доказан, то дело огмимистов — объяснить, как они надеются решить частный случай, используя его свойства.
Пример !6.2. Вспомним задачу КЛИКА, которая, как нам из. вестно, Л'Р-полна. Предположим, что мы рассматриваем задачу ПЛАНАРНАЯ КЛИКА, т. е. ее ограничение иа планарные графы. Теорема Куратовского (Еу) ') утверждает, что в планарном графе не може~ быть клик с пятью или более вершинами. Следовательно, максимальная клика в планарном графе 0= (!', Е) может иметь не более четырех вершин, и поэтому ее можно найти полным перебором за время О(!)7!').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
