Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 53
Текст из файла (страница 53)
3* (задача о китайском лочтавьоне). Ланы связный граф б ()г, Е) и функция стоимости с: Е- 2+. Требуется найти маршрут, проходящий по каждому ребру нз Е по меньшей мере один раз, так, чтобы общая стоимость маршрута была как можно меньше (при атом стоимость ребер, проходимых несколько раз, учитывается Задачи ал а, аз 12*. Дла данных множества стоимостей сгу на РебРах полного гРафа К„с л вершинами и л целых чисел Ь(иг), 1=1, .„, л, найди»е подграф 6 графа К„, такой, что степень вершины о~ равна Ь(о;), 1=1, ..., л, и 6 имеет минимально возможную общую стоимость. (3»казалие; вспомните построение из задачи 13 в гл. 1О).
13*. а) Рассмотрим частный случай задачи о назначениях, в котором В= =(р, и', ухи), с6: КХ У-~ Еь, )У(=16(=л и с; имеют ш~едующую специальную структуру: существуют действительные числа а»~се»)...)ил и р») )3»)...)15л, такие, что сб=гпах(0, э:; — 3») для всех 1~<, )~л, Покажите, что оптимальное паросочетание в этом случае всегда имеет вид М=((оь иг); <= =1, ..., л). б) Обобщите п.
а) на случай, когда 1(г) аг, если из~()ю и ° а; с6= й(1) М в противном случае для некоторых неотрицательных функций 1 н й. 14. В этой задаче показывается, что алгоритм нахождения взвешенного паросочетания в произвольном графе, приведенный на рис. 11.5, можно реалнзо. вать так, чтобы он требовал времени 0(л'). Алгоритм состоит из л)2 зталоа, т. е. частей между двумя последовательными увеличениями. Каждый этап может иметь 0(л) шагов, т. е.
частей, заключенных между двумя последовательными многократно). Приведите полиномиальный алгоритм для втой задачи, используя результат задачи 7. й*. Решите задачу 8 для случая, когда граф 6 ориентировал. 1О. Приведите полиномиальный алгоритм для задачи о реберлом локрыглии милималы<ой стоимости дая взвешенных графов (вспомните задачу 3 из гл. 1О), сводя ее к задаче о взвешенном паросочетанни. 11. Дано множество стоимостей с; на ребрах полного графа Кель» с 2п+1 вершинами.
Требуется найти подграф графа К,„,, изоморфный показанной ниже <двойной звезде» и имеющий наименьшую возможную общую стоимость. Покажи. те, что эта задача эквивалентна задаче о взвешенном паросочегании. Гл. !!. Взвешенное ларосочвшанив модификациями двойственных переменных. Один из аспектов расточительности алгоритма, приведенного иа рис. 11.5, состоит в том, что граф 07 заново строится на каждом новолг шаге, а граф О, выбрасывается.
а) Опишите реализацию этого алгоритма, в которой на протяжении этапа работа производится с одним и тем же графом. Не забудьте, что возможен шаг, такой, как предпоследний шаг в примере 11.2. Шаг называется шагом типа 1, 2 или 3 в зависимости ст того, будет ли в его конце 8,.=6„6, или бл. б) Покажите, что в течение этапа имеется 0(л) шагов каждого типа.
в) Покажите, как реализовать за время 0(л) каждый шаг любого сина, исключая вычисление 8,. Что касается вычисления 8„ то 6, можно вычислить за время 0(л), так как ]Чгг]=0(л). г) Покажите, как вычислить 6, за время 0(л) способом, аналогичным спасо. бу, примененному в венгерском методе (т.
е. используя массивы невязка и сосед). Остается вычислить 6,. Зто можно сделать, сохраняя список 1., содержащий 0(л) множеств вершин, а именно содержащий (!) все одноэлементные множества (ог], (2) все множества из 7», (3) все цветки графа б„возможно не входящие еще в У». Для каждой внешней вершины и; и каждого 5~Е имеется такая вершина ближайшая(члЯ ~5, что (1) ближийшая]вп Я не была внешней в тот момент, когда пг стала внешней; (!1) ближайшая]пг, Я имеет наименьшее значение с0 — а! — гху среди всех п7~5, удовлетворяющих (1).
Пусть рисса]оь Я.— значение с!7 — а! — сху в тот момент, когда вершина и; стала внешней или 5 было включено в Е в зависимости от того, что произошло позднее. Будем, кроме того, хранить для каждого 5 ~ Е две величины; 6]5]=ппп (сгу— -сх; — ау, о!~5, пугд5 и является внешней) и Л]Я, равную общему увеличению переменных а, соответствующих вершинам из 5, с того момента, когда 5 было включено в Е. д*) Покажите, что эту структуру можно поддерживать, затрачивая время 0(л') на каждан этапе. е) Выведите из сформулированных выше утверждений, что алгоритм нахождения взвешенного паросочетания в произвольном графе, приведенный на рис.
1!.5, можно реализовать так, чтобы время его работы не превосходило 0(]Ур). Комментарии и ссылки Венгерский метод принадлежит Куну. ]Кп] Кпйп Н. )Ч. Тйе Нппйаиап Ме!Бод !ог Ите Азяйпгпеп1 РгоЫеш, Кача! Резва!ей Еой!з(!сз Опаг!ег1у, 2 (1955), 83 — 97 Теорема 11,2 и прямо-двойственный алгоритм для задачи о взвешенном паросочетании в недаудпльиом графе принадлежат Эдмондсу: ]Ед] Едгпопдз д. Ма!сЫпй апд а Ро1уйедгоп ш!Рл 0-1 Чегнсез, 3. Вез. ИВЗ, 69В (1965), 125 — ! 30.
Алгоритм лля задачи о паросочетании с оценкой 0(л') (задача 14) взят из книги ]1.а) 1.аъ1ег Е. 1. Сопй!па!!опа! Орнгпаа1юп. Хе1могйз апд Ма(гоыз, Хеъ уогрп Но!1, )()пе)1аг! Ь )Ч|пь(оп, 1976. Задача 6 принадлежит М Яннакакису Задачи 8 и 9 взяты из работ (Км] Кшап Ме(-Ко. ОгарЫс Ргойгашшшй Е!з)пд Одд апд Ечеп Ро!пкй СЫпезе Ма!Ы 1 (1962), 273 — 277. ]Ед] Едшопдз 3., дайн»оп Е Е. Ма!сй!пй, Ец1ег Тонга апд Рпе СЫпезе Роз1гпап, Мани Ргой., 5 (1973), 88 — !24.
Комментарии и ссылки 279 Смешанный вариант задачи о китайском почтальоне (на взвешенных графах одновременно с ориентированными и неориентированными ребрами) оказывается намного труднее. См. гл. 15 и работу (Ра! РараоЗгпНПоо С. Н. Тйе Сотр1ехйу о! Ебяе Тгачегз!пя, 3. АСМ, 23 (1976), 544 — 554. Задача 11 взята из работы (Рг'! РарадппИПоц С. Н„уаппайай!з М. Тйе Сошр!ехйу о1 )!ез(г!с!ей Брани!пй Тгее РгоЫешз, рр.
460 — 470 ш Ап(ошй!а, (.аг|яцаяез апб Ргоягашш)пя, еб. Н. А. Мапгег Вег!)п: Брг1пйег-Чег1ай, 1979. Для матриц стоимостей специального типа, рассмотренных в задаче 13, про~не оказываетси не только задача о назначениях, не н ЗК. См. (ОО! О!!шоге Р. С., Оопюгу Е. Е. Бечцепс!пй а Опе-Б!а1е Чаг)аЫе МасЫпе: А Бо1чаЫе Сазе о( !йе Тгаче1!пя Ба1езшап РгоЫеш, О)т, 12 (!964), 655 — 679. 12 Остовные деревьв и матроиды В настоящей главе решается задача о минимальном остовном дереве. Заметим, что эта задача обладает фундаментальным структурным свойством, позволяющим получить для нее быстрое алгоритмическое решение. Таким свойством обладает целый класс задач оптимизации, известных как задачи о матпроидах, поскольку лежащая в их основе структура, являющаяся обобщением графов, называется матпроидом, Кроме того, будет показано, что некоторый класс более сложных задач также допускает эффективное решение.
В таких задачах, грубо говоря, требуется найти наилучшее решение, допустимое в двух различных задачах о матроидах. Эти задачи, равно как и задачи о паросочетании из предыдущей главы, в некотором смысле самые трудные комбинаторные задачи, о которых известно, что они разрешимы полиномиальными алгоритмами. Последнее резко отличает их от огромного числа намного более сложных задач таких, как ЗК и задача целочисленного линейного программирования, которые будут обсуждаться в последующих главах. 12Л Задача е мнннманьнем естовном дереве В предыдущих главах мы несколько раз упоминали задачу МОД как классическую хорошо решаемую комбинаторную задачу оптимизации. В задаче МОД дана симметричная (1Ц х [й[)-матрица с положительными элементами [а;,1, называемая матрицей расстояний, и требуется найти кратчайшее относительно этой метрики остовное дерево в графе К,и, — полном графе с [Р[ вершинами.
Иногда задача МОД ставится для связного графа 6= ($', Е)— не обязательно полного — и положительных расстояний дц') для каждого ребра [ио и;КЕ. Опять ищется кратчайшее остовное дерево в 6; так как Π— связный граф, то по крайней мере одно такое дерево существует.
Для преобразования некоторой индивидуальной задачи в этом варианте в индивидуальную задачу для исходной формулировки достаточно положить дн=оо для всех [ио и)1(Е. Ь) Мы будем испольэовать как а;р так н а(ип иу) Яля обозначения расстояния между иг н ир !2./. Задача о минимальном оооьооном дербе 28! Известно несколько эффективных алгоритмов для решения задачи МОД. Все они, так или иначе, используют следующий факт. Теорема 12.1. Пусть (([/и Т ). ([/„Т,),..., ([/ь, Ть) ) — остовный лес на множестве У, и пусть [о, и) — кратчайшее из всех ребер, у которых ровно один конец содержится в [/,. Тогда среди всех остов.
ных деревьев, содержащих все ребра из множества Т= .[/~,Т/, существует опгпимальное остовное дерево, содержащее [о, и). Рис. !2.! Доказательство. Предположим, что существует остовное дерево (У, г), где Г=Т и [о, и)(Р, которое короче, чем все остовные деревья, содержащие все ребра из Т и ребро [о, и[. Добавим к г ребро [о, и]; при этом, согласно предложению !.2, образуется единственный цикл. Не все вершины этого цикла содержатся в [/м так как о([/, (рис. 12.1). Следовательно, на этом цикле имеется такое ребро [о', и'1, отличное от [о, и1, что и'с[/ь и о'ЕУ вЂ” [/,. По условию это ребро не короче, чем [о, и), и не принадлежит Т.
Поэтому, удаляя ребро [о', и'1, получим новое остовное дерево (У, г"'), где с' =г"[/ 0 ([о, и1) — ([о', и'1), содержащее Т и ребро 1о, и) и имеющее стоимость не большую, чем стоимость и дерева (У, г'). Это, однако, противоречит нашему предположению о ! том, что дерево (У, г") короче, чем любое остовное дерево, содержащее ребро [о, и1 и множество ребер Т. П Посмотрим, как этот результат почти непосредственно приводит нас к эффективному алгоритму для задачи МОД.
Поскольку теорема справедлива для всех остовных лесов, то она, очевидно, справедлива и в том случае, когда [//= (о,), 1=1, ..., п, и Т=о. В применении к этому случаю теорема утверждает, что существуетминимальное остовное дерево, содержащее кратчайшее ребро, исходящее из о,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
