Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 84
Текст из файла (страница 84)
без ограничений) ЗК, по существу, так же безнадежна, как задача нахождения точногорешения. Тем не менее можно показать, что достаточно успешные стратегии существуют для очень естественного частного случая этой задачи. Рассмотрим (пхп)-матрицу расстояний Ы;;1 с положительными действительными элементами. Как обычно, считаем, что матрица [йы[ симметрична (т. е, йы=-йп для всех 1, 1) и что дух=0 для всех 1. Будем говорить, что матрица [ды! удовлетворяет неравенству треугольника, если й„+й»ь=..д;, для всех 1(1, 1, й ( п.
Неравенство треугольника, по существу, утверждает, что путь из города 1 в город й через город 1 не может быть дешевле, чем путь непосредственно из ( в й (см. рис, 17.5(а, б)). Это очень естественно, поскольку посещение города 1 является дополнительным ограничением, при котором стоимость может только возрасти. Неравенство треугольника выполняется автоматически, если, например матрица расстояний порождена метрикой — как в важном частном случае матриц евклидова расстояния, в которых каждый город представляет точку р; на 2-мерной карте с координатами (хь у,) и йы — — [(х,— х;)'+ (у,— у;)'1ч (см. рис, 17.5 (в, г) и задачу !7 из гл. 15). Другой важный класс матриц расстояний, для которых неравенство треугольника автоматически выполняется, образуют матрицы замыкания.
Будем говорить, что матрица [й;;1 — замыкание матрицы Ыы!, если 4; — длина кратчайшего пути из ( в 1 в полном графе с и вершинами (1, 2,..., и), в котором длина ребра [й 11 равна йп. Замыкание (ахп)-матрицы расстояний можно вычислить за время 0(п') с помощью алгоритма Флойда — Уоршелла (2 6.5). На рис. !7.5(б) показано замыкание матрицы, представленной на рис. 17.5(а).
Замыкание [йы1 любой матрицы расстояний Ып! удовлетворяет неравенству треугольника, поскольку если йы)йы+ +а»ю то йы не является длиной кратчайшего пути из 1 в й. Неравенство треугольника выполняется также для матриц расстояний, моделирующих структуру стоимости для намного более общих ситуаций. Они включают составление расписаний (где йы может означать начальные затраты на задание[ при условии„что 17,2. Приближением алгоритмы для эадачи яоммлвояже о 423 последним выполнено задание !) и задачи о маршрутах (х(«1 может включать кроме расстояния, близкого к евклидовому, такие компоненты стоимости, как стоимость горючего, затраты на обслуживающий персонал, время ожидания н т, д.). Как правило, если элементы матрицы расстояний представляют стоимости, неравенство треугольника автоматически выполняется.
Причина того, что эти матрицы расстояний удовлетворяют неравенству треугольника, О 3 3 1 3 О б 2 3 6 0 4 1 2 4 0 (б) )х! Рз ° ° (О, 1) (1, 1) 17« (О, 0) (в) Рис. !7.5. Матрица на рнс. (а) не удовлетворяет неравенству треугольника, поскольку, например, х(ы ) Ла« + Вм. Матрица на рис. (6) удовлетворяет неравенству треугольника.
На рнс. (т) показана матрица евклидовйх расстояний для карты с четырьмя точками, показанной на рис, (в). состоит в том, что они на самом деле являются матрицами замыкания положительных матриц стоимости. Это свойство может нарушаться, если некоторые из элементов являются выигрыиами— т. е. отрицательными стоимостями. Например, если каждое посещение города ! дает некоторую «премию», то вполне возможно, что ((!)+ с(1 ь(с(х ь. Определение 17.2. ЗК с неравенством треугольника (или метрическая ЗК) (сокращенно ЗКНТ) — это ЗК, ограниченная на матрицы, удовлетворяющие неравенству треугольника.
Если далее ограннчить эту задачу на матрицы евклидовых расстояний, получим евклидову ЗК. Теорема 17.1. ЗКНТ (в варианте распознавания) й(Р-полна. 1(оказательство. Напомним преобразование задачи ГАМИЛЬТОНОВ ЦИКЛ в задачу ЗК. По данному графу (У, Е) мы построили 0 5 3 ! о С7) 2 3 7 0 4 2 4 о (а) 0 1 1 «75 1 0 ~/2 2 ~/Х 0 ь/2 ~/5 2,/2 0 (т) 4в4 Гл. 17. Приближенние илгариьвми индивидуальную ЗК ((йы), !У!) размера !У!х !1'1, где а1ы=!, если (оо о;)сЕ, и йы=2 в противном случае. Сразу же получалось, что в этой индивидуальной задаче имеется обход стоимости !У! или меныпе тогда и только тогда, когда граф 6 гамильтонов. Заметим, что любая матрица расстояний с элементами 1 или 2, такая, как (йвл), удовлетворяет неравенству треугольника.
Таким образом, задача ГАМИЛЬТОНОВ ЦИКЛ полиномиально преобразуется в ЗКНТ, [л ав ьв аа ав ав аь ав аа вба ав ав ава (а) (б) Рис. !7,6. Далее мы приведем два приближенных алгоритма для ЗКНТ. Эти эвристики строят не обход, а эйлеров остовный граф. Будет показано, что при наличии неравенства треугольника такие решения можно преобразовать в обходы, не увеличивая стоимости. Мулыпиграф (У, Е) — т. е, граф, в котором допускаются кратные ребра, называется эйлеровым, если он содержит замкнутый маршрут (называемый эйлеровым мариьругпом), в котором каждая вершина появляется по крайней мере один раз и каждое ребро появляется ровно один раз.
Например, мультиграф, представленный на рис. 17.6(а), эйлеров, поскольку замкнутый маршрут (о„оа, о„, о„ оь оа ов оа ов оь оа ов оа ов ова ов ов, оо оа ов ов! проходит по всем вершинам и ровно по одному разу по каждому ребру. Следующий простой результат, принадлежащий Эйлеру (Бц), является исторически первой теоремой теории графов. Теорема 17.2. Мультиграф 6=(У, Е) эйлеров в том и только том случае, если а) 6 свлзен и б) все вершины из У имеют четную степень. Доказательство. Необходимость этих условий очевидна. Доказательство их достаточности проведем индукцией по числу ребер в 6. Базис индукции — т.
е. утверждение для мультиграфа с одной вершиной и без ребер — тривиален. Предположим теперь, что 6 удовлетворяет условиям а) и б) и, кроме того, все мультиграфы с числом ребер меньшим, чем в 6, удовлетворяющие условиям а) и б), 77.2. Приближенные алгориглмы для задачи коммивояжера 425 эйлеровы, Выберем некоторую вершину о в графе 6 и будем строить маршрут по ребрам графа 6, никогда не проходя по одному и гому же ребру дважды, до тех пор, пока снова не встретится вершина о. По свойству б) это всегда будет возможно. Удаляя ребра полученного маршрута из 6, приходим к некоторому числу связных компонент.
Прн этом каждая компонента удовлетворяет обоим условиям а) и б) и, следовательно, по предположению индукции является эйлеровым графом. Легко видеть, что эйлеров маршрут в графе 6 можно получить, <присоединяя» эйлеровы маршруты компонент к исходному маршруту. Д ргоседпге ЭЙЛЕР(чз) (сошшепи она выдает эйлеров маршрут в связной номпоненте графа 6, содержащей ч,) Ьей[п И из ч, не выходит ребер Гпеп геыгп [чй (сопнпепб пустой маршрут) еые Ьей[п начиная из ч„строить маршрут в Гь который ни по какому ребру не проходит дважды, до тех нор, пока снова не встретится ч,; пусть [ч„ч„..., ч„, ч,] — этот маршрут; удалить [ч,, ч,1, ..., [чн, ч,1 нз 6; гещгп [ЭЙЛГзР(чз), ЭЙЛЕР (ч,), ..., ЭЙЛЕР(ч„), ч,] '); епа епд Рис.
!7.7. Из данного конструктивного доказательства достаточности указанных условий вытекает приведенный на рис. 17.7 рекурсивный алгоритм для нахождения эйлерова маршрута в произвольном иультиграфе (]г, Е), удовлетворяющем условиям а) и б), за время Э([Е]) Пример 17.1. Применим процедуру ЭЙЛЕР к графу, изображенному на рис. 17.6(а). Вначале ЭЙЛГР(о,) может выдать маршрут [о„о„, о„о,, о„о„, оа, о„о,]. Затем вызывается ЭЙЛЕР(п,), а граф в этот момент имеет вид, приведенный на зис. 17.6(б).
Пусть выдается, например, маршрут [о„, п„о„о„ о„о„о,]. Затем вызывается ЭЙЛЕР (о„), в результате чего выдается [о„, о„о„о,~. ЭЙЛЕР (о,) выдает [о,|, ЭЙЛГР (о,) выдает о<1 и т. д. вплоть до вызова ЭЙЛЕР (о„), в результате чего выдается маршрут [о„о,, о,„, о„~. Остальные вызовы процедуры ЭЙЛЕР приводят к пустым путям; в результате получается эйлеров маршрут [о„о,, о„п„оа, п», о„о„, о„оз о< 0 о< 07, В~ р»' о10 э! оз' о<' о»1' Д ') Мы подразумеваем, что нызов функции х:=Г(б(х), Н(у)) означает, 1то Гз вызь:вагтся раньше Н. Это важно в тех случаях, когда, аналогично зэссматриваемому варианту, функции обладают побочными эффектами.
Гл. !у. Приблилсеннме олгориглми Пусть Ыы! — матрица расстояний размера пХ и, удовлетворяющая неравенству треугольника. Эйлеров остовный граф — это эйлеров мультиграф 6=(У, Е), где У=(1, 2,..., и). Стоимость графа 6 равна с(6)=~чР!с певйп. Теорема !7.3. Если 6=(1', Е) — зйлеров остовный граф, то за время 0(!Е~) можно найти обход т вершин множества У, удовлетворяюи(ий неравенству с(т)=с(6). Доказательство. По предположению в 6 имеется эйлеров маршрут ги, Так как ~е проходит через все вершины по крайней меРе один Раз, можно записать иэ=(ае(,аг(, ...г'„а,), где т = = (1„ ... („) †обх и а„ а,, ..., а„ вЂ последовательнос (возможно, пустые) целых чисел из множества (1, ..., и).
(Бу- 1. Для данных (б61 найти минимальное. остовное дерево Т. 2. Построить мультиграф б, используя бас копии каждого ребра из Т. 3. Найти эйлеров маршрут в 0 и вложенный в него обход. Рис. 17.8, Алгоритм дерева. дем говорить, что обход т вложен в 6.) Из неравенства треугольНИКа СЛЕДУЕТ, Чтп йы(дп +й,„,+... и йу „„,+й; ь ДЛЯ ЛЮ- бого т. »1. Следовательно, общая длина маршрута ш — которая в точности равна с (6) — не может быть меньше, чем йиг,-(-йгн.+... ...
+ йин, = с (т). ( ) Таким образом, теорема !7.3 утверждает, что при наличии неравенства треугольника задача нахождения кратчайшего обхода мсвивалентна задаче нахождения кратчайшего эйлерова остовного графа (обратная импликация очевидна, поскольку обход является частным случаем эйлерова остовного графа). Рассмотрим в связи с этим представленный на рис.
17.8 алгоритм для нахождения короткого эйлерова остовного графа и одного из соответствующих вложенных обходов. Теорема !7.4. Алгоритм дерева является 1-приближенным алгоритмом для ЗКНТ. Доказательство. Прежде всего нужно установить, что 6 эйлеров, с тем чтобы был возможен шаг 3.
Так как граф 6 содержит остовное дерево Т, то он связен. Кроме того, степени всех вершин в графе 6 четны, так как они вдвое больше соответствующих степеней в Т. Оценим теперь ошибку. Если с — стоимость кратчайшего обхода, то, согласно теорсме 17.3, достаточно показать, что с(6)(2 с. Но с(6)=-2 с(Т), где с(Т) — стоимость минимального остовного дерева. Кроме того, с(Т =с: это следует из того, что любой обход (включая кратчайший) можно преобразовать в дерево выбрасыва- 17.2.
Приближенные алгорвамы длл эадачи коммивояжера 497 нием ребра, и длина кратчайшего остовного дерева не превосходит длины получаемого дерева. () Пример 17.2. Пример применения алгоритма дерева приведен на рис. 17.9. Кратчайшее остовное дерево Т показано на рис. 17.9(а), в )о (б) (а) !),2,3,2,4,6,5,7,5,6,В,!0,9, )0,8,6,4,2, )1 (в) (г) (д) Рис.
)7.9. а) Минимальное остовное дерево. б) Эйлеров остовный граф. в) Эйлеров маршрут (подчеркнут выделенный обход) г) !.приближенный обход, д) Кратчайший обход, а граф 0 — на рис. ! 7.9(б). В графе 6 мы находим эйлеров маршрут (рис. 17,9(в)) и выбираем в нем по одному вхождению каждого целого числа из множества (1, 2,..., а) — по определению эйлерова маршрута каждое целое число появляется вием по крайней мере один раз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
