Источник: http://science.ncstu.ru/conf/past/2010/sc-potential/theses/mtransp/27.pdf/file_download
Задача коммивояжёра заключается в отыскании гамильтонова цик-
ла экстремального веса во взвешенном графе. Наиболее полные обзоры
работ по этой задаче можно найти в [8, 9]. Ранее интенсивно исследова
лась задача отыскания гамильтонова цикла минимального веса, которая
является одной из основных NP-полных задач. Однако в последнее вре
мя всё больший интерес уделяется задаче коммивояжёра на максимум.
Как известно, для этой задачи в общем виде существует порог неприбли
жаемости в классе полиномиальных алгоритмов (в предположении, что
P =6 NP).
В статье исследуется естественное обобщение задачи коммивояжёра
на максимум.
В [3] сформулирована задача отыскания графического представле
ния заданного набора натуральных чисел di
, 1 6 i 6 n и 1 6 di < n.
Задача заключалась в построении неориентированного графа G без пе
тель с n вершинами, степени которых равны числам di
Набор чисел .
d1, . . . , dn, для которых существует графическое представление, называ
ется графическим разбиением числа m =
nP
i=1
di
Очевидно, что такое m .
чётно и di 6 n ? 1 для каждого i, 1 6 i 6 n. Однако эти условия не
)Исследование выполнено при финансовой поддержке Российского фон
да фундаментальных исследований (проект 05–01–00395) и INTAS (грант
04–77–7173).
являются достаточными для существования указанного представления.
Например, набор D = (3, 3, 3, 1) не является графическим разбиением.
Конструктивный критерий существования графического разбиения для
набора натуральных чисел может быть получен из следующего утвер
ждения.
Теорема 1 [7]. Разбиение D = (d1, . . . , dp) чётного числа на p частей,
p > d1 > d2 > . . . > dp, является графическим тогда и только тогда, ког-
да графическим является модифицированное разбиение
D = (d2 ? 1, d3 ? 1, . . . , dd1+1 ? 1, dd1+2, . . . , dp).
Это утверждение даёт полиномиальный алгоритм проверки представимости графического разбиения.
Оптимизационный вариант задачи поиска графического представления набора натуральных чисел впервые был упомянут в [4].
Задан полный n-вершинный неориентированный граф G(V,E) без
петель. На рёбрах графа определена весовая функция w : E R, а
для вершин графа заданы такие натуральные числа di, 1 6 i 6 n и
1 < di < n, что набор (d1, ... , dn) является графическим разбиением
суммы
Pn
i=1
В графе G(V,E) требуется найти связный подграф с максимальным суммарным весом рёбер и заданными степенями вершин di,
1 6 i 6 n и 1 < di < n. Эта задача изучалась в [6] и обозначалась как
CSDP (Connected subgraph with given vertex degrees). Задача коммивояжёра на максимум совпадает с CSDP, если степени всех вершин искомого
подграфа равны 2.
Суммарный вес рёбер оптимального решения задачи для графа G
обозначим через W(G). Суммарный вес рёбер решения, полученного с
применением алгоритма A для графа G, обозначим через WA(G). Вели-
чину A = min
G
WA(G)
W(G)
, зависящую от алгоритма A и заданного набора
степеней вершин искомого подграфа, (в случае её существования) назы-
вают оценкой точности алгоритма A.
Задача CSDP называется метрической, если веса рёбер исходного
графа удовлетворяют неравенству треугольника.
Задача CSDP называется евклидовой, если вершинам исходного графа задачи поставлены в соответствие точки в евклидовом пространстве
Rk, и вес любого ребра равен расстоянию между концевыми точками
этого ребра.
Полиномиальный алгоритм приближённого решения метрической за-
дачи CSDP был предложен в [6]. Этот алгоритм применим только для
Об одном обобщении задачи коммивояж?ера на максимум 5
случая чётных значений di. Оценка точности алгоритма не меньше вели-
чины (1 ?
1
d(d + 1)
), где d = min
i=1,...,n
di.
В настоящей статье описывается
новый алгоритм приближённого решения CSDP, работающий произволь-
ных числах di. Проводится его анализ для разных классов исходной за-
дачи с детерминированными входами и обосновываются гарантирован-
ные оценки точности получаемых решений в общем случае, а также в
случаях метрической и евклидовой задач.
Получены следующие оценки точности алгоритма для решения задачи CSDP:
1 ? 1
d(d+1) в общем случае,
1 ? 1
d(d+1) в случае метрической задачи,
d(d+1) в случае евклидовой задачи.
Здесь d = min
i=1,...,n
di.
Кроме того, алгоритм, предложенный для нахождения подграфа с
вершинами произвольной чётности, является алгоритмом приближённо-
го решения задачи коммивояжёра на максимум с гарантированной оцен-
кой точности 2/3. При решении этой задачи его временная сложность
равна O(n3). При этом для метрической задачи коммивояжёра на мак-
симум алгоритм даёт приближённое решение с гарантированной оценкой
точности 5/6. Такой же гарантированной оценкой точности для метриче-
ской задачи коммивояжёра на максимум обладает алгоритм
Косточки–Сердюкова из [1]. Понятно, что для задачи коммивояжёра с
учетом её специфики удаётся получить лучшие оценки точности (см.,
например, [9, гл. 11]) по сравнению с более общей задачей задачей
CSDP.
1. Алгоритм приближённого решения задачи CSDP
Для решения задачи CSDP для заданного графа G предлагается сле-
дующий алгоритм, называемый алгоритмом A.
Шаг 1. С использованием алгоритма Габова из [5] находится такой
подграф G?(V,E?) графа G с заданными степенями вершин, что суммар-
ный вес рёбер в G? максимален.
Шаг 2. В подграфе G? выделяются компоненты связности C1, . . . ,C?.
Если ? = 1, то подграф G? является результатом работы алгоритма A и
алгоритм A заканчивает работу.
Шаг 3. В каждой компоненте Ci (i = 1, . . . , ?) выделяется подмноже-
ство Si её рёбер. Подмножество Si состоит из всех рёбер в Ci, не являю-
6 А.Е.Бабурин, Э.Х. Гимади
щихся перешейками (рёбрами, удаление которых приводит к увеличению
числа компонент связности).
Шаг 4. В каждом множестве Si находится ребро ei = uivi минималь-
ного веса.
Шаг 5. Полагается p1 = v1, q1 = u1, i = 1.
Шаг 6. Если w(qiui+1)+w(pivi+1) > w(qivi+1)+w(piui+1), то полага-
ется qi+1 = vi+1, pi+1 = ui+1. В противном случае полагается qi+1 = ui+1
и pi+1 = vi+1.
Шаг 7. Полагается i = i + 1. Если i < ?, то выполняется шаг 6. В
противном случае выполняется шаг 8.
Шаг 8. Если w(qiu1) + w(piv1) > w(qiv1) + w(piu1), то полагается
q?+1 = v1 и p?+1 = u1. В противном случае полагается q?+1 = u1 и
p?+1 = vi+1.
Шаг 9. Рёбра e1, e2, . . . , e? удаляются из G?, формируется подграф
G??(V,E??), где E?? = E? \ {e1, e2, . . . , e?}.
Шаг 10. Формируется подграф H(V, e E)