Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 98
Текст из файла (страница 98)
19.13, который мы будем называть алмазом. В тех случаях, когда этот граф с х зо 8 вершинами является подграфом некоторого графа 6, мы будем Е предполагать, что сг' соприкасается с этим алмазом только в угловых вершинах й!, 5, Е и 1уг. При этом предположении покажем, что если в 0 имеется гамильтонов цикл Я с, то алмаз 0 проходится циклом с в точности одним из двух способов, изображенных на рис. !9.14, Рнс. !9.!3. Подгрзф алмаз. которые мы будем называть северо-южньгм и воегаочно.западным способами. Для обоснования этого заметим, что если гамильтонов цикл входит в 0 в вершине !у, Рнс.
!9.!4. Северо-южный н восточно-западный способы прохода через алмаз, он должен далее пойти в х, иначе вершина х будет пропущена. Затем он приходит в вершину Ж', где он не может покинуть О, ибо в противном случае и и гп нельзя будет посетить, не пропустив у. Поэтому далее он должен идти в Е и Я, в результате чего получаем Ги 19. Лохааеныд попок (б) северо-южный способ прохода через !). Рассуждения для восточно- западного способа аналогичны, Пусть теперь 6=(Р, Е) — индивидуальная задача о гамильтоновом цикле.
Мы построим новый граф 6', в котором всегда есть гамильтонов путь и в котором гамильтонов цикл есть в том и только в том случае, если он есть в 6. Идея состоит в том, чтобы заменить вершины графа ~г 6 алмазами и поместить их в некоторый гамильтонов путь с Яа помощью северо-южного способа. При этом граф 6 кодируи рл ется ребрами, соединяющими западные и восточные вершины этих алмазов. Опишем конструкцию более подробно. Н ачнем с построения графа 6', поместив и=!Ц алмазов !); с вершинами Уо Ео Е, и К, в вертикальный столбец и добавив ребра (Яы У,+,), 1=1,..., и — 1, как показано на рис. 19.15(а). При этом в 6' заведомо имеется гамильтонов путь р, а именно путь, зв включающий северо-южный проход через О,, затем ребро (е) Ыы Уе), затем северо-южный !В )ь е) Гвмвлвтовов 0'. б) Ребра в С', порождаемые реб- Далее для каждого ребра ром(6 1! в 6.
Ьы а,) исходного графа 6 доба- вим к 6' ребра (Ж'ы Е ) и (К', Е;) (см. рис. 19.!5(б)). Если в О имеется гамильтонов цикл, то в 6' можно построить соответствующий ему гамильтонов цикл, посещая алмазы в 6' в том же порядке, в каком в 6 посещаются вершины, и проходя через каждый алмаз восточно-западным способом. Обратно, если в 6' имеется гамильтонов цикл, он ие может входить ни в какой алмаз в северной или южной вершине, ибо тогда он должен проходить по всем алмазам северо-южным способом и окажется в тупике в вершине Ж, или Я„, Следовательно, этот гамильтонов цикл должен проходить по всем алмазам восточно-западным способом, и порядок, в котором посещаются алмазы, определяет гамильтонов цикл в графе О. () Пример !9.6.
На рис. !9.16 изображен простой граф О, не имею- щий гамильтонова цикла, и соответствующий граф 6', также не 19.9, С н ю льн ° ° а аК 495 имеющий~ гамильтонова цикла, но имеющий гамильтонов путь Р, показанный пунктирной линией. Д Теперь мы можем доказать основной результат этого параграфа: распознавание неоптимальностн обхода в индивидуальной ЗК вклгсзчает в себя задачу ОГЦ. Сформулируем вначале задачу распознавания неоптимальных обходов. Определение 19,9. НЕОПТИМАЛЬНОСТЪ В ЗК вЂ” это следукзщая задача. Даны индивидуальная ЗК и обход г; спрашивается, верно лн, что Г неоптимален? Д Теорема 19.6.
Задача НЕОПТИМАЛЬНОСТЪ В ЗК МР-полыгз. Доказательство. Эта задача принадлежит !у'Р, так как оптгн мальный обход является коротким удостоверением, показывающиьи~ 1 ! ! ! ! 1 l с' Рис. !9.!6. Граф о и соответствующий ему граф 6', иллюстрирующие преобразование задачи о гамильтоновом цикле в ограниченную задачу о гамильтоиовом никле. что обход !' неоптимален, Преобразуем теперь полиномиально задта чу ОГЦ в задачу НЕОПТИМАЛЬНОСТЬ В ЗК. Пусть 6=()г, Е) — граф в индивидуальной задаче ОГЦ, и пус-'ть Р— соответствующий гамильтонов путь в ней. Построим инднв'и дуальную ЗК с и = !!г! городами и стоимостью 1, если [г', !'1Е Е, 2, если 11, !')гГЕ.
Гамильтонов путь р определяет обход Г' в ЗК со стоимостью (и — 1) !+ +2=-и+!. Предположим, что Г неоптимален в ЗК. Тогда сущесст' вует обход стоимости п, который определяет гамильтонов цикл' в исходном графе 6 из задачи ОГЦ. Гл. 19. Локальныа попок 496 Обратно, гамильтонов цикл в б определяет обход в ЗК со стоимостью и, показывающей, что 1 неоптимален. Г) Вспомним подпрограмму УЛУЧШЕНИЕ(1) в нашей формулировке локального поиска — при использовании точной окрестности она выдает улучшенный обход, если обход» неоптимален, по. этому любую индивидуальную задачу НЕОПТИМАЛЬНОСТЪ В ЗК можно решить, вызвав один раз подпрограмму УЛУЧШЕНИЕ любого алгоритма точного локального поиска, В результате мы доказали Следствие. Если Р~ь)[Р, то никакой алгоритм локального поиска для ЭК с полиномиальной сложностью аждой итерации не может быть точным.
Таким образом, мы заканчиваем эту главу несколько пессимистическим замечанием (см. также задачу 14), разрушающим надежду на то, что для ЗК вЂ” нашей основной й(Р-полной задачи оптимизации,— можно найти алгоритм локального поиска с быстрыми итерациями, ~акой, как симплекс-алгоритм. Однако не следует забывать, что локальный поиск может быть очень эффективной эвристикой для таких задач. В действительности это часто лучшее, что есть. Задачи 1". Покажите, что задача о равномерном разбиении графа из 4 19.5 )т'Р- полна. 2.
Докажите следующий факт н объясните его связь с поискам переменной глубины [1.К1. Пусть е», 1=1, ..., Ф,— последовательность чисел, и пусть — их частичные суммы. Тогда если б(Ф)ьо, то существует циклическая перестановка чисел д»! йю еге», ..., йа, 9», ..., Ег », 1~с~а, обладающая тем свойст. вом, что все ее частичные суммы положйтельны. 3.
Докажите, чта равенства (19.12) каррентно определяют новые значения Р после обмена. 4. Разработайте алгоритм для нахождения нижней границы в задаче о равномерном разбиении графа используя алгоритм нахождения максимального потока. 5. Предположим, что при выполнении алгоритма зонального поиска мы хотим проверить, не доказано ли уже для новых допустимых решений, что они локально оптимальны. Опишите эффективный метод ганой проверки, В. Для ускорения поиска следующей пары а», Ь! при локальном поиске по онрестностн с испол~зованием равенства (19.11) в алгоритме равномерного разбиения графа Керннган и Лип [КЦ сортируют числа Р в Рь в убывающем порядке. а) Объчсните, почему это ускоряет поиск.
б) Проанализируйте временную сложность каждого поиска по окрестности и покажите, что она не превосходит 0(пз1ойп). в) Как сообщается, общая временнйя сложность оказывается около 0(пз 4). Что можно на основе этого сказать о числе проходов, необходимых для дости. жения локальной оптимальности? г*) Сравните временную сложность в пп. б) н в) с асимптотическим поведе- нием времени, необходимого для проверки возможности перестановка всевозмож- ных пар множеств равной мощности. 7* [ТЯ.
Диаметр графа — это самый длинный среди нратчайших для каж- дой пары вершин путей. Граф б называется й-регуллряьгм, если все его вершины имеют одинаковую степень А. (В ориентированном случае все степени захода и степени исхода равны Ь.) Предположим, что мы хотим разработать алгоритм ло- кального поиска для построения Ь-регулярного графа (ориентированного или неориентированного) с п вершинами и минимальным диаметром. Опишите, как выбрать а) метод поиска начального решения; б) окрестносги; в) функцию стон.
мости. 8* [Р52). Воспользуйтесь подграфом из $ !9.9, названным алмазом, для построения индивидуальной задачи комлгнвоижера с и городами, обладающей следующими свойствами: имеются а) единственный оптимальный обход и б) экс- поненцнальное (относительно л] число обходов, которые являются следующими наилучшими по стоимости, имеюг произвольно большую стоимость и не могут быть улучшены заменой менее чем ап ребер, где я — фиксированная доля.
9 [Р52[. Рассмотрим задачу коммивояжера с л городами, в которой матрица расстояний удовлетворяеч неравенству треугольника. Пусть са)0 — стоимость оптимального обхода, и пусть с — стоимость следующего (по стоимости) обхода. Определим зазор я как величнйу (са — са)/аа. Докажите, что 9~2/и. 10. В пуагсаноаском процессе время считается разделенным на маленькие от. резки длины б! н предполагается, что вероятность наступления некоторого собы- тия в любом сегменте равна б!/т независимо от остальных сегментов.
а) Покажите, что в пределе при гИ, стремящемся к нулю, вероятность того, что событие нз осуществится за время Т, равна е б) Будем считать, что вычислительная машннз делае~ незамеченную ошибку в течение года работы с вероятносгью !О " и что появление таких ошибок пред- ставляет собой пуассоноаскнй процесс. Какова вероятность гого, что вычисли- тельная машина выпалив~ 1 секундную программу без незамеченной ошибки? в) Предположим, что алгоритм локального поиска находит оптимальное ре- шение с вероятностью 0.39, н пусть выполняются предположения иа п. б).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
