Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 85
Текст из файла (страница 85)
Получающийся в результате обход приведен на рис. !7.9(г). Теорема 17.4 гарантирует, что этот обход является 1-приближенным. На самом деле этот обход всего на!(ехе длиннее оптимального обхода, приведенного на рис. 17.9(д). Д Насколько плохим может быть поведение этого алгоритма? На рис, ! 7.10 приведен пример с евклпдовымн расстояниями, на котором достигается верхняя оценка ошибки, равная 100%.
Кратчайшее остовное дерево Т приведено на рис. 17.10(а). Если взять две копии дерева Т (рис. 17.10(б)) и произвольный вложенный обход, то можно 428 Гл. 17. Прналиженные алгорнтмы получить обход т, приведенный на рис. 17.!0(в). Оптимальным об- ходом является обход т, приведенный на рнс. 17.10(г). Элементарные вычисления дают с(т) =2 (и — 1) (2Р+с) з)п ~ — ) +2с, гп~ !01 с (т) = и (2)7 + с) з! и ( — ~ + пс. (и, Положив )с=1, с=-1/и' и и сколь угодно болыпим, получаем, что а1 аг а„ (б) (а) (в) (г) Рис.
!7.Ю. 1нпс(т)=4п, в то время как 1ппс(т)=2п. Таким образом, ошибка а и может быть сделана сколь угодно близкой к 100%. Алгоритм дерева, замаскированный во многих вариантах„был из. вестен исследователям в данной области многие годы как приближенный алгоритм для ЗКНТ с наилучшей относительной ошибкой !7.2. Приближенные алгоритмы для задачи г1аммшюяееера 4эв . в худшем случае. Не было известно, существует ли приближенный алгоритм с ошибкой, в худшем случае меньшей, чем 100%; при этом широко было распространено мнение, что в рамках полиномиального времени нельзя достичь лучшей оценки в худшем случае для ЗКНТ. Однако недавно Кристофидес (СЫ нашел следующий простой алгоритм.
Алгоритм Кристофидеса работает полиномиальное время. Шаг 1 можно выполнить за время 0(п') (см. 2 12.1), Нахождение кратчайшего совершенного паросочетания в полном графе (естественно, 1. Найти минимальное истинное дерево Т для матрицы расстояний (б!71.
2. Выделить в Т вершины нечетной степени и найти кратчайшее совершенное паросочетание М в полном графе, содержащем только эти вершины. Пусть б — мультиграф с вершинами (1,2, ..., я), в который входят все ребра иэ Т и М. 3. Найти в П эйлеров маршрут и вложенный в него обход. Рис. 17.11. Алгоритм Крнстофидеса. с четным числом вершин; заметим, что в Т всегда имеется четное число вершин нечетной степени) — это другой вариант задачи о взвешенном паросочетаиии из гл. !1, и, следовательно, найти такое паросочетание можно за время 0(я') с помощью алгоритма, приведенного на рис. 11.5.
На самом деле возможен даже алгоритм со сложностью 0(п') (см, задачу 14 из гл. 1!). Наконец, шаг 3 можно выполнить за линейное время. Замечательным фактом является то, что результат отличается ог оптимального заведомо не более чем на 50%. Теорема 17.5. А лгоритм Кристофидеса является 172-приблиэкеяяым алгоритмом для ЗКНТ. Доказательство. Граф 6, построенный на шаге 2,— эйлеров. Для доказательства этого заметим, что, если вершина имеет четную степень в Т, она имеет ту же степень в 6. Если она имеет нечетную степень в Т, то в 6 ей инцидентно одно дополнительное ребро из паросочетания М. При этом граф 6, очевидно, связеи, так как в качестве подграфа он содержит остовное дерево, а именно дерево Т. Чтобы получить оценку 172 для ошибки, вспомним, что граф 6 состоит из Т и М; поэтому стоимость получаемого обхода т удовлетворяет неравенству с(т) ~ с(6) =с(Т)+с(М).
(г17. э) При этом с(Т) (с(т), (17,2) где т — кратчайший обход. пусть ((ы 1,,..., 11 ) — множество вершин нечетной степени в Т в том порядке, в каком они появляются в т. Другими словами, т=(аг(,а,1,... аг,!г аэ ), где все ив 430 Гл. 17. Пупблименные алеоринсмы последовательности (возможно, пустые) вершин из множества (1, 2,..., п). Рассмотрим два паросочетания на множестве вершин нечетной степени: М,=(П„с,), [!е, 1,),... [е,„„(, [) и М,=([!еч 1,[, [(„!е[,..., [)е, с',!).
По неравенству треугольника (см. рис. 0 — — — — -лэ а)а с — -с ц 0 ~ ~.О' Рис ) 7.! 2. 17.12) с(т)= с(Мс)+с(М,). Но М вЂ” оптимальное паросочетание, поэтому с(т))2с(М), или с(М) (е (т))2. (17.3) Подставляя (17.2) и (!7.3) в (!7.1), получаем с (т) «...— с(т) или ( —. 3 . (т) — с (т) 1 [) с !т) Пример 17.2 (продолжение), На рис. !7,13(а) при»едено минимальное остовное дерево Т с вершинами нечетной степени, выделенными кружком, для рассматривавшейся выше карты, изображенной на рис. 17.9. На рис. 17.!3(б) приведено кратчайшее паросочетание М на выделенных вершинах, а на рис. 17.13(в) приведен граф 6. Эйлеров маршрут в графе 0 указан иа рис. 17. !3(г), а соответствующий обход приведен на рис.
17.13(д). Построенный обход чуть-чуть лучше, чем обход, построенный на рис. 17.9 с использованием алгоритма дерева, 'он отличается от оптимума меньше чем на 8'7е. Аналогично алгоритму дерева, алгоритм Кристофидеса может асимптотически достигать своей оценки в худшем случае.
В примере на рис. 17.!4(а) приведено кратчайшее остовное дерево Т. В нем только две вершины нечетной степени, поэтому оптимальное паросочетание состоит из единственного ребра. Получаемый в результате эйлеров граф является обходом, и, следовательно, шаг 3 17.2. Приближенные алгоритмы для задачи коммивояжера 431 !б) !а) (в) !! 2,3,6,8, !6,9,7,5,6,4,2, !! (д) Рис. 17,!3. ь, ьг Ь ь ь, ь, Ь «-! аг аг лз ал алел л» (б) Рис.
17.14, 432 Гл. )7. Приближенные алгоритмы тривиален. Построенный таким образом обход имеет общую длину Зп, тогда как кратчайший обход (рис. 17.14(б)) имеетдлину 2п+1. Поэтому ошибка может быть как угодно близкой к 1/2, 4 У.З Приближенные схемы Задача 0-1-РЮКЗАК была определена в гл. 15 следующим образом: Для данных положительных целых с,, с„..., с„и К выяснить, существует ли в множестве (1, 2,..., п) такое подмножество Я, что ~члезсу — -К. Задачу 0-1-РЮКЗАК можно решить с помощью псевдополиномиального алгоритма, являющегося модификацией алгоритма для задачи ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК, приведенного в 2!6.2.
Снова строим орграф б(с„см..., с„; К)=(к', А), где)г=(0„1, ..., К), 1. Пометить вершину О. 2. Для 1=1, 2... и выполнить: для каждой помеченной вершины о пометить вершину и, такую, что (о, и) а Ар 3. Заключитгн что данная индивидуальная задача имеет решение в том и только в том случае, если К помечено Рис. !7.15. Алгоритм ДП-1. А=-А, 1)А,()...
ОА„и А,=((о, и)Е$": и — о=с)). Затем применяем алгоритм, приведеннйй на рис. !7.15. Этот алгоритм является примером очень общего класса методов, называемых обычно динамггческилг программированием (см. 2 18.6), Лемма 17.1. Пусть М. — множество помеченных вергиин после 1'-го выполнения шага 2 в алгоритме, приведенном на рис. 17.15.
Тогда М =(оЕ)7: суи4ествует такое множество Вс:-(1, 2,... !), что ~гевсг=о). Доказательство. Докажем эту лемму индукцией по!. Она, очевидно, справедлива для 1=0. Для проведения шага индукции рассмотрим)-ю итерацию, 1= О, ипредставим Му в видеМ =М,)..)В,, где Ву (и: оЕМ7 т и (о, и)ЕА7)= (и: оЕМ7 т и и=о+су). 17.3, Приблихеннв!е схема .Тогда по предположению индукции 433 М7 — — (оЕ'г", существует такое множество 5' ~ (1, 2, ..., 1 — 1), что либо Х с!=о, либо ~ с,+с =о) = 16з !чз' = (оЕ'г' существует такое множество Я = (1, 2, ..., 1), что Хс!=о). П сев Теорема 17.6. Алгоритм ДП-! корректно решает задачу 0-1- РЮКЗАК за время 0(пК).
М,: (0) М,:(О, !) М,: (0,11,18,29) Мз' (0~ 11 !8~24 29 35 42 53) М,: (О, ! 1, 18, 24, 29, 35, 42, 53) М,; (О, 11, ! 5, ! 8, 24, 2б, 29, 33, 35, 39, 42, 44, 50, 53) М,: [О, 7, !1„15, ! 8, 22, 24, 25, 2б, 29, 3!> 33, 35, Зб, 39, 40, 42, 44, 4б, 49, 50, 51, 53) Таким образом, множество Мг содержит всевозможные суммы целых чисел из множества (с„с„,..., с ), не превышающие К. Поэтому алгоритм ДП-1 можно рассматривать не как процесс расстановки пометок в графе, а как процесс построения подмножеств М,, что проиллюстрировано на рис. 17.16. В результате получаем, что рассматриваемая индивидуальная задача не имеет решения, поскольку 56(М„.
() Определим теперь следующую близкую задачу опта.иизации. ОПТИМИЗАЦИОН11ЫЙ 0-1-Р(ОКЗАК Даны целые числа (и!„..., !о„; с„..., с„; К). Требуется максимизировать 2', с,ху !'=! Доказательство. Корректность алгоритма следует непосредственно из леммы: К помечено тогда и только тогда, когда в множестве (1, 2... и) существует такое подмножество Я, что ~!,зс =-К. Для получения временнбй оценки заметим, что каждое выполйение шага 2 требует 0(К) времени, так как помечено не более К вершин.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
