Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 83
Текст из файла (страница 83)
С. Г)пгипй йе Магнтит Сн( $п а Сгарй, Епйпгй. СуЬегпе$)сз, 10 (1972), 502 — 506. Комментарии и ссылки 41? 'Задача 5 — иэ [РУ) Рараг))в1)г!он С. г)., Уаппа)га1г!з М. Т)ге С)гйне РгоЫев 1ог Р)апаг бгарйз, 1п1. Ргос. 1.е11егз (в печати). Задачи 9 и 10 взяты из . [бб) бИвоге Р. С,, богпогу )1. С. Зейнепс)пи а Опе 5)а)е-Чаг)ай)е Масйпе: А Зо) чаЫе Сазе ог йе Тгаче1)па За1емпап РгоЫев, 09, 12 (19645 655 — 679. [1.а) 1.аи'1ег Е. 1. А Зо1чаЫе Сазе о1 йе Тгаче1)пи За)емпап РгоЫев, Май.
Ргод., 1 (1971), 267 — 269. Теорему Куратовского можно найти, например, в книге') [Еч) Ечеп 5. бгарй а!ног!!йвз. Ро1овас, Магу1апй Соврн1ег Зс)енсе Ргезз, !979. ') См. также: Харири Ф. Теории графов. Пер. с англ.— Мл Мир, 1973.— 7?рггм. иерее 14 гп вова !7 Приближенные алгоритмы 1 7.1 Эвристики дпя задачи о вершинном покрытии. Пример Рассмотрим задачу ВЕРШИННОЕ ПОКРЫТИЕ ,г(ля данного графа 6=(У, Е) найти наименьшее возможное множество вершин С, такое, что [и, и)ЕЕлоЕС или иЕС.
Это очень важная практическая задача, возникающая, например, когда требуется управлять работой большой сети, управляя как можно меньшим числом вершин. Поэтому, естественно, тот факт, что эта задача ЧР-полна (следствие из леммы 15.4), несколько разочаровывает, Тем не менее для этой задачи имеются некоторые правдоподобные методы получения «хорошнхзз (но, возможно, не оптимальных) решений. Например, многообе;цающей выглядит «жаднаяаз эвристика, представленная на рис. 17.1.
Вход. Граф Гг=(Ч, Е). Выход. Вершинное поирытие С в графе б, предположительно ненамного больше, чем оптимальное. Ьен(п С:=Я; мЬПеЕФЯ бо выбрать в Ч вершину с наибольшей степенью (сонипепт: неопределенность разрешать произвольно), удалить ее из б и добавить и С епд (зио.
17.1. Алгоритм Е Поскольку наша цель в данной задаче — покрыть все ребра графа б наименьшим числом вершин, то стратегия выбора на каждом шаге одной вершины, покрывающей как можно больше оставшихся ребер, нас вполне устраивает. Конечно, в силу йгР.полноты задачи ВЕРШИННОЕ ПОКРЫТИЕ нет надежды, что этот эффективный алгоритм будет всегда давать наименьшее вершинное покрытие Но насколько близко оно будет к оптимуму? Применим указанный алгоритм к графу, представленному на рив. ! 7.2.
Вначале выбирается одна из вершин а„а, или а, степени 5, скажем а„затем оы затем аз и, наконец, с„с„с,, с, и сы Полученное вершинное покрытие состоит из восьми вершин. Однако оптимальное вершинное покрытие содержит всего пять вершин: !7.1. Эвристики дяя задачи о ввришнном покрытии 419 (Ьа, Ь„Ь„Ь„Ь,). Если обобщить этот пример и взять граф с а вершинами типа а, и+2 вершинами типа Ь и и+2 вершинами типа с (и ребрами [сп Ь,) н )а;, Ь1) для всех 4, !), то в новом графе алгоритм ! ГЗ Г4 Г5 а., аз аз Рис. !7аи найдет покрытие из 2л+2 вершин, тогда как оптимальное покрытие содержит только а+2 вершин.
Поскольку значение и не ограничено сверху, ошибка может стать сколь угодно близкой к !00%. с, Гв Г4 45 а, В4 '45 аз Рис. 17,3, Наихудший ли это вариант для данной эвристики или может получаться ошибка даже ббльшая? Судя по приведенному на рис. 17.3 примеру, это действительно возможно. Вначале вершина а, имеет максимальную степень, а именно 5.
После удаления а, вершина а„имеет наиболыпую степень, затем ав и т. д. На каждом шаге среди вершин с наибольшей степенью имеется некоторая вершина типа а, которая и удаляется. В заключение вершинное покрытие дополняется, скажем, всеми вершинами типа с. В этом решении !3 вершин, тогда как оптимальное решение (Ьз, Ь„Ь„Ь„Ь„Ь,) 144 420 Гл, 17. Приближенные алгоритма содержит только 6 вершин. Отклонение от оптимума превышает 100 05„. Чтобы обобщить контрпример, приведенный на рис. 17.3, необходимо вначале понять его структуру. Его можно рассматривать как 6 ребер (рь Ь!), (=-1,..., 6, к которым следующим образом добавлены вершины типа а.
Сначала 6 вершин типа Ь разбиваются на три пары и вершины каждой пары соединяются с некоторой вершиной типа а. Затем вершины типа Ь разбиваются на две тройки и опять все вершины каждой тройки соединяются с новой вершиной типа а. То же самое делаем с четверками, пятерками и т. д., возможно выбрасывая некоторые вершины типа Ь и добавляя каждый раз новую вершину типа а для каждого множества в каждом разбиении. Нетрудно видеть, что при применении алгоритма 1 к полученному графу вершина с наибольшим номером среди оставшихся вершин типа а всегда имеет наибольшую степень. Таким образом, получаемое вершинное покрытие содержит 7 (и)+п вершин, где !.(и)— число вершин типа а в данном графе, а оптимальное вершинное покрытие состоит из и вершннтипа Ь.
Следовательно, алгоритм 1 дает относительную ошибку й(и)!и, Заметим, что Е(л) — -~! ',( и!!' ). Как видно из.табл. 17.1, ( (и)!и может расти очень сильно. В действительности это отношение растет как 10 и Следовательно, на первый взгляд правдоподобный алгоритм 1 для построения вершинного покрытия не имеет фиксированной границы для получаемой в результате относительной (т. е. в процентах) ошибки.
Можно построить примеры, в которых он ведет себя как угодно плохо! Можно ли предложить эвристику для задачи ВЕРШИННОЕ ПОКРЫТИЕ с ограниченной относительной ошибкой? Рассмотрим алгоритм, представленный на рис. !7 4, Получаемое в результате множество вершин С является, оче. видно, вершинным покрытием. Согласно определению, любое вершинное покрытие должно покрывать все ребра, выбираемые данным алгоритмом. Однако эти ребра не имеют общих вершин, и поэтому все они должны покрываться разными вершинами из вершинного покрытия.
Следовательно, любое вершинное покрытие должно содержать хотя бы одну вершину каждого выбранного ребра и поэтому мощность никакого вершинного покрытия не может быть меньше, Таблица !7П и 6 !О 30 !00 !000 !!7 !60 267 380 600 ! (и)!и (о„! чем половина мощности С, Таким образом, относительная ошибка алгоритма 2 не превосходит !00о6. Эта наихудшая ошибка действи- 17.1. Эвристики для эадатс о вершинном покрытии 421 тельно достижима; достаточно взять граф, состоящий из большого числа непересекающихся ребер, На примере задачи ВЕРШИННОЕ ПОКРЫТИЕ и двух праде ложенных звристик мы проиллюстрировали общую идею оценки Вход и выход: как в алгоритме 1. Ьек(п С:=Я; мине ЕФЯ бо выбрать в Е любое ребро !н,с), удалить обе вершины и и т нз 6 и добавить их к С епб Рис. 17.4.
Алгоритм 2. эвристики путем анализа ее ошибки в худшем случае. Эти понятия можно формализовать следующим образом. Определение 17.1. Пусть А — задача оптимизации (минимизации или максимизации) с положительной целочисленной функцией стоимости с, и пусть А — алгоритм, который по данной индивидуальной задаче / задачи А выдает допустимое решение /л(/); оптимальное решение задачи / обозначим через /(/) ").
Тогда А называется в-приближенным алгоритмом для задачи А для некоторого е ) О в том и только в том случае, если ! с ()А(1) ) - с (/ (/)) ~ ~ (е с (/ (/)) для всех индивидуальных задач /. () Например, алгоритм 2 является 1-приближенным алгоритмом для задачи о вершинном покрытии.
Алгоритм 1 не является в- приближенным алгоритмом ни для какого к)0, поскольку — как было указано — его относительная ошибка будет для подходящих индивидуальных задач превосходить любую константную оценку. Для описания поведения в худшем случае таких алгоритмов, как алгоритм 1, мы будем иногда доп>скать, чтобы е. было функцией входа, Например, если п обозначает число вершин в индивидуальной задаче ВЕРШИННОЕ ПОКРЫТИЕ, то можно показать, что алгоритм ! является 1п п-приближенным алгоритмом (задача 2).
Это означает, что для всех графов 6 с п вершинами этот алгоритм выдает множество С, .удовлетворяющее неравенству !С) †!С! ~)пп, !С! где С вЂ” оптимальное вершинное покрытие. ') Некоторые приближенные алгоритмы содержат не полностью определенные шаги, сакие, как предложение в алгоритме 1: неоднозначности разреишть произвольным образом, или шаг в алгоритме 2: выбрать произвольное ребро. В такни ситуаниих в качестве с(/ 1(/й берется самая плохая стоимость, получаемая при применении А к /. Гл.
!7. Приближенние алгоршпни 422 17.2 Приблмженные апг»»ритмы дпя задачи коммивояжера В этом параграфе мы рассмотрим возможность применения идей, описанных в предыдущем параграфе, к задаче коммивояжера (ЗК). Наша цель — построить эффективные алгоритмы, дающие «хорошие» приближенные решения для ЗК. К сожалению, в 2 17.4 будет доказано, что эта задача для общей (т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
