Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 59
Текст из файла (страница 59)
Алгорипслс, представленный ни рис. 12 21, корректно ресиает задачу а пересечснсссс лсапсроидав за ссре,сея 0(/Е!ьС(! Е!)). Доказательства. Во-первых, утверждается, чсо последовазельность 5=!е„г„..., е ), пострсеииая этим алгоритмом, является правильной и, следовательно, чередующейся. Свойсзво Г1р( из определеиия 12.6, очевидно, выполняется. Для доказательства свойсгва Пр2 заметим, что элемеиты, стоящие в 5 иа четных несзах, входяз в !, что вытекает из двуссольиости вспомогательного графа.
Кроче того, коиструкция вспомога,ельпого орграфа гарактирует, что гс Е0,, для четкых с. Предположим теперь, что ес Е0„ для некоторого )с(сй Тогда дуга (е„, ес) содержится во вспомогательиом графе. Это, однако, противоречит тому факту, что с„с — очередь (и, следовательно, иаш алгоритм находит кратчайшие пути). Свойство ПрЗ показывается аналогично. Накоиец, так как сиЕ Т, зо т нечетко и !+е аль'; саким образом, !Я35Еус' и 5— ) величивающая последовательность.
Таким образом, иаш алгоритм производит увеличеиие вдоль увеличивающих последовательиостей, и поэтому все получаемые миожества ! лежат в д Г) Х, как и требуется. Покажем теперь, что алгоритм ие может остановиться, пока ! ие станет максимально возможиым. Пуссь Е и 1l — соответствеиио множества помеченных и иепомечекиых элемеитов из ! в копие алгорссзма Г'ассмотрим Е,=- г-в!см((!) и Ев=-з!сн(Е). Каждый элемент множества ! прииадле- 12.5. Пгрнхчение двух лащрондоз жит одному из множеств Е„Е, Рассмотрим лкгбой элемент е; из Š— 7; покажем, что он также принадлежи! одному из множеств Е„Е,.
Если е, помечен, значит, во время поиска мы помечали все элементы соответствующего 0Ь Поэтому если е! добавить к ~., то АЛГОРИТМ ДЛЯ ЗАЛАЧИ О ПЕРЕСЕЧЕНИИ МАТРОИЛОВ Вход. Два матроида М=-(Е, Э) н М=(Е, РГ), заданные двумя алгоритмами аул и е(д Выход. Множество ! Р 5 ПЖ чаксимальной мощности. Ьед[п 1;=м); (сопнпепг; начальное значение! этап: А:=кз, О'=З, Т:=я!; (сопппеп! задание начальных значений для поиска по орграфу) 1ог ан е;СŠ— !до Ьедчп (сопппепт: построение вспомогательного орграфа) И 1+е;Р З, !л' Шеп 1:=1+ е!, до 1о этап; и 1+е;ч 7 реп О.=О(3(е!), помелгка[е!):=О, е1зе (ог ан е!цС! — е; до А:=А[3((е), е,)); и 1+с;СЖ Гиен Т:=Т [3(е!) ' еые 1ог аП е!РР! — е! до А:=А()((еь е!)) (сопппепг; С! и Р! — циклы, определяемые через е! и 1 тан, как описано в тексте перед определением 12.6) епг(; пЬПе О Ф мз с(о Ьея[п пусть е †элеме из !): удалить е из О; (согптеп1: О долясно быть очередью) 1ог ап непомеченных е'еЕ, таких, что (е, е') СА до Ьей! п полгтка[е'1:=е, О:=-О[3(е'); И е'ЕТ Гиен 1:=1(йПУТЬ(ез), яо 1о этап епо епо спи ргоседнге ПУ'ТЬ(е) (сопппеп1; онз выдает правильную увеличивающую последовательность от некоторого элемента множества В до е; ПУТЬ вЂ” ренурсивная и ро цеду ра) И помелгка[е) =-.
О гиен ге!нгп [е) е1зе геьзгп ПУТЬ(ломглгка[е)) [[ [е) Рнс. !2 2!. Алгоритм для задачи о ~ересеченнн матроидов образуется )у'-цикл, именно 0Ь Таким образом, е; Е зрдг(Е). Предположим теперь, что е! не помечен. Тогда должно быть 3+ег(У, ибо в противном случае элемент е; имел бы пометку О. Следовательно, 3+е! содержит М-цикл Сь Однако никакой элемент е из Сг не мог помечаться, поскольку в противном случае е, был бй помечен на следуюшем шаге по дуге (еп е;). Поэтому при добавлении е; к (У обРазУетсЯ М-цикл.
Следовательно, е! бздд!('(3). Итак, Е, [)Е,=Е, и поэтомУ г(Е„Ех) ) [з'[ дла всех з' Е 2 Пзь (лемма 12.4). Однако легко понять, что е(Е„Еа) =[Е[+[(I [=-[I [ Гл. 12. Остовнмв деревья и матроиди и поэтому !1(~ (в' ! для всех / Е д Пус'. Следовательно, 1 — требуемое максимальное пересечение. Для получения временной оценки заметим, что возлюжно не более ~ Е ! увеличений. Г!ри каждом увеличении основное время уходит на построение вспомогательного орграфа. Для каждого еьЕŠ— 1 мы находим 0о или С,, или оба цикла. Это можно сделать, применяя алгоритмы и(в и Тл к 1+е,— е, для каждого ее ЕЕ. Построение вспомогательного орграфа Я и множества Т также можно выполнить за время О (! Е !' С (! Е !)).
Наконец, поиск по орграфу требует 0(~ Е!ь) времени. Получаем нужную временную оценку. ( ) 12.6 О некоторых расшмреннях задачи о пересеченмн матрондоа 12.6.1. Взвешенное пересечение матрондов. Г1усть даны два матроида М=(Е,,7) и 1ч'=(Е, Зб), и пусть каждому еЕ Е сопос~авлен вес ш(е).
Требуется нанти такое подмножество 1ЕКП,7, чтобы ~З„, гс(е) б(Зла как можно больше Для этой задачи имеется полиномиальиый алгоритм, являющийся еще одним применением прямо-двойственного метода. Опять задача с весами сводился к задаче без весов с помощью представления исходной задачи в виде задачи линейного программирования. Э~о представление— впало~ ~еоремы 1!.2 — описано в следующей ~еореме. Теорема 12.9 (Эдмондс). Задача о взвешенном пересечении лапьроидов эквивалентна задаче ЛП шах ~ ш(е) х(е) ьва пРи УсловиЯх ~ х(е)~г (А), вел для всех А ~ Е.
~ х(е) (гн (А), ья А Очевидно, что если х(е), где е с Е, представляет некоторое множество из зПрь', то ограничения из теоремы !2.9 выполняются. Остается показать, что при любых весах компоненты оптималышго решения этой задачи ЛП всегда равны О или 1 и, следовательно, на самом деле соответствуют множеству наибольшего веса из 2 П уб. Конструктивное доказательство этого факта можно получить, применяя прямо-двойственный метод к рассматриваемой ЛП и замечая, что ограниченная прямая задача всегда оказывается задачей о не- взвешенном пересечении матроидов для пары модифицированных матроидов М' и У' Мы не приводим здесь деталей, поскольку они совершенно очевидны (см.
!).а1)). !2.6. О неноторнн раешгзреннях 12.6.2. Матроид с соответствием. Даны матроид М = (Е, 5) и разбгн нне П множества Е на непересекающиеся пары: П =- =()е„е.,~, [е„е,), ..., !е„„е !). Требуется найти наибольшее подмножество Р в множестве П, такое, что ()„,ррЕЮ Эта задача называется задачей о матроиде с сооогоеаотоиен. Например, легко видеть, что если М вЂ” матроид разбиения, то задача о матроиде с соответствием вырождается в задачу о паросочетании (задача !9). Если М вЂ” графический матроид, то задачу о ег н (!ез ° ез! ° !ез,ез! !ез ее),(ег еа) (ег езо1 !езг,зйг1, (езз,ем1, !езз,езе)) Рис.
!2.22, магроиде с соответствием можно переформулировать следующим образом: для данных графа 6 и разбиения П ребер этого графа на пары (рис. !2.22) найти такое остовное дерево Т, чтобы вместе с любым ребром е, содержащимся в Т, напарник эгого ребра также содержался бы в Т.
Эта задача является обобщением двух задач — задачи о пересечении двух графических матроидов (пример !2.12) и задачи о паросочетании (задача 20). Ловац (Ео) недавно показал, что задача о матроиде с соответствием не может быть решена для произвольных матроидов. Для случая з рафических матроидов (иа самом деле для более общих матричньи матроидов) Лован привел алгоритм. 12.6.3.
Пересечение трех матроидов. Еще одно направление, в котором можно попытаться обобщить результаты, полученные для пересечения двух матроидов,— это построение алгоритма для нахождения наибольшего множества, независимого в огрел матроидах. К сожалению, не известно полиномиального алгоритма, решающего эту задачу.
Более того, как будет показано в гл. 15, имеются свидетельства в пользу того, что для этой задачи никогда не будет найдено полнномиального решения независимого ог того, насколько мы продвинемся в понимании ее структуры в будущем. Пока мы пока- Гл. >2. Опповчые деревья и ма>ираиды 310 жем, что если бы у нас был способ решения этой задачи за полиномиальное время (полиномиальиое огносительно )Е! и сложностей С„Св и С, алгоритмов, описывающих три рассматриваемых матроида), то мы могли бы также решить за полиномиальное время хо- Ое У5 Рис. 12.23. роша изучекную комбинаторную задачу оптимизации, связанную с ЗК,— задачу об ориентированном гамильтоноаом пути; для данного орграфа 0=('(>, А) определить, имеется ли и Р гамильтонов путь, т. е. ориентированный путь й, проходящий через каждую вершину множестиа )> ровно один раз.
Например, орграф О, предсгааленный на рис. !2.23, содержит гамильтоноа путь ('о„ом о„оь. о о«о о ° оь) Теорема 12.10. Существуюгп такие три матроида М,=(А, 7,), М,= (А, 5,) и М„=-. (А, 5,) с полиномиально ограниченными алгоритмами Хв„2в, и Ев„чп>о орграф 0 = — (!', А) содержит гамильтонов путь в том и только в том Случае, если суи(ествует л>ножество 1 ~ 5, ПЛ,П,7„>пакое, что ! > (= )Ъ'! — 1. Доказательство. Достаточно заметить, что гамильтонов путь— э>о просто ордереао, никакие дае дуги которого ие имеют общего начала.
Поэтому любой гамильтонов путь может быть определен как подмножестао множества А, независимое одновременно в графическом матроиде, соответствующем графу ()>, Ел), в матроиде разбиения по концам дуг орграфа 0 и и матроиде разбиения по началам дуг орграфа О, и имеющее мощность !'и'! — 1. Заиичи Задзэчн 1. Найдите МЮД в приведениям ниже графе, используя еба алгоритма' представленные на рис.
12.2 и 12.5. Найдите ЛЬ!В лля того же графа. 2". Алгоритм построения МОД, предстзвлснньп1 на рис. 12.5, нощно реалнаоватг так, чтобы время его работы не пр~восходило 0()Е) )од!од))г)), испо.ш. зуя следующую процедуру Прежде всего мы не буден вычислять связные компоненты графа (У, Т) заново нэ каждом этапе. Вместо этого чы булеи сливать соответствующие компоненты. а) Покажите, как можно представлять разбиение С=(5„, 5э) вершин с помощью четырех массивов пераая. следующая, размер и множество таким об. разом, чтобы за один шаг иожно было определить.
в каком множестве содержится данная вершина, а двз множества 5; и 5у иожно было бы слить за 0(ппп(15;1, 15т)1) шагов. Медиану нножества, солержашего и чисел, можно вычислить за время 0(п), используя умный алгоритм из (ВГРКТ). б) Используя эту информацию, понажите, что множество 5, содержащее и чисел, можно за время 0(п 1ой р) разбить на р-хзантили, т. с. такие р ипожеств 5г, 5х,, 5г, каждое мощности ( п(р ) или ("п(р ), что из ац5~', Ь~5У, ~(А следует а~Ь. Предположим теперь, что список смежностей каждой вершины а подразбит на р-квантили лля некоего р, которое предстоит определить. Будем вычислять значения пассива кратчайшее (рис.
12.5), просматривая список сиежностсй каждой вершины о пачками, содержащими целые квантнли. Если ганой поиск по квантили обнаруживает по крайней мере одно ребро 1о, и), в ноторои и принадлежит другоиу множеству разбиения С, то поиск успешный; в противном случае зто неудачный поиск. в) Покажите, как вычислять кршпчайиме таким образом, чтобы (1) общее число успешных поисков не превосходило О((ЕУр) на этап и (В) общее время неудачных поисков не превосходило О((Е1) для асах зтапоз вместе. г) Покажите, что нремя работы описанного выше алгоритма не пр.восходит О (1ой 1'г( ((ЕУР+ Пг)+(Е( )од р), Соответствующим образом выбирая р, покажите, что МОД в графе с (Е()!)г()од('г'! может быль найдено за время 0()Е) 1ой 1ои()г)).
л) Обобщите результат из п г) на графы с (Е)<1)г(1од(у(. (указание; вначале вьгполните ой1од()г) этапов алгоритма, представленного на рис. 12.5.) 3. Покажите что жадный алгоритм длн МОД можно реализовать так, чтобы время его работы не превосходило 0()Е))од))г)). 4, Пусть Р=(р„рэ, ..., рп)~рэ — конечное множество точек на плоскости. Пусть йг =бш1(рп ру) — евклидова расстояние между рг и р .. Клетхог) Дирихле точки р;~Р называется множество всех 4~Р, таких, что бпй(рь 4)аб)з((рм д) г /.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
