(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) (1186152), страница 20
Текст из файла (страница 20)
ТОЧНОЕ ПОКРЫТИЕ ЧЕТЫРЕХЭЛЕМЕНТНЫМИ МНОЖЕСТВАМИУСЛОВИЕ Задано конечное множество X , (X| = 4<?, целое число q исемейство С четырехэлементяых подмножеств множества X,ВОПРОС, Существует ли подсемейство С' е . С, такое, что каждый элемент из X принадлежит в точности одному элементу из С'?8. ДОМИНИРУЮЩЕЕ МНОЖЕСТВОУСЛОВИЕ. Заданы граф(У, Е } и целое число К Ka£\V\ВОПРОС. Существует лк такое подмножестве P 's У ’что 11"!< /< икаждая вершина v e V W > соединена ребром по крайней мере с'однойвершиной из V'}0. ДЕРЕВО ШТЕЙНЕРАУСЛОВИЕ.
Заданы граф О — (V, £), подмножество S s | / « положительное целое число А' е j F| — J,ВОПРОС. Существует лк поддерево в О, содержащее асе вершины из Rи имеющее не йолее К ребер?Ш. НЕЭКВИВАЛЕНТНОСТЬ РЕГУЛЯРНЫХ ВЫРАЖЕНИЙ,НЕ СОДЕРЖАЩИХ ЗВЕЗДОЧЕКУСЛОВИЕ. Заданы дна не содержащие зводажк регулярных аыпажешж С| н В г в конечном алфавите Г. Такое имрпжиню определяетсяследующим образом: (!) любой символ сг алфавита 2 есть не содержащее звездочек регулярнее выражение. (2) «ела m и в*— два не содержащие звездочек регулярных выражения, то и слова е(#е 11 {*(V «а) та?же не-содержащие авездойек регулярнйё' вйрШМия.ВОПРОС' Верно лк, что Ё , и Ег представляют различные языки в алфавите Е? (Язык, представляемый, символом ,аез2. есть {о},-а если ei,i< «апредставляют соответственно язык» Ц'_я U, то «»е» представляет язык{*у, * е= /.(, у © U ), a (si V «г) представляет язык U U is.)Метод построения компонентИ) РАСЩЕПЛЕНИЕ'МНОЖЕСТВАУСЛОВИЕ.
Задано семейство С подмножеств конечного множества S.ВОПРОС, Существует ли разбиение 5 ив две части $ ( и S i, такое, чтоmi одно подмножество из С ке содержится ни в S f ни я S»?•У к азан и е, -Использовать-3-ВЫП.12. РАЗБИЕНИЕ НА ПУТИ ДЛИНЫ 2УСЛОВИЕ. Золам граф О *- (V , Е ), где [Я ! = 3<? д.чя некоторого целогоположительного числа ц.ВОПРОС. Существует ли разбиениеV на <? [«пересекающихся подмножеств Vi, V i,Vt, ио три вершины в каждом, такое, что для всех(0;uj, Ofisj, u(j 3j} 110 крайней мере дяа из трех ребер {о/цр 0{(2)}.{ ° М П ’ 0 i (3 i} * { в щзр <,< и }Указание,принадлежат£?Использовать 3-С,АППЕНДИКС: ПРИМЕНЕНИЕ ТЕОРИИ NP-ПОЛНОТЫДЛЯ АНАЛИЗА ЗАДАЧПерейдем к использованию теории NP-полноты дляанализа задач.
Из рассуждений, приведенных ранее, следует,что, встретившись с новой задачей, естественно сначалазадать вопрос: «Можно ли рассматриваемую задачу решитьполиномиальным алгоритмом?» Если ответ на этот вопросоказывается положительным, то с точки зрения теории NPполноты ничего большего о задаче сказать нельзя.Дальнейшие усилия мы можем сконцентрировать на поискекак можно более эффективных полиномиальных алгоритмов.Но если для решения задачи не известно полиномиальногоалгоритма, естественно возникает второй вопрос: «Верно ли,что рассматриваемая задача NP-полна?»Чтобы поставленный вопрос имел смысл, предположим,что рассматриваемая задача сформулирована как задачараспознавания и что она принадлежит классу NP.
В некоторыхслучаях легко устанавливается полиномиальная разрешимостьинтересующей нас задачи, в других же оказывается очевиднойее NP-полнота. Если задача оказалась NP-полной, то этоявляется сильным аргументом в пользу того, что ее нельзярешить за полиномиальное время. В большинстве случаев,однако, найти ответ на каждый из поставленных вопросовдовольно трудно. Обычно совсем не очевидно, что задачаразрешима за полиномиальное время или что она NP-полна, атребуется некоторая работа для выяснения, какая из этих двухвозможностей в действительности реализуется (в том случае,конечно, если реализуется хотя бы одна из них).
Напомним,что ранее говорилось о том, что если P^NP, то в классе NPсуществуют задачи, которые неразрешимы за полиномиальноевремя и не NP-полны). Как в этом случае выяснить сложностьрассматриваемой задачи?Если интуитивно мы склоняемся в пользу одной извозможностей, то очень соблазнительно сконцентрироватьусилия в этом направлении. Однако в подобных вопросахинтуиция оказывается особенно обманчивой, ибо зачастуюзадачи, разрешимые за полиномиальное время, оченьнезначительно отличаются от NP-полных задач. Например, мывидели, что задачи 3-ВЫПОЛНИМОСТЬ (3-ВЫП) иТРЕХМЕРНОЕ СОЧЕТАНИЕ (3-С) NP-полны, а близкиезадачи2-ВЫПОЛНИМОСТЬиПАРОСОЧЕТАНИЕразрешимы за полиномиальное время. На рис. 6.4 указанонесколько других пар задач, одна из которых принадлежитклассу Р, а другая NP-полна.Наша интуиция основана на опыте работы с близкимизадачами.
По этой причине мы серьезно рискуем сбиться справильного пути, если позволим себе, доверяясь интуиции,сконцентрироватьсянаисследованиитолькооднойвозможности.Таким образом, при анализе задач лучше пользоватьсядвусторонним подходом. Пытаясь с одной стороны доказатьNP-полноту задачи, одновременно целесообразно искатьполиномиальный алгоритм ее решения. Конечно, в каждыйданный момент мы выбираем направление исследованийисходя из того, что представляется нам перспективнее, нонужно быть готовым сменить направление исследований. Вдействительности, по мере того как мы будем переходить отодного направления к другому и обратно, оба направления,взаимодействуя друг с другом, сливаются в единое целое.Неудачи в доказательстве NP-полноты задачи могут породитьидею алгоритма ее решения, а неудачи в построенииалгоритма могут указать путь к доказательству NP-полнотызадачи.
Любые частичные результаты, полученные в процессеподобных исследований, особенно результаты о «нормальнойформе» решений, могут оказаться в равной степениполезными как для доказательства NP-полноты задачи, так идля построения эффективного алгоритма ее решения.Само собой разумеется, что успешное применение напрактике такого двустороннего подхода требует отисследователя мастерства как в отыскании доказательств NPполноты, так и в построении полиномиальных алгоритмов. Ометодах доказательства NP-полноты было достаточно многосказано выше. Мы сосредоточим внимание на следующемвопросе: если доказана NP-полнота некоторой задачи (чтобывает очень часто), то как использовать рассмотренныйвыше двусторонний подход для более глубокого анализа згойзадачи?Сначала обсудим вопрос, каким образом можно глубжепрозондировать сложность NP-полной задачи, изучая ееподзадачи и пытаясь разграничить полиномиально разрешимые и NP-полные подзадачи.
Затем рассмотрим подзадачиспециального вида, часто заслуживающие внимания в техслучаях, когда в исходной задаче существенную роль играютцелые числа. Такой подход приводит к понятиям «алгоритм спсевдополиномиальным временем работы» и «сильная NPполнота», а также к дополнению списка основных NP-полныхзадач седьмой задачей. Обсудим и вопрос использованияподзадач при изучении влияния на сложность задачи ееиндивидуальных параметров (а не только общей «длинывхода»).К^-полныерграф£), длины f(e)€sZ + дляпсех*<г£' выделенные всршнж4a, b<sV и положительное целоечисло В.ВОПРОС.
Существует ли в 0простой путь из л в Ь., имеющийдлину «С более В ?САМЫЙ ДЛИННЫЙ ПУТЬМЕЖДУ ДВУМЯ ВЕРШИНАМИУСЛОВИЕ. Заданы: граф О**» (У,В), длины /(а )<£*2т дяя всехо с? Ё, выделенные вершины о,t i e ^ н* положительное целоечисло В .ВОПРОС. Существует ли в Опростой путь кэ « в Ь, имеющийдлину ие менее S?РЁвериое покры тиеУСЛОВИЕ. Заданы граф Q~(V>Я) и положительное целое число/Г.ВОПРОС, Сушеетнувт ли иодмиржестпо В г £ Ячтакое. что | В* | Ки для каждой вершины uc= Vимеется такое ребро е «= К', чтонее?ВЕРШИННОЕ ПОКРЫТИЕУСЛОВИЕ. Заданы граф 0 — (V,К) н положительное целое число К.ВОПРОС. Существует ли подмножествоP ' s V, такое, что| V '| <; К а Для любого ребрае «в В имеется тлкая вершинао е V', что о шв ?ТРАНЗИТИВНАЯ РЕДУКЦИЯУСЛОВИЕ.
Заданы ориентированный граф (?«*{{/, Л) я положительное целое число д.ВОПРОС. Существует лк подмножество A' s V Х У, такое, что| A' f * ^t f и для всех «, pcs Уграф G* «* (К, АП содержит путькз « п о тогда в только тогда,когда граф О содержит такойпуть?МИНИМАЛЬНЫЙ 9КДИНАЛЕИТНЫЙ ОРИЕНТИРОВАННЫЙ ГРАФУСЛОВИЕ. Заданы ориентированный граф 6*«{У , А) и положительное целое число К.ВОПРОС. Существует ли подмножество А' s* А ,такое» что(А'{.<(К и'для всех и » С б ?граф 0 ’ — (У, А% содержит путьно и a v тогда и только тогда,когда граф G содержит такойпуть?РАСПИСАНИЕ ДЛЯ ПРЯМОГОДЕРЕВА ЗАДАНИЙУСЛОВИЕ. Заданц; множество Тзаданий с’' еднкнчиогг длительносгыо, директивный срок </(/)'« ЗЕ+дли каждой t щ Т, частичный порядок <- на множестве 7, отво*.снтсльио которого каждое заданиеимеет не более одного непосредственно следующего за ним, положительное целое число г/гВОПРОС; Можно ЛН составитьдля множества Т расписание на mпроцессорах, на каждом из которых задания выполняются согласнозаданному частичному, порядку,так что осе директивные срокиОк9жY T C я выполнен» ы.ми?РАСПИСАНИЕ ДЛЯ ОБРАТНОГО ДЕРЕВА ЗАДАНИИУСЛОВИЕ, Задании Мчфкдство.Гзаданий с'' сДиТ|ичкЬп' длительно^стмо, дврективны# срок &{Q e 'Z +для каждого 1 ее Т, - частичныйпорядок -<• ид множестве 7\ .относительно которого каждое заданиеимеет не более,одного непосредственного предшественника, положительное целое число Hi.ВОПРОС.
' МбжнО' ли состайнтьдля множества Г расписание на mпроцессорах, на каждом пз которых задания выполнятся согласно заданному частичному по--,рядку, так что все директивныес р о к и окажутся выполненная и?__к ратчайш ийпутьм еж дуД В У М Я ВЕРШИНАМИУсловие.Зядаш:Рис. 6.4 Пары близких задач, одна из которых принадлежит классу Р,а другая NP-полна.АНАЛИЗ ПОДЗАДАЧПредположим, нам удалось доказать, что интересующаянас задача NP-полна. При этом мы получаем полные ответына оба вопроса, с которых начинался анализ вопросов.
Однакоэто лишь первый шаг на пути решения задачи. Задача, котороймы занимаемся, часто получается как идеализация менеепривлекательной прикладной задачи и некоторые детали,опущенные в процессе идеализации, могут изменить задачутак, что она станет разрешимой за полиномиальное время.Даже если это не так, у задачи могут иметься некоторыеважные частные подзадачи, которые могут быть решены заполиномиальное время. Возможно, что индивидуальныезадачи,плохоподдающиесярешению,встречаютсяотносительно редко и имеют легко выявляемые особенности,позволяющие заблаговременно опознать такие задачи. Этивозможности могут быть изучены с помощью анализаподзадач интересующей нас задачи.Согласно принятому нами описанию массовых задачраспознавания, каждая из них состоит из двух частей:множества D всех индивидуальных задач и множества Yиндивидуальных задач из D с ответом «да».
Подзадачейзадачи П = (D.Y) называется такая задача П -(Z)', Г), что f l 'c f lи 7'=JT\D', т.е. ГГ есть подзадача задачи П, если в нейсформулирован тот же вопрос, что и в П, но только наподмножестве множества индивидуальных задач из П.Таким образом, подзадачи возникают всякий раз,когда на множество индивидуальных задач налагаютсядополнительные ограничения. В задачах из теории графов,например, можно ограничиваться индивидуальными задачами,в которых графы планарны, или двудольны, или ацикличны,или обладают некоторыми из этих свойств одновременно. Взадачах, содержащих множества, можно ограничитьсяиндивидуальными задачами, в которых мощность множествне превосходит заданной величины, или задачами, в которыхвсе элементы содержатся не более чем в ограниченном числемножеств.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
