Содержание к диссертации
Введение
Глава 1. Задачи поиска гамильтоновых циклов экстремального реберного веса 20
1.1. Задачи коммивояжера в евклидовом пространстве 20
1.1.1. Постановка задачи 20
1.1.2. Алгоритм А. И. Сердюкова 20
1.1.3. Модифицированный алгоритм А 23
1.2. Задачи поиска двух реберно непересекающихся гамильтоновых циклов экстремального веса 28
1.2.1. Общая постановка задачи 28
1.2.2. Задача на максимум с одной весовой функцией 28
1.2.3. Метрическая задала на минимум с одной весовой функцией 37
1.2.4. Метрическая задача на минимум с двумя весовыми функциями 41
Глава 2. Задачи поиска связных подграфов с ограничениями на степени вершин 50
2.1. Задача поиска подграфа с заданными степенями вершин максимального реберного веса 50
2.1.1. Постановка задачи 50
2.1.2. Описание приближенного алгоритма 50
2.1.3. Анализ алгоритма 52
2.2. Задача поиска регулярного связного подграфа экстремального реберного веса 58
2.2.1. Постановка задачи 58
2.2.2. NP-трудность 58
2.2.3. Описание приближенного алгоритма решения задачи . 60
2.2.4. Вероятностный анализ алгоритма 65
2.2.5. Случай независимого равномерного распределения элементов матрицы расстояний 67
2.2.6. Случай минорирующей функции распределения элементов матрицы расстояний, заданных независимо 77
2.2.7. Некоторые обобщения 78
Глава 3. Задача разбиения множества векторов 80
3.1. Постановка задачи 80
3.2. Решения задачи в полиэдральном пространстве (Rk, с) с конечной нормой 80
3.3. Решение задачи в ft-мерном евклидовом пространстве 82
3.3.1. Области принадлежности решения 82
3.3.2. Описание алгоритма 86
Заключение 87
Список публикаций автора по теме диссертации 89
Благодарности 91
Литература 92
- Задачи поиска двух реберно непересекающихся гамильтоновых циклов экстремального веса
- Метрическая задача на минимум с двумя весовыми функциями
- Задача поиска регулярного связного подграфа экстремального реберного веса
- Случай минорирующей функции распределения элементов матрицы расстояний, заданных независимо
Введение к работе
Теоретические исследования, связанные с вопросами сложности задач дискретной оптимизации, а также с построением и анализом эффективных приближенных алгоритмов решения этих задач, находятся в русле современных, интенсивно развивающихся областей математики. Терминология, возникающая в ходе этих исследований, широко распространена в современной научной литературе и требует определенного с ней знакомства.
На вопрос, для чего надо иметь представление о сложности решаемых задач, наиболее наглядный ответ дан во введении к книге [11]. В этой книге приводится более 300 задач (из самых разных областей, включая теорию графов и сетей, теорию расписаний, теорию автоматов и языков, оптимизацию программ, базы данных, игры и головоломки и т.п.), для которых в настоящее время нет основании надеяться па построение эффективных алгоритмов их решения.
В результате бурного развития вычислительной техники появилась возможность решать не отдельную конкретную задачу, а разрабатывать методы и программы, рассчитанные на целый класс задач, получающихся одна из другой заменой ряда исходных данных. Поэтому целесообразно говорить о сложности не для одной индивидуальной задачи /, а для массовой задачи, или проблемы Y\, соответствующей множеству индивидуальных задач.
Задачи дискретной (комбинаторной) оптимизации образуют важный класс упомянутых массовых задач. Для задачи J] дискретной оптимизации решением каждой индивидуальной задачи / Є П является произвольная реализация оптимума Оріц(І) := та,хгЄ$п{і) f{\(I,z) Здесь *%(/) — область допустимых значений дискретной (целочисленной) переменной z, /д(/, г) : [](/) ~~* ^+ целевая функция индивидуальной задачи / оптимизации, знак max в постановке задачи может быть заменен на min.
Большинство дискретных и комбинаторных задач допускает решение с по-
мощью некоторого процесса перебора вариантов. Вместе с этим число возможных вариантов, я, следовательно, и время решения растет экононеициально от размеров задачи. Так, например, в задаче коммивояжера число всевозможных маршрутов растет как факториал от "размера" задачи (числа вершин графа). Поэтому переборные алгоритмы решения массовых задач считаются неэффективными. В отличие от них эффективными называются полиномиальные алгоритмы решения массовой задачи, т.е. такие, которые решают произвольную задачу / Є П за время, ограниченное полиномом от "размера" входных данных задачи /. Несмотря на определенную условность этого разделения с точки зрения практического счета, объясняется оно прежде всего тем, что центральным для дискретной оптимизации является вопрос, можно ли построить алгоритм решения массовой задачи (т.е. любой индивидуальной), не перебирающий всех или почти всех вариантов ее решения. В этой связи выделяют класс Р задач дискретной оптимизации, разрешимых за полиномиальное время (в зависимости от длины входа), а также класс iVP-трудиых задач, для которых построение полиномиальных алгоритмов проблематично (в предположении Р не равно NP) (11). Одной из фундаментальных проблем современной математики является вопрос: существует ли полиномиальный алгоритм решения ЛгР-трудных задач? Многие исследователи склоняются к отрицательному ответу на данный вопрос.
Алгоритм А называется приближенным алгоритмом решения массовой задачи Г] оптимизации, если для произвольного / Є П он находит некоторую точку из допустимой области z^(I) Є 5rj(/), принимаемую за приближенное решение. Значение /rj(/, 2^(/)) называется приближенным значением оптимума и обозначается через Л(1).
Говорить об абсолютной погрешности приближенного алгоритма решения массовой задачи оптимизации (па классе всевозможных индивидуальных задач) обычно не имеет большого смысла, так как для разных индивидуальных
задач величина оптимума может быть как сколь угодно большой, так и малой. Поэтому целесообразно анализировать относительную точность приближенных алгоритмов.
Иногда при анализе приближенного алгоритма удается показать определенные гарантированные оценки качества решения, получаемого в ходе его работы для произвольной индивидуальной задачи.
Зачастую при наложении определенных условий на входные данные для задачи удается построить ^-приближенный алгоритм.
Приближенный алгоритм А решения массовой задачи J| оптимизации называется е-приближеиным алгоритмом решения Y\ Для некоторого є > 0, если для произвольной / Є Р
Optn(I)-A(I)
Optn(I)
т.е. его относительная погрешность не превосходит Є.
Величину
. Л(1) mm
/єп Optn{I)
(если она существует) называют оценкой точности алгоритма А для задач максимизации. Аналогично определяется оценка точности алгоритма для задач минимизации.
Зачастую целевая функция принимает только целочисленные значения. Если для какого-то подкласса задач удается показать, что произведение относительной погрешности алгоритма на верхнюю оценку целевой функции меньше 1, то такой алгоритм на этом подклассе задач находит точное решение.
Одной из самых широко известных и исследованных задач комбинаторной оптимизации является задача коммивояжера (далее ЗК). ЗК заключается в отыскании экстремального но длине гамильтонова цикла в заданном графе. ЗК известил среди математиков и статистиков под разными названиями. В [28]
ЗК связывается со знакомой статистикам задачей средних минимальных расстояний.
Стоит отметить, что систематическое исследование ЗК как задачи комбинаторной оптимизации началось с работы [30]. Обзоры [50, 55, 60, 62] и книги [54, 59] содержат описание основных достижений в исследованиях данной задачи.
Кратко представим постановку ЗК:
Задано множество С, состоящее из п городов и матрица d(ci, с,-) Є N расстояний между ними. Допустимым решением является простой обход множества С, т.е. одіюцикличная перестановка городов. Требуется найти допустимое решение, обладающее максимальной длиной соответствующего обхода.
В целом ряде работ ЗК рассматривалась с точки зрения выявления полиномиально разрешимых подклассов. Первый нетривиальный полиномиально разрешимый случай этой задачи был описан в [41]. В упомянутой работе исследовались случаи, когда оптимальное решение определялось простым многоугол-пиком на плоскости. Один из наиболее известных полиномиально разрешимых случаев, имеющих большое практическое применение, представлен в [25, 44].
Ввиду богатой истории исследования ЗК, широкое распространение и известность получили также различные ее модификации и обобщения.
Например, ранее интенсивно исследовалась только ЗК на минимум. Однако в последние десятилетия вес больший интерес уделяется ЗК на максимум. Как известно, для этой задачи в общем виде существует порог неприближаемости в классе полиномиальных алгоритмов (в предположении Р ф NP) [38, 57]. В работах [10, 13, 21, 23, 24, 26, 40, 48, 52] были предложены полиномиальные алгоритмы с гарантированными оценками для решения ЗК на максимум.
Так для метрической ЗК на минимум (вышеупомянутая задача с условием выполнение неравенства треугольника для матрицы d(Cj,Cj) расстояний) известен полиномиальный ^-приближенный алгоритм Кристофидеса-Сердюкова
[27], [IS).
Одним из основных исследуемых подклассов ЗК па максимум является евклидова задача. ЗК на максимум называется евклидовой, если вершинам заданного графа сопоставлены точки в евклидовом пространстве Rk , а длины дуг между вершинами определяются как расстояния между точками, соответствующими этим вершинам. В [56] показано, что евклидова задача коммивояжера на минимум является NP-трудной в случае, если размерность пространства превышает 2. Этот же сложностной статус имеет евклидова ЗК на максимум [39].
В работе [20] был представлен асимптотически точный алгоритм Л решения ЗК на максимум в ^-мерном евклидовом пространстве Rk . Трудоемкость алгоритма определялась трудоемкостью отыскания максимального паросочетания в заданном графе. Получаемый гамильтонов цикл содержал все ребра данного паросочетания.
В работе [4] была представлена модификация этого алгоритма, имеющая такие же оценки точности, но более простая в изложении. Несмотря на сходство подходов, гамильтонов цикл, получаемый этим алгоритмом, строился проще и не содержал ребер максимального паросочетания, за исключением, быть может, двух.
Изучение этих алгоритмов показало, что возможно пересмотреть некоторые их шаги с тем, чтобы на более узком классе задач улучшить получаемые оценки точности. Основной результат первой части главы 1 данной диссертации -построение и анализ такой модификации.
Так как относительная точность алгоритма является величиной безразмерной, то масштабирование графа (растяжение соответствующего пространства Rk на неотрицательную величину) не изменяет оценки точности алгоритмов. Будем полагать, что длина минимального ребра графа равна 1. В этом случае отношение максимальной длины ребра графа к минимальной является диамет-
ром множества его вершин (в дальнейшем просто диаметром).
Оказывается, что при наложении достаточно слабых ограничений па диаметр множества вершин исходного графа, алгоритмы из [20] и [4] допускают хорошую, с точки зрения улучшения оценок точности, модификацию.
Вполне естественно, что специфика задачи, определяемая дополнительными ограничениями, может быть использована в ходе работы алгоритма. Однако эти же ограничения создают дополнительные трудности при обосновании полиномиальной сводимости одних задач к другим, тем самым, оставляя открытым вопрос о сложностпом статусе исходных. Так, например, общая задача коммивояжера па максимум является iVP-трудной, однако вопрос об iVP-трудпости этой задачи для иланарных графов или точек в евклидовой плоскости остается на текущий момент открытым.
В численных экспериментах данные представляются числами с фиксированным количеством разрядов. Исходя из соображений масштабируемости задачи, предположим, что задаваемые таким образом точки лежат в вершинах целочисленной решетки Ък.
Обозначим за 5к{Х) диаметр множества вершин исходного графа G, построенного на множестве точек X и имеющего п вершин. При этом все вершины графа лежат в шаре с радиусом, равным 6^(Х), но находятся на расстоянии не меньшем 1 друг от друга. Тогда верно следующее неравенство:
5к{Х)>скпК (1)
где ск — константа, зависящая только от размерности пространства Rk .
Предлагаемая в главе 1 модификация алгоритма А. И. Сердюкова является асимптотически точной при выполнении следующих условий:
о (пі), если к = 2;
№)=\ (4~п^ если к=з- (2)
Зк-]
о(п^^), если А: > 3. Модификация обладает лучшими оценками точности по сравнению с алгоритмами [4, 20] при;
I Сгпе, если к — 2;
№И j Сз^, если^ = 3; (3)
1 , 4
Скпк ^^, если А > 3, где С* — константа, зависящая только от размерности пространства Rk .
Сравнивая накладываемые ограничения 3 и естественное неравенство 1, видим, что описанная область входных данных достаточно велика, особенно при малых к.
Приведенные соображения показывают важность данного подкласса евклидовой задачи коммивояжера па максимум.
Во многих задачах оптимизации в заданном взвешенном графе требуется отыскать подграф (клику, доминирующее множество, остовное дерево, гамиль-тонов цикл, вершинное покрытие и т. п.) минимального или максимального веса. Естественными модификациями подобных задач являются задачи, в которых требуется найти несколько (вершинно или реберно) непересекающихся подграфов определенного типа минимального или максимального суммарного веса. Одной из первых задач этого типа, привлекших внимание исследователей, является задача о т бродячих торговцах (т-peripatetic salesman problem [53], далее m-PSP). В задаче m-PSP задан полный п-вершинный неориентированный граф G — (V, Е) с неотрицательной весовой функцией ребер w : Е —* Е+. Требуется найти т таких непересекающихся по ребрам гамильтоновых циклов
#i,... ,Нт С Е, 10
что величина {суммарный вес ребер найденных циклов)
т к=1 eetft
минимальна (или максимальна).
В [32] показано, что задача о существовании двух непересекающихся гамиль-тоновых циклов NP-полна, что влечет NP-трудность 2-PSP (как на минимум, так и на максимум).
В работе [31] рассмотрены некоторые полиномиально разрешимые случаи задачи 2-PSP на минимум. Работы [32-34] посвящены построению и анализу нижних и верхних оценок в задаче 2-PSP на минимум с целью использования этих оценок в методе ветвей и границ. В работе [35] применяется полиэдральный подход к решению m-PSP. В работе [29] для решения метрической задачи 2-PSP па минимум анонсирован алгоритм с оценкой 9/4.
В разделе 1.2.1 диссертации рассматривается задача 2-PSP на максимум. Для нахождения приближенного решения задачи построен алгоритм с временной сложностью 0(п3) и гарантированной оценкой точности 3/4.
В следующем разделе диссертации рассматривается задача 2-PSP на минимум. Эта задача возникает, например, при планировании одновременной работы двух роботов, обрабатывающих п деталей на плате. Каждый из роботов совершает замкнутый обход всех деталей. В интересах технологической безопасности прохождение роботов по одному и тому же ребру запрещается. При этом требуется минимизировать суммарное время, затрачиваемое роботами на обработку деталей.
Для решения задачи построены полиномиальные приближенные алгоритмы с временной сложностью 0(п^). Показано, что гарантированные оценки точности асимптотически (с ростом п) равны 9/4 (в случае одной весовой функции) и 12/5 {в случае двух весовых функций). Получение оценок существенно опирается на классический результат Кристофидеса (см., например, в [15]) и Сердю-
кова [18], предложивших (независимо друг от друга) приближенный алгоритм построения гамильтонова цикла в полном графе с расстояниями, удовлетворяющими неравенству треугольника. Этот алгоритм, называемый далее алгоритмом КС, находит решение с гарантированной оценкой точности 3/2 за время 0(п3), определяемое сложностью отыскания совершенного паросочетаиия минимального веса (см., например, [43]). При построении первого алгоритма (в случае одной весовой функции) была использована техника склеивания циклов 2-фактора в гамильтонов цикл, примененную Сердюковым и Косточкой [14].
В главе 2 диссертации исследуется такое естественное обобщение ЗК, когда в полном взвешенном графе выбирается остовный связный подграф со степенями вершин, отличными от 2.
В [47] сформулирована задача отыскания графического представления заданного набора натуральных чисел di (і = 1,..-, їт-), і < dj < п. Задача заключалась в построении простого неориентированного графа G без петель с п вершинами, степени которых совпадали бы с числами dj. Набор чисел d\,..., dn, для которых существует соответствующее графическое представление, называ.-ется графическим разбиением числа т — ^21=1^- Очевидно, что любое такое т четно и di < п — 1 для каждого і — 1,..., п. Однако, эти условия не являются достаточными для существования указанного представления. Например, набор D - (3,3,3,1) не является графическим разбиением. Конструктивный критерий существования графического разбиения для набора натуральных чисел может быть получен из следующего утверждения, доказанного в [49]:
Разбиение D — (di,..., dv) четного числа па р частей, р > d\ > d2 > ... > dp, является графическим тогда и только тогда, когда графическим является модифицированное разбиение D' = (cfe - 1* ^з - 1. . d^+i — 1> ^,+2, , dp).
Это утверждение дает нам полиномиальный алгоритм проверки представимости графического разбиения.
Оптимизационный вариант задачи поиска представления набора натуральных чисел впервые был упомянут в [37].
В [42] для задачи поиска Ar-связного подграфа минимального реберного веса с заданными степенями вершин в графе, веса ребер которого удовлетворяют неравенству треугольника, был предложен полиномиальный алгоритм с гарантированными оценками точности.
В диссертации рассматривается задача, представленная в [46], где она обозначалась как CSDP (Connected subgraph with given vertex degrees). Задача состоит в отыскании связного подграфа G исходного графа G, обладающего максимальным весом ребер и имеющего заданные степени вершин.
Заметим, что задача коммивояжера совпадает с CSDP, если степени всех вершин искомого подграфа G равны 2.
Задача CSDP называется метрической, если веса ребер исходного графа G удовлетворяют неравенству треугольника.
Задача CSDP называется евклидовой, если вершинам исходного графа G задачи сопоставлены точки в евклидовом пространстве Rk, и вес любого ребра равен расстоянию между точками, соответствующими концам этого ребра.
Приближенный алгоритм решения метрической задачи CSDP был предложен в [46]. Этот алгоритм применим только для случая четных значений сЦ. Оценка точности алгоритма была не меньше величины {1 — ju+l\), где d — минимальное значение заданных степеней вершин искомого подграфа.
В данной работе представляется новый приближенный алгоритм решения CSDP, работающий независимо от четности чисел d{. Проводится его анализ для разных классов исходной задачи с детерминированными входами и обосновываются гарантированные оценки точности получаемых решений в общем случае, а также в частных случаях метрической и евклидовой задач. Алгоритм имеет временную сложность 0(Мп?), где М - число ребер в искомом подграфе.
Для алгоритма решения задачи CSDP получены следующие оценки точно-
сти:
1 ~ ЩЩ h бЩем елучае, Дл > < 1 - жщт в случае метрической задачи ,
1 - Jfd+n в слУчае евклидовой задачи. Здесь сі — min{di|i = 1,..., п}.
Кроме того, алгоритм, предложенный на случай произвольных степеней вершин выбираемого подграфа G, является приближенным алгоритмом решения задачи коммивояжера на максимум с гарантированной оценкой точности 2/3. При решении этой задачи его временная сложность равна 0(п2). При этом для метрической задачи коммивояжера на максимум алгоритм дает приближенное решение с гарантированной оценкой точности 5/6. Такой же гарантированной оценкой точности для метрической задачи коммивояжера на максимум обладает алгоритм Косточки и Сердюкова из [14]. Понятно, что для непосредственно задачи коммивояжера с учетом ее специфики удается получить лучшие оценки точности (см., например, [59], глава 11) по сравнению с более общей задачей — задачей CSDP.
При вероятностном анализе алгоритмов часто используются обозначения и определения, представленные в [5].
Рассмотрим алгоритм А решения оптимизационной задачи на максимум. Алгоритм А имеет оценки (єп, 6п) в классе Рп задач максимизации размерности п, если для каждого п выполнены следующие неравенства:
I OptPn{I) )
где Pr{ J} — вероятность соответствующего события J. Величина еп называется относительной погрешностью, 5п — вероятностью несрабатывания алгоритма А.
Приближенный алгоритм называется асимптотически точным в классе задач Yl — U{P„|n = 1,2,...}, если для него существуют такие оценки (є„, 6п),
что єп —* 0, 6п —* 0 при п —+ оо.
Впервые вероятностный анализ был продемонстрирован А. А. Боровковым в [2] применительно к задачам дискретной оптимизации — ЗК и задаче о назначениях на случайных входных данных. Им был предложен полиномиальный алгоритм, который почти всегда дает решение ЗК на минимум с константной относительной погрешностью. Позже для ЗК па случайных входных данных был реализован асимптотически точный подход, основанный на использовании неравенства Чебышева ([6-8] для задачи на минимум, [3, 63) - для задачи на максимум). В работах |9,45, 46] для обоснования условий асимптотической точности полиномиальных алгоритмов решения ЗК на случайных входах была использована теорема Петрова [16], позволившая получать лучшие оценки для вероятности несрабатывания алгоритма.
Ряд результатов вероятностного анализа алгоритмов решения различных задач комбинаторной оптимизации может быть найден в [22, 51, 58].
Для решения задачи отыскания d-однородного оетовного связного подграфа максимального суммарного веса в [46] был предложен приближенный алгоритм в предположении, что число вершин п графа G кратно величине d— 1. Времен- пая сложность алгоритма 0(п2), В работе (46| были представлены результаты вероятностного анализа этого алгоритма в случае, когда входные данные (веса ребер графа С?)—случайные независимые переменные с одинаковой функцией равномерного распределения.
В диссертации доказывается NP-трудность задачи и описывается новый приближенный алгоритм, дающий улучшенные оценки качества его работы но сравнению с теми, что были получены в работе [46]. При этом удалось снять ограничение на кратность числа вершин графа G. Проведен вероятностный анализ алгоритма на случайных исходных данных и получены условия асимптотической точности предложенного алгоритма как в случае равномерного распределения весов ребер, так и в случае распределений минорирующего типа. Алгоритм,
имея временную сложность 0(п + nd\nn), отыскивает асимптотически точное решение при d = о{п). Таким образом, при d < ^ асимптотически точное решение может быть получено за время 0(п2).
В заключение главы 2 алгоритм модифицируется на случай минимизацион-ной версии задачи. К условию асимптотической точности модифицированного алгоритма добавляется дополнительное ограничение па разброс весов ребер графа.
В главе 3 исследуются задачи выбора подмножества векторов, отвечающего тем или иным критериям оптимальности. Пусть в векторном пространстве Rk с нормой ||.||,, которое будем обозначать через (Я*, ||.||,), задано конечное семейство ненулевых векторов V = {і>і,г>2,... ,}. Определим функцию Sv(x) — YA=ivixi переменной х — {х\,Х2,. .Ухп) Є Rn. Рассматриваются две задачи:
Для заданного семейства входных векторов V требуется найти вектор х Є {0,1}", максимизирующий функцию ||V(:c)||*-
Для заданного семейства входных векторов V требуется найти вектор х є {-1,1}п, максимизирующий функцию ||5v(a;)||*.
Данная модель может быть применена к решению задач выбора оптимального (максимизирующего прибыль) производства на предприятии, когда некоторые характеристики выбираемых компонент могут иметь отрицательный знак (затраты на ресурсы). Тогда каждая компонента может быть представлена вектором, координаты которого - ее характеристики. При суммировании векторов (одновременном выборе ряда компонент производства) соответствующие координаты складываются (как и соответствующие им характеристики компонент). Роль целевой функции играет оценка эффективности производства.
В формальной постановке первой задачи значение переменной Х{ отвечает за выбор или невыбор вектора г!*. Например, если х = (1,1,..., 1), то все векторы
будут выбраны, а если х = (О, О,..., 0), то все векторы будут не выбраны. Тем самым, первая задача является задачей выбора подмножества векторов с целью максимизации нормы суммы элементов выбранного подмножества.
Нетрудно заметить, что первая задача полиномиально сводится ко второй задаче: ее решение легко строится из решения второй задачи с набором векторов
В то же время имеет место и обратная сводимость. Те.м самым, упомянутые две задачи полиномиально эквивалентны.
Данные задачи упоминаются в статье [12], в которой исследуется условная сходимость векторных рядов в конечномерном евклидовом пространстве. Однако вопрос об отыскании эффективной процедуры решения задачи в работе не рассматривается. Вопрос об эффективности такого алгоритма рассмотрен позже в статье Jl]. В ней предполагается возможность достижения временной сложности процедуры 0(пк~1), хотя сам алгоритм не приводится.
Отметим, что минимизационный вариант задачи исследовался Дворецким в [36), который в 1963 г. сформулировал проблему нахождения функции
/(&) = sup{ min ||5іл(х)||2|КєЯ*,гаах|НІ2<1}.
ГЄ{-1,1}" vV
Эта проблема до сих пор открыта.
С подходами к приближенному решению аналогов предложенных задач на минимум можно ознакомиться в работе [17].
Учитывая эквивалентность задач, в дальнейшем мы ограничимся рассмотрением только второй задачи (когда координаты векторы х принимают значения 1 и -1), которую будем называть задачей разбиения множества векторов.
Обозначим через {о, 6) скалярное произведение векторов а и Ъ из Ик. Рассмотрим выпуклый полиэдр В = {х Є Rfc | (Aj,x) < 1, 1 < і < т} с т гранями Fi, 1 < і < т, такими, что F{ с {х Rfc | {Хг,х) = 1}, где А, Є Rfc.
Полиэдральной нормой вектора х Є Rk называется величина
с(х) = гаах|0,{Лі,л:),...,(Лт,я:)|.
Заметим, что если полиэдр В несимметричен, то полиэдральная норма не является нормой в классическом понимании, так как аксиома \\ах\\ = \а\\\х\\ может нарушаться для отрицательных значений а. Такие нормы иногда называют несимметричными нормами. Более подробную информацию о них можно найти в [61]. Если же полиэдр В симметричен, то полиэдральная норма удовлетворяет всем аксиомам нормы. Примерами полиэдральных норм являются нормы 1\ и
'со-
В дальнейшем под полиэдральным пространством размерности к будем понимать пару (R*, с). Полиэдр В в норме с является единичным шаром. Если В — ограниченное множество, то полиэдральную норму с будем называть конечной.
Также исследуется поставленная задача в ^-мерном евклидовом пространстве (Rk,l2)-
Напомним, что для и Є Rk эта норма определяются следующим образом:
||u||2 = \/ Основным результатом главы являются следующие утверждения: Рассмотренная задача разбиения множества векторов является полиномиально разрешимой в fc-мерном полиэдральном пространстве (#*, с) с конечной нормой с, а также в пространстве (й*,^). Основные результаты диссертации докладывались на Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004), на Международной научной студенческой конференции (Новосибирск, 2000), па Международных конференциях по исследованию операций OR2002 (Клаген-фурт, 2002), OR2003 (Гейдельберг, 2003), OR2004 (Тилбург, 2004), на Всероссийской конференции "Методы оптимизации и экономические приложения" (Омск, 2003, 2006), на семинаре проф. Брукера университета г. Оснабрюк (Оснабрюк, 2004), па семинаре по дискретной математике Санкт-Петербургского отделения Института математики им. Стеклова (Санкт-Петербург, 2005), на семинаре Объединенного Института Проблем Информатики (Минск, 2007), на научных семинарах Института математики им. Соболева СО РАН. В основе алгоритма лежит общая идея, впервые реализованная А. И. Сердю-ковым [19] при построении приближенного алгоритма для нахождения одного гамильтонова цикла максимального веса в полном неориентированном взвешенном графе с теми же оценками временной сложности и точности. Алгоритм Сердюкова в исходном графе находит два подграфа - 2-фактор и паросочета-ние, суммарный вес которых не менее чем в 3/2 раза больше веса оптимального решения. Затем ребра этих подграфов перераспределяются между двумя частичными турами, произвольно дополняемыми до гамильтоновых циклов. Максимальный из построенных циклов (по весу входящих в него ребер) дает решение с оценкой точности 3/4. Нетрудно понять, что прямое применение этой схемы к задаче 2-PSP не приводит к успеху, поскольку построенные таким образом частичные туры могут содержать одинаковые ребра. В настоящей диссертации представлен алгоритм, в котором в качестве исходного подграфа, подвергающегося разбиению на два непересекающихся но ребрам частичных тура, используется либо кубический подграф (при четном п), либо "почти кубический" подграф (при нечетном п) максимального веса. Более того, найденные реберно непересекающиеся частичные туры в дальнейшем удается дополнить до непересекающихся но ребрам гамильтоновых циклов, что далеко не всегда возможно в случае произвольных реберно непересекающихся частичных туров. В процессе работы алгоритм обращается к процедуре отыскания в полном взвешенном графе G = (V, Е) такого подграфа Н максимального суммарного реберного веса, что степени его вершин удовлетворяют следующим ограничениям снизу и сверху: /„ d(v) uv, v Є V. В качестве такой процедуры используется алгоритм Габова из [43], который имеет временную сложность o(min{[:logn 2}E;=1 )- Перейдем к формальному описанию предлагаемого алгоритма. Этап 0. При п 13 задача решается полным перебором. На этом алгоритм закапчивает свою работу. Иначе осуществляется переход на этап 1. Этап 1. Вводится новая весовая функция ребер w(e) = w(e) L, где С использованием процедуры из [43] к графу G с весовой функцией w, находится подграф максимального веса G = (V,E) такой, что 3 (IQ(V) 4, v Є V. Пусть G = (V, Е) - дугой такой подграф и \Е\ \Е\. Тогда Отсюда следует, что подграф G имеет минимально возможное число ребер. Значит, и случае четного п подграф G является кубическим, а в случае нечетного п оп имеет только одну вершину степени 4, а степени остальных его вершин равны 3. Так как вес подграфа G относительно весовой функции w равен J2eeE w(e) ЦЩ то этот подграф будет иметь максимальный вес относительно весовой функции w среди всех таких графов. Переход на этап 2. Этап 2. В графе G = (V, Е) веса ребер w (e) переопределяются следующим образом: В графе G с такими весами ребер находится подграф 7\ = {V,E\) максимального реберного веса при условии, что степень вершины v, v V, удовлетворяет ограничению 1 djj(v) 2. Отыскание Ті выполняется с помощью упомянутой выше процедуры из [43]. По лемме 5 этот граф не содержит циклов. Положим Ei = Е\Е\ и определим подграф Gi = (V, i%)- Легко видеть, что степень вершины v графа (?2 удовлетворяет неравенству 1 dc2(v) 2. Число циклов в графе G 2 обозначим через S. Переход на этап 3. Этап 3. Если в графе ( каждый цикл содержит ребро, которое инцидентно концам разных цепей из Т\, то делается переход на этап 4. Если в графе С?2 имеется цикл С, в котором нет двух соседних вершин, являющихся концами разных цепей из 7\ (см. рис. 1.4) , то полученная пара реберно непересекающихся остовных подграфов (TbG2) преобразуется следующим образом. По лемме 6 в цикле С имеются только три вершины, одна из которых (обозначим ее через 1) имеет степень 4 в графе G (и степень 2 в графе Ті), а остальные две вершины V\ и vi являются концами одной цепи Р в графе Ті. Кроме того, согласно лемме 6 вершина v$ не лежит на цепи Р, которая, в свою очередь, состоит из трех вершин v\, Uj и г 2 и двух ребер (см. рис. 1.4). Ребра графа G перераспределим между Ті и ( так, как это показано па рис. 1.4; при этом объединение ребер будет по-прежнему равно Е\ U i?2, число цепей в Gi увеличится на 1, число циклов в ( уменьшится на 1, а число цепей в Ті останется прежним. Заметим, что в каждом цикле преобразованного графа Gi имеется ребро, инцидентное концам разных цепей из Т\. Этап 4. Пара непересекающихся по ребрам остовных подграфов (Ті,С?2) преобразуется в пару (Ті, Gi) следующим образом: из каждого цикла графа G% удаляется по ребру, соединяющему концевые вершины разных цепей в Ті, и эти ребра добавляются в Ті. Заметим, что полученные графы Т\ и ( являются частичными турами. При этом число цепей в (?2 не меньше 5, а число цепей в Ті меньше числа цепей в Ті не больше чем на S. Переход на этап 5. Этап 5. Если 5 3, то полагается Ті = Gi, Ті = Ті, иначе полагается Ті = Ті, Ті = (?2- Переход на этап б. Этап 6. По очереди соединяются цепи тура Ті в гамильтонов цикл #2 и добавляются недостающие ребра в Ті произвольным образом. Если какие-то из этих ребер присутствуют в Ті, то удаляем их из Ті- При этом в Ті не появляются изолированные вершины (лемма 7). Переход на этап 7. Этап 7. По лемме 8 в графе Ті имеется не менее трех цепей. Очевидно, что из любой трех таких цепей можно выбрать такие две цепи, что существует ребро, объединяющее эти две цепи в одну цепь и не входящее в гамильтонов цикл Яг- Последовательно в граф Tj добавляются такие ребра до тех пор, пока полученный граф не будет состоять ровно из трех цепей. Затем осуществляется переход на этап 8. Этап 8. В начале этапа в графе Ті имеются ровно три цепи. Возможные взаимные расположения их концов Vi,... ,VQ на цикле Hi изображены на рис. 1.5. В каждом случае концевые вершины одной цепи обозначены одной геометрической фигурой (треугольником, квадратом или кругом). Если возникла одна из первых четырех конфигураций, то, добавляя в Т\ следующие наборы ребер, не входящие в #2, получаем гамильтонов цикл Н\. А именно: 1) ребра ( 1, 5),( 2,1/4),( 3,) Для конфигурации 1. 2) ребра (i/bi/3),( ,y5),(t/4,t;6) для конфигурации 2. 3) ребра ( 1, ).(. 5),(.) для конфигурации 3. А) ребра (vi, v4), (v2, t/б), (us, 1) для конфигурации 4. В случае, когда п 6 и имеет место конфигурация 5, в гамильтоповом цикле Яг есть хотя бы одна вершина, отличная от концевых вершин цепей Ті. В силу симметричности конфигурации 5 достаточно рассмотреть случай, когда эта вершина лежит на любом из сегментов цикла Яг, например между V\ и г 2- Тогда при добавлении в граф Т\ ребер (14, 2),( 3, 5),( 4,). которые не входят в Яг, получается гамильтонов цикл Н\. В результате работы алгоритм строит непересекающиеся по ребрам гамиль-тоновы циклы Я] и Н% суммарный вес которых не меньше (3/4)W . Описание алгоритма закончено. Предполагается, что для функции W{ и w2 выполняется неравенство треугольника. Обозначим через G\ — [V\,E\) = G — (V,E) граф с весовой функцией u i, а через С?2 = () Е2) = G — (V, Е) граф с весовой функцией w2. Требуется минимизироваь величину И Яі) + И 2(Я2). Описание приближенного алгоритма Алгоритм состоит из двух этапов. Этап 1. С помощью алгоритма КС находятся два гамильтоновых цикла Н\ С G\ и Иг С (. Веса найденных циклов удовлетворяют неравенствам W№) (г/2Щ(Щ) и Ж2(Я2) (3/2)W2(H2 ), где Я[ и Я2 - гамильтоновы циклы минимального веса в соответствующих графах G\ и Gi. Очевидно, что W\(H{) + И (Я) И7 . Если найденные циклы Hi и Я2 не пересекаются по ребрам, то мы получили приближенное решение с оценкой точности 3/2 и алгоритм па этом заканчивает свою работу. В противном случае выполняется этап 2. Этап 2. В качестве первого обхода берется гамильтонов цикл Hi. Целью 2-го этапа является преобразование гамильтонова цикла Я2 в гамильтонов цикл Я2, реберно непересекающийся с первым обходом Я]. Прежде всего перенумеруем вершины графа G согласно порядку обхода в гамильтоновом цикле Я2. Пусть п = 5т + г, где 0 г 5. Очевидно, что т = [п/5]. Пусть Sk - совокупность последовательно расположенных в гамильтоновом цикле Я2 отрезков (цепей) Pi,..., Р . Последние получаются в результате разрезания цикла Я2 нат-г отрезков по 5 сцепленных ребер и оставшиеся г отрезков по 6 сцепленных ребер. Индекс к означает, что первый отрезок Я (в совокупности Sk) начинается с вершины к Є {1,..., К}, где 5, если п кратно 5, п в противном случае . Крайние ребра отрезка Я обозначим через е\к и е -к. Вершины каждой цепи Р Sk обходятся путем Р, удовлетворяющим следующим свойствам: 1. Я выходит из начальной вершины цепи; Т. Я проходит ровно один раз через каждую внутреннюю вершину этой цепи; 3. Р входит в концевую вершину цепи; 4. Р не пересекается с ребрами гамильтонова цикла Hi. {Корректность построения пути Р, состоящим из 5 или из 6 ребер, обосновывается далее в лемме 3), Склеивая все пути, найденные для множества Sk, получаем гамильтонов цикл Нк, реберно непересекающийся с гамильтоновым циклом Ні. В качестве решения принимается гамильтонов цикл Нг наименьшего веса, выбираемый из системы Я1,. -! Нк. Описание алгоритма закончено. Анализ алгоритма Далее для упрощения записи вторую весовую функцию будем записывать без нижнего индекса, то-есть положим W = W2- Лемма 10 Пусть цепь Р Є Ні состоит из 5 или 6 последовательно сцепленных ребер. Тогда за константное число элементарных операций можно построить путь Р, удовлетворяющий свойствам \-4 и имеющий суммарный вес где є1, є" - первое и последнее ребро цепи Р. Доказательство. Для каждого из случаев, когда цепь Р состоит из 5 или б ребер, доказательство проведем отдельно. Случай 5-реберной цепи. Рассмотрим цепь Р = {VI,V2,V3,V4,V5,VQ). Для данной цепи е - (vi,v2), е" = (VS,VQ). Ребро е = (vi,vi+i) Є Р,і Є {1,...,5}, будем называть запрещенным, если є, Є Н\. Доказательство утверждения основано на рассмотрении всевозможных случаев вида цепи Р (см. рис. 1.9). Предполагается, что для функции W{ и w2 выполняется неравенство треугольника. Обозначим через G\ — [V\,E\) = G — (V,E) граф с весовой функцией u i, а через С?2 = () Е2) = G — (V, Е) граф с весовой функцией w2. Требуется минимизироваь величину И Яі) + И 2(Я2). Описание приближенного алгоритма Алгоритм состоит из двух этапов. Этап 1. С помощью алгоритма КС находятся два гамильтоновых цикла Н\ С G\ и Иг С (. Веса найденных циклов удовлетворяют неравенствам W№) (г/2Щ(Щ) и Ж2(Я2) (3/2)W2(H2 ), где Я[ и Я2 - гамильтоновы циклы минимального веса в соответствующих графах G\ и Gi. Очевидно, что W\(H{) + И (Я) И7 . Если найденные циклы Hi и Я2 не пересекаются по ребрам, то мы получили приближенное решение с оценкой точности 3/2 и алгоритм па этом заканчивает свою работу. В противном случае выполняется этап 2. Этап 2. В качестве первого обхода берется гамильтонов цикл Hi. Целью 2-го этапа является преобразование гамильтонова цикла Я2 в гамильтонов цикл Я2, реберно непересекающийся с первым обходом Я]. Прежде всего перенумеруем вершины графа G согласно порядку обхода в гамильтоновом цикле Я2. Пусть п = 5т + г, где 0 г 5. Очевидно, что т = [п/5]. Пусть Sk - совокупность последовательно расположенных в гамильтоновом цикле Я2 отрезков (цепей) Pi,..., Р . Последние получаются в результате разрезания цикла Я2 нат-г отрезков по 5 сцепленных ребер и оставшиеся г отрезков по 6 сцепленных ребер. Индекс к означает, что первый отрезок Я (в совокупности Sk) начинается с вершины к Є {1,..., К}, где 5, если п кратно 5, п в противном случае . Крайние ребра отрезка Я обозначим через е\к и е -к. Вершины каждой цепи Р Sk обходятся путем Р, удовлетворяющим следующим свойствам: 1. Я выходит из начальной вершины цепи; Т. Я проходит ровно один раз через каждую внутреннюю вершину этой цепи; 3. Р входит в концевую вершину цепи; 4. Р не пересекается с ребрами гамильтонова цикла Hi. {Корректность построения пути Р, состоящим из 5 или из 6 ребер, обосновывается далее в лемме 3), Склеивая все пути, найденные для множества Sk, получаем гамильтонов цикл Нк, реберно непересекающийся с гамильтоновым циклом Ні. В качестве решения принимается гамильтонов цикл Нг наименьшего веса, выбираемый из системы Я1,. -! Нк. Описание алгоритма закончено. Анализ алгоритма Далее для упрощения записи вторую весовую функцию будем записывать без нижнего индекса, то-есть положим W = W2- Лемма 10 Пусть цепь Р Є Ні состоит из 5 или 6 последовательно сцепленных ребер. Тогда за константное число элементарных операций можно построить путь Р, удовлетворяющий свойствам \-4 и имеющий суммарный вес W(P) 3 W{P) - 2(w(e ) + w(e")), где є1, є" - первое и последнее ребро цепи Р. Доказательство. Для каждого из случаев, когда цепь Р состоит из 5 или б ребер, доказательство проведем отдельно. Случай 5-реберной цепи. Рассмотрим цепь Р = {VI,V2,V3,V4,V5,VQ). Для данной цепи е - (vi,v2), е" = (VS,VQ). Ребро е = (vi,vi+i) Є Р,і Є {1,...,5}, будем называть запрещенным, если є, Є Н\. Доказательство утверждения основано на рассмотрении всевозможных случаев вида цепи Р (см. рис. 1.9). Рассмотрим класс /Стаж(0,1) матриц расстояний, элементы которых распределены независимо на отрезке [0,1] с функцией распределения F(x) такой, что F(x) х при 0 х 1. Тогда распределение F(x) совпадает с распределением величины /(), где /[0,1], /- монотонно возрастающая функция, при этом ДО) = 0, /(1) = 1, Да) х при 0 х 1. Теорема 8 Алгоритм Areg решения исходной задачи является асимптотически точным па классе Ктах(0,1) при d = о{п). Доказательство. Проводя выкладки для величины 6п(ёп), аналогично схеме доказательства леммы для класса задач fCmax(0,1), получим Здесь фгк — максимум из к независимых случайных величин распределения F(x); г — независимая случайная величина с той же функцией распределения F{x)\ Ck — сумма.? старших порядковых статистик в выборке размера к для распределения F(x). Пусть Ф1, г, Ск — аналогично определенные случайные величины для распределения /[О,1]. Тогда распределения величин фгь г совпадают с распределениями величин /{Ф1), f{C) соответственно, Функция распределения для величины (г-к мажорирует функцию распределения (Тд. ввиду аддитивности конструкции к, ( к и свойств функции /, преобразующей распределение /[0,1] к F(x). Следовательно, Принимая это во внимание, получим, что дальнейшие рассуждения в доказательстве теорем 26 и 7 верны и для класса задач Ктах(0,1). Отсюда следует, что алгоритм Агед на классе fCmax(Qy 1) является асимптотически точным и обладает теми же оценками точности, вероятности несрабатывания и временной сложности. Теорема доказана. Утверждение 5 Если d = о(п), то для произвольных О ап Ьп алгоритм Afeg является асимптотически точным на классе задач Ктах{атЬп) пРи тех же оценках точности, вероятности несрабатывания и временной сложности, что и для класса fCmax(Q, 1). Алгоритм Лтєд легко модифицировать в приближенный алгоритм А для решения задачи па минимум па классе /Cm;n(a„, Ьп). tCmin(a mK) — класс матриц расстояний, элементы которых распределены независимо на отрезке [an,6n] с функцией распределения F(x) такой, что F(x) zSa_ при ап х Ьп. Отличие алгоритма А от алгоритма Агед заключается в том, что па шагах 1 и 2 выбор очередного ребра (элемента матрицы) осуществляется исходя из минимизациоппых соображений. Результатом вероятностного анализа в этом случае является следующее утверждение. Утверждение 6 Если d = о(п), то для произвольных 0 ап Ьп алгоритм А асимптотически точен на классе задач K,min(an,bn) с оценкой относительной погрешности и с теми же оценками вероятности несрабатывания и временной сложности, что и для класса Ктах{ап,Ьп), при дополнительном требовании на разброс элементов матрицы расстояний между вершинами (отношение границ Ьп и ап): Напомним, что предлагаемые алгоритмы асимптотически точны при d = о(п) и имеют временную сложность О {п2 + nd In п). Так что при условии Inn асимптотически точное решение может быть получено за время 0(п2). Рассмотрим следующую задачу разбиения множества векторов. Пусть в векторном пространстве Rk с нормой ]. , которое будем обозначать через (Rk, 11-11 ), задано конечное семейство ненулевых векторов V {vi,V2,--- ,vn}. Определим функцию Sv{x) = Y =ivixi переменной X = (xi,X2,...,xn) {-1,1}". Для заданного семейства входных векторов V требуется найти вектор х Є максимизирующий функцию Sv(#) . Обозначим через {а,Ь) скалярное произведение векторов а и b из R . Рассмотрим выпуклый полиэдр В = {х Rfc (А , я) 1, 1 і т} с т гранями Fi, 1 і m, такими, что F{ С {х Кк \ (Xiyx) = 1}, где А; Є Кк. Полиэдральной нормой вектора х Є Rk называется величина В дальнейшем под полиэдральным пространством размерности к будем понимать пару (R ,c).Задачи поиска двух реберно непересекающихся гамильтоновых циклов экстремального веса
Метрическая задача на минимум с двумя весовыми функциями
Задача поиска регулярного связного подграфа экстремального реберного веса
Случай минорирующей функции распределения элементов матрицы расстояний, заданных независимо
Похожие диссертации на Алгоритмы с оценками для некоторых модификаций задач коммивояжера и разбиения множества
