ДОКЛАДЫ АКАДЕМИИ НАУК, 2015, том 461, № 6, с. 644-649
ИНФОРМАТИКА
УДК 519.8
АППРОКСИМИРУЕМОСТЬ ЗАДАЧИ О МИНИМАЛЬНОМ ПО ВЕСУ
ЦИКЛОВОМ ПОКРЫТИИ ГРАФА
© 2015 г. М. Ю. Хачай, Е. Д. Незнахина
Представлено академиком РАН В.И. Бердышевым 14.10.2014 г.
Поступило 10.11.2014 г.
DOI: 10.7868/S086956521512004X
Для заданного наперед числа к исследуется задача о покрытии множества вершин полного взвешенного орграфа (с петлями) G = (V, E, w) семейством из к вершинно-непересекающихся контуров минимального суммарного веса.
Пусть C — произвольный контур в орграфе G. Как обычно, через V(C) и E(C) обозначим подмножества составляющих его вершин и дуг.
На множестве дуг графа G задана весовая функция w: E ^ [, в силу конечности множества E однозначно определяемая матрицей
W = (Wij), 1 < i, j < n,
так, что для произвольных i и j вес дуги e = (i, j) задается соотношением w(e) = Wj. Весом (стоимостью)
контура C назовем величину W(C) = ^ w (e).
е е E( С)
Определение 1. Цикловым покрытием размера к (k-Size Cycle Cover, k-SCC) орграфа G назовем произвольное семейство % = = {C1, ..., Ск} его вершинно-непересекающихся простых контуров, удовлетворяющее условию V(C1) u ... u u V(Ck) = V. Вес °W(%) такого покрытия зададим равенством
В оптимизационной форме данная задача примет вид:
W (%) = £ W( Ct).
Институт математики и механики им. Н.Н. Красовского
Уральского отделения Российской Академии наук, Екатеринбург
Уральский федеральный университет им. Б.Н. Ельцина, Екатеринбург
E-mail: mkhachay@imm.uran.ru
W (%) = £ £ w (е)
i = 1 е е E(Ci)
Задача Minimum-Weight k-Size Cycle Cover Problem (Min-k-SCCP). Задан полный взвешенный орграф G = (V, E, w). Требуется найти цикловое покрытие размера k наименьшего веса.
k ^ min .
UV(C,.) = V; V(C)n V(Cj) = ф, ({i,j} е{1,..., k}) i = 1
Задачей Metric Min-k-SCCP договоримся называть задачу Min-k-SCCP, в которой каждой вершине орграфа G инцидентна петля нулевого веса, функция w симметрична (т.е. Wj = w^ для произвольных i и j), принимает неотрицательные значения и для любой тройки i, j, l справедливо неравенство треугольника wj + w}l > w(l. Орграфу G договоримся сопоставлять взвешенный граф G, получаемый из G отменой ориентации. Поскольку в метрической постановке задачи в силу симметричности весовой функции вес произвольного циклового покрытия не зависит от ориентации составляющих его контуров, договоримся всюду ниже, где это не будет вызывать недопонимания, проводить рассуждения, касающиеся графа G, в терминах цикловых покрытий соответствующего ему неориентированного графа G.
Исследуемая задача о цикловом покрытии размера к наименьшего веса является естественным обобщением классической задачи коммивояжера (Traveling Salesman Problem, TSP) [1], связанной с поиском в полном взвешенном графе G гамильто-нового цикла (маршрута коммивояжера) минимального веса.
Известно [2], что задача коммивояжера NP-трудна даже в евклидовой постановке при произвольном d > 1. Среди наиболее важных результатов
стоит отметить 3 -приближенный алгоритм для задачи Metric TSP [3] и полиномиальную приближенную схему (Polynomial-Time Approximation Scheme, PTAS) для задачи коммивояжера в евклидовом пространстве конечной размерности, разработан-
k
k
ную С. Аророй [9]. Отдельно отметим результаты [4—8], связанные с исследованием вычислительной сложности и аппроксимируемости различных модификаций задачи о нескольких коммивояжерах (^-Peripatetic Salesman Problem, k-PSP), в которой для заданного k в графе G требуется найти оптимальный набор из k реберно-непересекающихся гамильтоновых циклов.
Основное отличие задачи k-PSP от исследуемой в настоящей работе задачи Min-k-SCCP удобно описать в терминах перестановок множества вершин графа G. Если в первом случае цель состоит в поиске специальным образом согласованного набора из k одноцикловых перестановок, то во втором целью поиска является единственная перестановка (минимального веса), разложимая в произведение k циклов.
В работе обоснована труднорешаемость задачи Min-k-SCCP, предложен эффективный 2-прибли-женный алгоритм для задачи Metric Min-k-SCCP и построена PTAS для Euclidean Min-2-SCCP на плоскости.
ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ ЗАДАЧИ Min-k-SCCP
Часть результатов, касающихся вычислительной сложности и аппроксимируемости задачи TSP, удается распространить и на семейство задач Min-k-SCCP, k > 1.
Теорема 1 [10]. Задачи Min-k-SCCP, Metric Min-k-SCCP и Euclidean Min-k-SCCP (в пространстве произвольной фиксированной размерности d > 1) NP-трудны в сильном смысле1 при произвольном фиксированном k > 1.
Модифицируя технику, использованную в [11] при доказательстве неаппроксимируемости задачи TSP, на случай k циклов, нетрудно показать, что задача Min-k-SCCP (при произвольном k > 1) не допускает полиномиальной аппроксимации с точностью O(2n), если P Ф NP. Ниже показано, что, как и в случае задачи коммивояжера, задача Min-k-SCCP в метрической постановке принадлежит классу APX задач комбинаторной оптимизации, обладающих полиномиальными приближенными алгоритмами с фиксированной точностью, а Euclidean Min-k-SCCP обладает полиномиальной приближенной схемой (PTAS).
2-ПРИБЛИЖЕННЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ Metric Min-k-SCCP
В целом, алгоритм повторяет схему известного 2-приближенного алгоритма [3] для метрической задачи коммивояжера. Без ограничения общности полагаем n > k, так как при n < k постановка
1 То есть для них не существует точных псевдополиномиаль-
ных алгоритмов, при условии P Ф NP.
задачи теряет смысл, а при n = k процедура поиска оптимального решения элементарна. Здесь и ниже договоримся использовать стандартные обозначения APP и OPT для веса циклового покрытия, найденного приближенным алгоритмом, и оптимального циклового покрытия соответственно (в обоих случаях имеющего размер k).
Алгоритм 1.
1. Применяя естественную модификацию [10] алгоритма Борувки—Краскала [12], строим остов-ный k-лес минимального веса.
2. Удваиваем ребра построенного леса, преобразуя таким образом все его непустые деревья в эйлеровы подграфы.
3. В каждом полученном эйлеровом подграфе находим эйлеров маршрут, который стандартным образом преобразовываем в гамильтонов цикл (для данной компоненты связности).
4. В качестве ответа выдаем построенную совокупность циклов, дополненную необходимым числом вырожденных одновершинных маршрутов.
Утверждение 1 [10]. Вес APP-приближен-ного решения задачи Metric Min-k-SCCP, построенного Алгоритмом 1, удовлетворяет соотношению
OPT < APP < 2OPT. (1)
Заметим, что оценка точности (1) Алгоритма 1 не зависит от k и асимптотически достижима при произвольном фиксированном k > 2, а его трудоемкость может быть оценена сверху O(n2logn). Таким образом, Алгоритм 1 сохраняет свои ап-проксимационные свойства даже в том случае, когда параметр k является частью входа решаемой задачи.
ПРИБЛИЖЕННАЯ ПОЛИНОМИАЛЬНАЯ СХЕМА ДЛЯ ЗАДАЧИ Euclidean Min-2-SCCP НА ПЛОСКОСТИ
Определение 2. Полиномиальной приближенной схемой (PTAS) для задачи комбинаторной оптимизации называется семейство алгоритмов, содержащее для каждого фиксированного c > 1 приближенный алгоритм, решающий данную задачу с гарантированной точностью
^ 1 + за время, ограниченное сверху некоторым
полиномом от длины записи ее исходных данных (при этом порядок и коэффициенты полинома могут, вообще говоря, зависеть от c).
Предварительное преобразование условия задачи
Покажем, что для произвольной постановки исследуемой задачи справедлива одна из двух аль-
тернатив, проверка которых может быть осуществлена за полиномиальное время:
1) задача допускает полиномиальное сведение к двум независимым задачам Euclidean TSP;
2) расстояние между узлами исходной задачи ограничено сверху некоторой линейной функцией от OPT.
Применяя упоминавшуюся выше модификацию алгоритма Борувки—Краскала, построим минимальный остовный лес из двух деревьев T1, T2.
Как известно, диаметр D множества и радиус R описанной вокруг него сферы в J-мерном евклидовом пространстве связаны между собой неравенством Юнга:
- D < R <( —dd-2 V 2 d +
D,
принимающем в рассматриваемом нами случае евклидовой плоскости вид:
1D < R < D. 2 3
(2)
Пусть далее Db D2 — диаметры подмножеств F(T1) и V(T2) (вершин деревьев T1, T2 соответственно); R1 и R2 — радиусы описанных вокруг них окружностей; p(T1, T2) — расстояние между центрами этих окружностей. Для D = max{D1, D2} справедливо следующее
Утверждение 2. Если для графа G = (V, E, w) выполнено соотношение
р(T-, T2)> 5R, (3)
то произвольное оптимальное решение задачи Euclidean Min-2-SCCP состоит из подходящих оптимальных решений задач Euclidean TSP для подграфов G(T1) и G(T2), индуцированных деревьями T1 и T2. В противном случае диаметр множества V
не превосходит ^j--3 OPT.
Таким образом, в случае выполнения неравенства (3) наличие PTAS для задачи Euclidean Min-k-SCCP следует из аналогичного результата [9] для задачи Euclidean TSP, поскольку искомая полиномиальная приближенная схема может быть получена комбинацией полиномиальных схем для подзадач, порожденных деревьями T1 и T2.
Остановимся на рассмотрении частного случая задачи Euclidean Min-2-SCCP, для которого (3) не выполняется.
Округленная задача Euclidean Min-2-SCCP. Для построения PTAS для общей задачи Euclidean Min-2-SCCP достаточно построить аналогичную схему для некоторого ее подкласса. По аналогии с понятием округленной задачи TSP, введенным в [9], введем понятие округленной задачи Euclidean Min-2-SCCP.
Определение 3. Округленной назовем постановку задачи Euclidean Min-2-SCCP, для которой выполняются следующие ограничения: все вершины графа имеют целочисленные координаты x,y е {0, ..., O(n)} и вес произвольного ребра ву больше или равен 4.
С помощью линейных преобразований координатной сетки постановке задачи Euclidean Min-2-SCCP можно сопоставить округленную постановку так, чтобы стоимость любой пары маршрутов изменилась несущественно. Справедливо следующее утверждение.
Лемма 1 [10]. PTAS для округленной Euclidean Min-2-SCCP индуцирует PTAS для общей задачи Euclidean Min-2-SCCP.
Опишем построение PTAS для округленной задачи Euclidean Min-2-SC
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.