Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 82
Текст из файла (страница 82)
Некоторые из них можно пай~и в задачах в конце этой ~лавы. Несколько сотен ~ЧР-полных задач содержится в книге Гэри и Лжоисона (ОД2!— наиболее полном собрании на сегодняшний день. Среди них имеется несколько задач оп~пмиззции, решение которых представляет большое практическое значение. Тот факт, что э~и задачи Л'Р-полны— вместе с широко распространенным и хорошо обоснованным мнением, что из этого следует труднорешзе»осзь,— привел многих исследователей к пересмотру их стра»егин подхода к этим задачам, Имеется несколько возможносзей, которые менее безнадежны, чем попытки решить УР-полную задачу оптимизации точно и эффективно.
Ниже мы приводим список основных возможностей, 1. )лриближеиные алгорагплга. Э»и алгоритмы порождают не оптимальные решения, а решения, отличающиеся от действительного оптимума заведомо не более чем на фиксированную долю этого оптимума. Этот подход и границы его возможностей мы изучим в следующей главе. 2. Вероятностные алгоришл~ьь Иногда оказывается возможным построи~ ь алгоритмы, которые очень часто относительно некоторого вероятностного распределения на индивидуальных задачах работают неплохо — в смысле качества получаемых решений илп затрачиваемого времени.
3. Частные случаи. В Э 16.3 мы видели, что интересные частные случаи г(Р-полной задачи могут быть простыми. Если нас интересую» только эти частные случаи, то тот факт, что общая задача й(Р- полна, более или менее несуществен. 4. Экгпоненциальнг«е алгоритмы. Такие алгоритмы могут, в конце концов, быть не слишком плохими. Мы уже показали, что псевдаполиномиальные алгоритмы (6 16.2) могут иногда хорошо работать на практике, несмотря на тот факт, что они, строго говоря, экспоненциальпы. Кроме того, некоторые методы поиска с экспоненциальной сложностью в худшем случае, такие, как метод вешвей и зраниц из гл. 18, можно успешно применять к индивидуальным задачам разумного размера.
5. Локальный поиск, Одним из наиболее успешных подходов к решению трудных комбинаторных задач является дискретный аналог «метода спуска», известный как локпльный (или окрестноггпный) поиск. Он будет рассмотрен в гл. 19. 6. Эвристики. Любой из описанных выше подходов без формальной гарантии хорошего поведения можно рассматривать как «эв- 414 Гл. !б. Еще об ИР-полноте ристику». Такие подходы, будучи неудовлетворительными с математической точки зрения, уверенно работают в практических ситуациях.
Задачи 1. Следующая задача является классической задачей распознавания. ПРОСТЫЕ ЧИСЛА Дано десятичное представление целого числа. Спрашиваетсн, является ли это число простым. а) Приведите алгоритм распознавания для задачи ПРОСТЫ Е ЧИСЛА. Какова сложность Вашего алгоритма) б) Покажите, что ПРОСТЫЕ ЧИСЛА ~ со-А'Р, в*) Покажите, что целое число п является простым тогда и только тогда, когда существует такое целое число а, что (1) ач э==1(люб л) н (Н) а(' ~)гпф((шоб и) для всех простых делителей Р числа и — 1.
г) Используя и, в), покагките, что ПРОСТЫЕ ЧИСЛА ~ НР, 2. Полиномиальное преобразование Т задачи А в задачу В называется сохра. ялюи(ил, если для любой индивид> альной задачи х задачи А в Т(х) имеется столь- ко же решений (т, е, разлн шых удостоверений с(Т(хйк сколько в х. Какие из преобразований, испол~зованных в доказательствах в предыдущей главе, явля- ются (нлн могут быть летно сделакы) сохраняюшимир 3*. Пусть т — прои гвольиое фиксированное целое число и т-ЦЛП вЂ” это задача ЦЛП, ограниченная на нндивнл) альные задачи с т уравнениями. Пока- жите, что для задачи т-ЦЛП суисс~пуст псевдополиномиальный алгоритм.
(Указание. Вспомните опенки из 4 (З.З.) 4. а) Приведите полиномиальное преобразование задачи 3-МЕРНОЕ СОЧЕ- ТАНИЕ в следующую задачу: 4-РАЗБИЕНИЕ Ланы 4л целых чисел (ст,, счо). Спрашивается, существует ли такое раз. биение этих целых чисел на и четверок (сг..., 11ч, что Х с =- ~, су для всех г, й) с .О,' г «Гэ г Получаемые прн этом преобразовании числа с1 должны удовлетворять неравен- ству су<р(п) для некоторого нолинска р б) Покажите, по задача З.РАЗБИЕНИЕ сильно ФР-полна. 6*. Покажите, что вопрос о том, имеется ли в планарном графе (р, Е) клика размера 4, может быть решен эа время 0())г)). 6 .
Рассмотри з следующий алгоргым для решения задачи МНОГОПРО- ЦЕССОРНОЕ РАСПИСАНИЕ в юм случае, когда отношение предшествования представляет собой аншнордеревх (т. е. степени исхода всех вершин, кроме корня, равны 1). 1) Каждому заданию приписываем приоритеш, равный его расстоянию от корня. 2) Распределяем гадания по интервалам времени и процессорам, выбирая на каждом шаге задания, все предшественники которых уже обработаны и кото- рые имеюз наибольший приоритет.
а) Покажите, что этот алгоритм корректно решает рассматриваемый частный случай за полнпомиальное время. б) Приведите пш~иномиальные алгоритмы для случаев, когда отношение предшесгвования является лесам нз антиорзеревьев, орлеревом и лесом из орде. ревьев.
7. Граф называется хордоеолп если все его циклы1ем гх, ..., оа) длины четыре илн Голее илгегот хорду, т. е. ребро (оь о.), где 1ы'=-1ш) (глоб й) Задачи 415 а) Покажите, чго съл) юасс (ртпургигпое) определение хордовых ~ рафов эквивалентно прнвгдгннопу выше Граф 6 —.(У, /.) янляшся хордовым е шм ь ~ольке в том случае, если б= =(Я, З) (пустой граФ), либо сущесгвуе~ ~зная нерп и. э ~ ~ У, что (~) окрас~ность вершины и (т. е. е и смежные ей вершины) образ)е клику и (Н) (рекурсивно) 6 — а есть хордовый граФ.
б) Покахките, по для хордовых графов зада ш РАСКРАСКА ГРАФА, НЕЗАВИСИМОЕ М1(ОЖЕСТВО и КЛИКА полиномцнльны 8. Пусть 6==(1', Е) — плзнарный ~ раф, и ~ ус~в l' — мпожес~во областей (грангй), нз которые плоское «изобрлжсппез графа б цс.пп плоскость Дзе грани графа б называются мемиыми, если пх пересечением является ляпин (но не точка). Графом, дзайстгснным к 6, называемся ~ рзф 6/з — 1р, Н], ~де )/и /з) ~ Н ~огда и только тогда, ко~ па /, и /з смежны (н графе оа пп у~ быть повторяющиеся ребра).
а) Сформулируй~с задачу ИАКСИМАЛЬ)1ЫЙ РАЗРЕЗ (задача 13 из гл. 15) для планаркого гр ~фэ 6 как задач) ~пш: задач ~ паросочетаниях в графе ба и ре. шите ее за пол~цюхщчлыюе время. б) Повторите и а) для гзвгшгяяо,о варпзптн гада ~и МАКСИМАЛЪНЫЙ РАЗРЕЗ.
9*. Покажите что (асимче~рнчпую) ЗК с рэссюяниямн, описанными вп, а] и б) задачи 13 из ~л 11, можно решит~ зз полиномизльное нремя. 10. Покажите, что (асимметрич~~ую) ЗК с неоз рипа телы ычи расстояниями д//, удовлетворяющими условию ~/, — -О, если /)/, моткно реши~ь за полинами. альное время.
11. Покажите, по задача о ~амильгг нов ~м цикл. длн плзнарных графов А/Р.полна. (Указание; вспомните рис, 15 9 в .нп азн сльствг теоремы 15.6. Все, что требуется показать,— это как позволить лпннцм А пересекаться. Рассмотрите следующую идею.) ,Р А Р с:."ф ) х' 12. Докажите методом сужения (равд. !6.3.2), что следующие задачи //Р. полны. а ГОМЕОМОРФИЗМ ПОДГРАФУ эны два ~рафа 6=(У, Е) и Н=-(0, Е).
Спрашивается, существует ли ~акое отобрэжепне й из 6 е У, что (1) из Ь(и)/.8(г) вьпекает и=и) (6) для каждого ребра (и. Ийр существует пусть из й(и) в д(а) в ~ рафе 6; (111) все зги пути не пересекаются по вершинам. (Указиние. см ГАЛ1ИЛЪТОНОВ ЦИКЛ.) Транзитивным замыканием орграфа 0=(У, А) называется орграф 0 Я=(У, А *), такой, что (и, т) ЪА* тогда и только тогда. когда в А существует путь из и в а (или и= е). б) ТРАНЗИТИВНОЕ СОКРАЩЕНИЕ ВЫЪРАСЫВАНИЕМ Даны орграф 0=(1', А) и целое число й Спрашивается, существует ли таной подграф Е=(У, В), что О*==/' и )В, 'Мlг. (Указание: см. ОРИЕНТИРОВАННЫЙ ГАЛ1ИЛЪТОНОВ ЦИКЛ.) в) ПРОТЫКАЮЩЕЕ МНОЖЕСТВО Даны семейство С= (Вт, ..., Зн) конечных мнгпкеств н целое число й.
Спрашивается, существует ли такое множество Н, что)Н) жй и Н П Я/~З для /= 1, ..., а. (Указание; см. ВЕР1ПИННОЕ ПОКРЫТИЕ.) 4!6 Гл. (б. Ещэ об ВР-нолноте г) ГАМИЛЬТОНОВЛ»<[ОСТРОГ)КА Даны граф В=(р, Е) и целое число Ф. Спрашивается, существует ли такое множество ребер В, что !В)~й и в графе (Ч, Ео В) имеется гамильтонов цикл. Комментарии и ссылки Идеи, обсуждавшиеся в ьх 16.2, взяты нз [С21! Сагеу Л1 К., Зойпзоп О. 5. <Игопй Л$Р-сотр!е)сает генг!Пп МоПчаПоп, Ехапгр)ез апг) 1гпрПса()опз, 3. ЛСМ, 25 (1978), 499 — 508.
Теорема 16.8 взята из [3 К! йо1$пзоп О. В., Казйбап 5. О, Ео»чег Вонпбз 1ог Зе1есНоп )п Х+1' аггб ойег Мн!НзеЬь 3 АСМ, 25 (!978), 556 — 570. Дальнейшее обсуждение вопросов, упомянутых в 4 16.4, можно найти в гл. <За пределами класса АгР-полных задач» книги [С32! Сагеу М. К., )ойпзоп Р. 5. Соптрн1егз апб )п1гас1аЬг)Иу: А йные 1о йе йеогу о1 АГР-со<яр)е1епезз. 5ап Ггапсмсо.
УЧ. Н. Ггеегпап 4< Сагпрапу, 1979. [Имеется перевод' Гэри М., Джонсон Д. Вычислительные машины и труднорешэемые задачи.— Мл Мир, 1982.! Задача $(г) прйнадлежит Прет<у: [Рг[ Рга(1 Ч. К. Ечеху Ргнпе Наз а 5нссгпс1 Сег()Пса(е, Л, 51ЛМ Сотр., 4(1975), 214 — 270. Сохраняющие сведения введены в работах [еы! сын»оп 2, Оп 5оте Сеп1<а! РгоЫегпз !п Сотрп1аПопа) Согпр!ехИу (неопубликованная диссертация, ГогпеП 1)пгчсгн1у, 1977). [Ча)! ЧаИап1 й С. А ро1упопна) Кеон1юп о1 5а1ИПаЬ$)иу (о НаппИоп|ап С1гснцз йа1 Ргезегчез йе ИшпЬег о1 5о!н(юпз (нс опубликовано). Используя такие свелсния, Валиант развил теорию сложности для перечисли- тельных задач (т. е. задач, связанных с лодгчетолг решений), параллельную соответствующим теориям для задач распознавания и оптимизации.
См. [Чай! Чайап1 1. С. ТЬе Сотр!ехцу о1 Еншпега1юп апб геПаЬПИу РгоЫегпз, Керог1 СЗК-15-77, (Угг)ч. о1 Еб[пйнгйй, 1977. Задача 3 взята нз [Ра) Рараснпп(ион С. Н. Оп йе Сотр)ехИу о1 )п1едег Ргойгаттшй, М. 1. Т, ЕаЬ. 1ог Сотрыег Зс)епсе, ТА1-152, 1980. Также 3. ЛСМ, 28(1981), Ио. 4, 765 — 768. Задача 4 взята из [С32!. Задача 6 — из [НЫ Нн Т. С. РагаПе! 5ейнепс!пй апб АмешЫу Ь)пе РгоЫетз, ОК, 9 (1961), 841 — 848. Задача 7 — чз [Са[ Сачгй Г. Л!йоийгпз 1ог М)п)тнгп Со1онпй, Мах)гпшп Скйне, М)п)тшп Соченпй Ьу С!гйнез апг) Махнпшп !пберепбеп( 5е1 о$ а СЬогба! Сгарй, 2. 5! АМ Сотр., 1 (1972), 180 — 187. Задача 8 взята из [ОР[ Ог!оча С. 1., Рог1птап У.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
