Алгоритмы с оценками для некоторых модификаций задач коммивояжера и разбиения множества тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Бабурин, Алексей Евгеньевич

• Бабурин, Алексей Евгеньевич
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Бабурин, Алексей Евгеньевич

Введение

Глава 1. Задачи поиска гамильтоновых циклов экстремального реберного веса

1.1. Задачи коммивояжера в евклидовом пространстве

1.1.1. Постановка задачи.

1.1.2. Алгоритм А. И. Сердюкова.

1.1.3. Модифицированный алгоритм А.

1.2. Задачи поиска двух реберно непересекающихся гамильтоновых циклов экстремального веса

1.2.1. Общая постановка задачи.

1.2.2. Задача на максимум с одной весовой функцией

1.2.3. Метрическая задача на минимум с одной весовой функцией

1.2.4. Метрическая задача на минимум с двумя весовыми функциями

Глава 2. Задачи поиска связных подграфов с ограничениями на степени вершин.

2.1. Задача поиска подграфа с заданными степенями вершин максимального реберного веса

2.1.1. Постановка задачи.

2.1.2. Описание приближенного алгоритма

2.1.3. Анализ алгоритма.

2.2. Задача поиска регулярного связного подграфа экстремального реберного веса

2.2.1. Постановка задачи.

2.2.2. NP-трудность

2.2.3. Описание приближенного алгоритма решения задачи

2.2.4. Вероятностный анализ алгоритма.

2.2.5. Случай независимого равномерного распределения элементов матрицы расстояний

2.2.6. Случай мипорирующей функции распределения элементов матрицы расстояний, заданных независимо

2.2.7. Некоторые обобщения.

Глава 3. Задача разбиения множества векторов.

3.1. Постановка задачи.

3.2. Решения задачи в полиэдральном пространстве (Rk, с) с конечной нормой

3.3. Решение задачи в fc-мерном евклидовом пространстве

3.3.1. Области принадлежности решения

3.3.2. Описание алгоритма.

Введение диссертации (часть автореферата) на тему «Алгоритмы с оценками для некоторых модификаций задач коммивояжера и разбиения множества»

Теоретические исследования, связанные с вопросами сложности задач дискретной оптимизации, а также с построением и анализом эффективных приближенных алгоритмов решения этих задач, находятся в русле современных, интенсивно развивающихся областей математики. Терминология, возникающая в ходе этих исследований, широко распространена в современной научной литературе и требует определенного с ней знакомства.

На вопрос, для чего надо иметь представление о сложности решаемых задач, наиболее наглядный ответ дан во введении к книге [11]. В этой книге приводится более 300 задач (из самых разных областей, включая теорию графов и сетей, теорию расписаний, теорию автоматов и языков, оптимизацию программ, базы данных, игры и головоломки и т.п.), для которых в настоящее время нет оснований надеяться на построение эффективных алгоритмов их решения.

В результате бурного развития вычислительной техники появилась возможность решать не отдельную конкретную задачу, а разрабатывать методы и программы, рассчитанные на целый класс задач, получающихся одна из другой заменой ряда исходных данных. Поэтому целесообразно говорить о сложности не для одной индивидуальной задачи /, а для массовой задачи, или проблемы П, соответствующей множеству индивидуальных задач.

Задачи дискретной (комбинаторной) оптимизации образуют важный класс упомянутых массовых задач. Для задачи J] дискретной оптимизации решением каждой индивидуальной задачи I € П является произвольная реализация оптимума Opty[(I) :— тахг€5п(/) z). Здесь »%(/) — область допустимых значений дискретной (целочисленной) переменной z, fy[(I,z) : 5[](/) —> R+ — целевая функция индивидуальной задачи I оптимизации, знак max в постановке задачи может быть заменен на тгп.

Большинство дискретных и комбинаторных задач допускает решение с помощью некоторого процесса перебора вариантов. Вместе с этим число возможных вариантов, а, следовательно, и время решения растет экспоненциально от размеров задачи. Так, например, в задаче коммивояжера число всевозможных маршрутов растет как факториал от "размера" задачи (числа вершин графа). Поэтому переборные алгоритмы решения массовых задач считаются неэффективными. В отличие от них эффективными называются полиномиальные алгоритмы решения массовой задачи, т.е. такие, которые решают произвольную задачу / Е JJ за время, ограниченное полиномом от "размера" входных данных задачи /. Несмотря на определенную условность этого разделения с точки зрения практического счета, объясняется оно прежде всего тем, что центральным для дискретной оптимизации является вопрос, можно ли построить алгоритм решения массовой задачи (т.е. любой индивидуальной), не перебирающий всех или почти всех вариантов ее решения. В этой связи выделяют класс Р задач дискретной оптимизации, разрешимых за полиномиальное время (в зависимости от длины входа), а также класс iVP-трудных задач, для которых построение полиномиальных алгоритмов проблематично (в предположении Р не равно NP) [11]. Одной из фундаментальных проблем современной математики является вопрос: существует ли полиномиальный алгоритм решения ЛгР-трудных задач? Многие исследователи склоняются к отрицательному ответу на данный вопрос.

Алгоритм А называется приближенным алгоритмом решения массовой задачи JI оптимизации, если для произвольного / € f] он находит некоторую точку из допустимой области za{I) £ Sjjil), принимаемую за приближенное решение. Значение /д(/, za{I)) называется приближенным значением оптимума и обозначается через А{1).

Говорить об абсолютной погрешности приближенного алгоритма решения массовой задачи оптимизации (на классе всевозможных индивидуальных задач) обычно не имеет большого смысла, так как для разных индивидуальных задач величина оптимума может быть как сколь угодно большой, так и малой. Поэтому целесообразно анализировать относительную точность приближенных алгоритмов.

Иногда при анализе приближенного алгоритма удается показать определенные гарантированные оценки качества решения, получаемого в ходе его работы для произвольной индивидуальной задачи.

Зачастую при наложении определенных условий на входные данные для задачи удается построить s-приближенный алгоритм.

Приближенный алгоритм А решения массовой задачи J] оптимизации называется ^-приближенным алгоритмом решения f] для некоторого е > 0, если для произвольной I € Р

Optn(I)-A(I)

Optn(I) е, т.е. его относительная погрешность не превосходит е. Величину

• А(1) гшп ieП Optu{I) если она существует) называют оценкой точности алгоритма А для задач максимизации. Аналогично определяется оценка точности алгоритма для задач минимизации.

Зачастую целевая функция принимает только целочисленные значения. Если для какого-то подкласса задач удается показать, что произведение относительной погрешности алгоритма на верхнюю оценку целевой функции меньше 1, то такой алгоритм на этом подклассе задач находит точное решение.

Одной из самых широко известных и исследованных задач комбинаторной оптимизации является задача коммивояжера (далее ЗК). ЗК заключается в отыскании экстремального по длине гамильтонова цикла в заданном графе. ЗК известна среди математиков и статистиков под разными названиями. В [28]

ЗК связывается со знакомой статистикам задачей средних минимальных расстояний.

Стоит отметить, что систематическое исследование ЗК как задачи комбинаторной оптимизации началось с работы [30]. Обзоры [50, 55, 60, 62] и книги [54, 59] содержат описание основных достижений в исследованиях данной задачи.

Кратко представим постановку ЗК:

Задано множество С, состоящее из п городов и матрица d(ci, Cj) € N расстояний между ними. Допустимым решением является простой обход множества С, т.е. одпоцикличиая перестановка городов. Требуется найти допустимое решение, обладающее максимальной длиной соответствующего обхода.

В целом ряде работ ЗК рассматривалась с точки зрения выявления полиномиально разрешимых подклассов. Первый нетривиальный полиномиально разрешимый случай этой задачи был описан в [41]. В упомянутой работе исследовались случаи, когда оптимальное решение определялось простым многоугол-ником на плоскости. Один из наиболее известных полиномиально разрешимых случаев, имеющих большое практическое применение, представлен в [25, 44].

Ввиду богатой истории исследования ЗК, широкое распространение и известность получили также различные ее модификации и обобщения.

Например, ранее интенсивно исследовалась только ЗК на минимум. Однако в последние десятилетия все больший интерес уделяется ЗК на максимум. Как известно, для этой задачи в общем виде существует порог неприближаемости в классе полиномиальных алгоритмов (в предположении Р ф NP) [38, 57]. В работах [10, 13, 21, 23, 24, 26, 40, 48, 52] были предложены полиномиальные алгоритмы с гарантированными оценками для решения ЗК на максимум.

Так для метрической ЗК на минимум (вышеупомянутая задача с условием выполнение неравенства треугольника для матрицы d(c2,cj) расстояний) известен полиномиальный ^-приближенный алгоритм Кристофидеса-Сердюкова

27], [18].

Одним из основных исследуемых подклассов ЗК па максимум является евклидова задача. ЗК на максимум называется евклидовой, если вершинам заданного графа сопоставлены точки в евклидовом пространстве Rk , а длины дуг между вершинами определяются как расстояния между точками, соответствующими этим вершинам. В [56] показано, что евклидова задача коммивояжера на минимум является NP-трудной в случае, если размерность пространства превышает 2. Этот же сложностной статус имеет евклидова ЗК на максимум [39].

В работе [20] был представлен асимптотически точный алгоритм А решения ЗК на максимум в ^-мерном евклидовом пространстве Rk . Трудоемкость алгоритма, определялась трудоемкостью отыскания максимального паросочетания в заданном графе. Получаемый гамильтонов цикл содержал все ребра данного паросочетания.

В работе [4] была представлена модификация этого алгоритма, имеющая такие же оценки точности, но более простая в изложении. Несмотря на сходство подходов, гамильтонов цикл, получаемый этим алгоритмом, строился проще и не содержал ребер максимального паросочетания, за исключением, быть может, двух.

Изучение этих алгоритмов показало, что возможно пересмотреть некоторые их шаги с тем, чтобы на более узком классе задач улучшить получаемые оценки точности. Основной результат первой части главы 1 данной диссертации -построение и анализ такой модификации.

Так как относительная точность алгоритма является величиной безразмерной, то масштабирование графа (растяжение соответствующего пространства Rk на неотрицательную величину) не изменяет оценки точности алгоритмов. Будем полагать, что длина минимального ребра графа равна 1. В этом случае отношение максимальной длины ребра графа к минимальной является диаметром множества его вершин (в дальнейшем просто диаметром).

Оказывается, что при наложении достаточно слабых ограничений па диаметр множества вершин исходного графа, алгоритмы из [20] и [4] допускают хорошую, с точки зрения улучшения оценок точности, модификацию.

Вполне естественно, что специфика задачи, определяемая дополнительными ограничениями, может быть использована в ходе работы алгоритма. Однако эти же ограничения создают дополнительные трудности при обосновании полиномиальной сводимости одних задач к другим, тем самым, оставляя открытым вопрос о сложностном статусе исходных. Так, например, общая задача коммивояжера на максимум является iVP-трудпой, однако вопрос об ^VP-трудности этой задачи для иланарных графов или точек в евклидовой плоскости остается на текущий момент открытым.

В численных экспериментах данные представляются числами с фиксированным количеством разрядов. Исходя из соображений масштабируемости задачи, предположим, что задаваемые таким образом точки лежат в вершинах целочисленной решетки Ък.

Обозначим за 5ь(Х) диаметр множества вершин исходного графа G, построенного на множестве точек X и имеющего п вершин. При этом все вершины графа лежат в шаре с радиусом, равным 6k(X), но находятся на расстоянии не меньшем 1 друг от друга. Тогда верно следующее неравенство:

5к{Х)>скпК (1) где q. — константа, зависящая только от размерности пространства Rk .

Предлагаемая в главе 1 модификация алгоритма А. И. Сердюкова является асимптотически точной при выполнении следующих условий: з о(пг), если к = 2;

Модификация обладает лучшими оценками точности по сравнению с алгоритмами [4, 20] при:

Сравнивая накладываемые ограничения 3 и естественное неравенство 1, видим, что описанная область входных данных достаточно велика, особенно при

Приведенные соображения показывают важность данного подкласса евклидовой задачи коммивояжера на максимум.

Во многих задачах оптимизации в заданном взвешенном графе требуется отыскать подграф (клику, доминирующее множество, остовное дерево, гамильтонов цикл, вершинное покрытие и т. п.) минимального или максимального веса. Естественными модификациями подобных задач являются задачи, в которых требуется найти несколько (вершинно или реберно) непересекающихся подграфов определенного типа минимального или максимального суммарного веса. Одной из первых задач этого типа, привлекших внимание исследователей, является задача о т бродячих торговцах (m-peripatetic salesman problem [53], далее m-PSP). В задаче m-PSP задан полный n-вершинный неориентированный граф G = (V, Е) с неотрицательной весовой функцией ребер w : Е —> R+. Требуется найти т таких непересекающихся по ребрам гамильтоновых циклов

Сгпе, если к = 2;

3)

Н\,., нп С Е, 10 что величина (суммарный вес ребер найденных циклов) т

Е Е«»(«) к=1 ееНк минимальна (или максимальна).

В [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(п3). Показано, что гарантированные оценки точности асимптотически (с ростом п) равны 9/4 (в случае одной весовой функции) и 12/5 (в случае двух весовых функций). Получение оценок существенно опирается на классический результат Кристофидеса (см., например, в [15]) и Сердюкова [18], предложивших (независимо друг от друга) приближенный алгоритм построения гамильтопова цикла в полном графе с расстояниями, удовлетворяющими неравенству треугольника. Этот алгоритм, называемый далее алгоритмом КС, находит решение с гарантированной оценкой точности 3/2 за время 0(п3), определяемое сложностью отыскания совершенного паросочетания минимального веса (см., например, [43]). При построении первого алгоритма (в случае одной весовой функции) была использована техника склеивания циклов 2-фа,ктора в гамильтонов цикл, примененную Сердюковым и Косточкой [14].

В главе 2 диссертации исследуется такое естественное обобщение ЗК, когда в полном взвешенном графе выбирается остовный связный подграф со степенями вершин, отличными от 2.

В [47] сформулирована задача отыскания графического представления заданного набора натуральных чисел di (i = l,.,n),l < dj < п. Задача заключалась в построении простого неориентированного графа G без петель с п вершинами, степени которых совпадали бы с числами di. Набор чисел d\,., dn, для которых существует соответствующее графическое представление, называется графическим разбиением числа т = ]СГ=1 Очевидно, что любое такое т четно и di < п — 1 для каждого г = 1,. ,п. Однако, эти условия не являются достаточными для существования указанного представления. Например, набор D = (3,3,3,1) не является графическим разбиением. Конструктивный критерий существования графического разбиения для набора натуральных чисел может быть получен из следующего утверждения, доказанного в [49]:

Разбиение D = (di,.,dp) четного числа на р частей, р > d\ > d2 > . > dp, является графическим тогда и только тогда, когда графическим является модифицированное разбиение D' = (d? - 1,с?з — 1,.,d^+i — 1,2,. ,dp).

Это утверждение дает нам полиномиальный алгоритм проверки представимости графического разбиения.

Оптимизационный вариант задачи поиска представления набора натуральных чисел впервые был упомянут в [37].

В [42] для задачи поиска к-связного подграфа минимального реберного веса с заданными степенями вершин в графе, веса ребер которого удовлетворяют неравенству треугольника, был предложен полиномиальный алгоритм с гарантированными оценками точности.

В диссертации рассматривается задача, представленная в [46], где она обозначалась как CSDP (Connected subgraph with given vertex degrees). Задача состоит в отыскании связного подграфа G исходного графа G, обладающего максимальным весом ребер и имеющего заданные степени вершин.

Заметим, что задача коммивояжера совпадает с CSDP, если степени всех вершин искомого подграфа G равны 2.

Задача CSDP называется метрической, если веса ребер исходного графа G удовлетворяют неравенству треугольника.

Задача CSDP называется евклидовой, если вершинам исходного графа G задачи сопоставлены точки в евклидовом пространстве Rk, и вес любого ребра равен расстоянию между точками, соответствующими концам этого ребра.

Приближенный алгоритм решения метрической задачи CSDP был предложен в [46]. Этот алгоритм применим только для случая четных значений Оценка точности алгоритма была не меньше величины (1 — щ^ц), где d — минимальное значение заданных степеней вершин искомого подграфа.

В данной работе представляется новый приближенный алгоритм решения CSDP, работающий независимо от четности чисел d(. Проводится его анализ для разных классов исходной задачи с детерминированными входами и обосновываются гарантированные оценки точности получаемых решений в общем случае, а также в частных случаях метрической и евклидовой задач. Алгоритм имеет временную сложность 0(Мп2), где М - число ребер в искомом подграфе.

Для алгоритма решения задачи CSDP получены следующие оценки точности:

1 ~ Щй) ы °бЩем «^учае, Дл > < 1 - j^fjj в случае метрической задачи 1 - I'.'f'I в случае евклидовой задачи.

Здесь d = min{di\i = 1,., п].

Кроме того, алгоритм, предложенный на случай произвольных степеней вершин выбираемого подграфа G, является приближенным алгоритмом решения задачи коммивояжера на максимум с гарантированной оценкой точности 2/3. При решении этой задачи его временная сложность равна 0(п3). При этом для метрической задачи коммивояжера на максимум алгоритм дает приближенное решение с гарантированной оценкой точности 5/6. Такой же гарантированной оценкой точности для метрической задачи коммивояжера на максимум обладает алгоритм Косточки и Сердюкова из [14]. Понятно, что для непосредственно задачи коммивояжера с учетом се специфики удается получить лучшие оценки точности (см., например, [59], глава И) по сравнению с более общей задачей — задачей CSDP.

При вероятностном анализе алгоритмов часто используются обозначения и определения, представленные в [5].

Рассмотрим алгоритм А решения оптимизационной задачи на максимум. Алгоритм А имеет оценки (еш 5п) в классе Рп задач максимизации размерности п, если для каждого п выполнены следующие неравенства: где Pr{J} — вероятность соответствующего события J. Величина еп называется относительной погрешностью, 5п — вероятностью несрабатывания алгоритма А.

Приближенный алгоритм называется асимптотически точным в классе задач J] = U{Pn\n =1,2,.}, если для него существуют такие оценки (еп, 6п), что еп —> 0, 5п —» 0 при п —> 00.

Впервые вероятностный анализ был продемонстрирован А. А. Боровковым в [2] применительно к задачам дискретной оптимизации — ЗК и задаче о назначениях на случайных входных данных. Им был предложен полиномиальный алгоритм, который почти всегда дает решение ЗК на минимум с константной относительной погрешностью. Позже для ЗК на случайных входных данных был реализован асимптотически точный подход, основанный на использовании неравенства Чебышева ([6-8] для задачи на минимум, [3, 63] - для задачи на максимум). В работах [9, 45, 46] для обоснования условий асимптотической точности полиномиальных алгоритмов решения ЗК на случайных входах была использована теорема Петрова [16], позволившая получать лучшие оценки для вероятности несрабатывания алгоритма.

Ряд результатов вероятностного анализа алгоритмов решения различных задач комбинаторной оптимизации может быть найден в [22, 51, 58].

Для решения задачи отыскания d-однородного остовного связного подграфа максимального суммарного веса в [46] был предложен приближенный алгоритм в предположении, что число вершин п графа G кратно величине d— 1. Времен- • пая сложность алгоритма 0(п2). В работе [46] были представлены результаты вероятностного анализа этого алгоритма в случае, когда входные данные (веса ребер графа G)—случайные независимые переменные с одинаковой функцией равномерного распределения.

В диссертации доказывается NP-трудность задачи и описывается новый приближенный алгоритм, дающий улучшенные оценки качества его работы по сравнению с теми, что были получены в работе [46]. При этом удалось снять ограничение на кратность числа вершин графа G. Проведен вероятностный анализ алгоритма на случайных исходных данных и получены условия асимптотической точности предложенного алгоритма как в случае равномерного распределения весов ребер, так и в случае распределений минорирующего типа. Алгоритм, имея временную сложность 0(п2 + пбПпп), отыскивает асимптотически точное решение при d = о(п). Таким образом, при d < асимптотически точное решение может быть получено за время 0(п2).

В заключение главы 2 алгоритм модифицируется на случай минимизацион-ной версии задачи. К условию асимптотической точности модифицированного алгоритма добавляется дополнительное ограничение па разброс весов ребер графа.

В главе 3 исследуются задачи выбора подмножества векторов, отвечающего тем или иным критериям оптимальности. Пусть в векторном пространстве Rk с нормой ||.||*, которое будем обозначать через (Rk, ||.||*), задано конечное семейство ненулевых векторов V = {vi,v2,. ,vn}. Определим функцию Sv(x) — YA=ivixi переменной х = (х\, ., xn) G Rn. Рассматриваются две задачи:

Для заданного семейства входных векторов V требуется найти вектор х € {0,1}", максимизирующий функцию ||SV(:e)||*.

Для заданного семейства входных векторов V требуется найти вектор х € {-1,1}п, максимизирующий функцию ||5у(а;)||#.

Данная модель может быть применена к решению задач выбора оптимального (максимизирующего прибыль) производства на предприятии, когда некоторые характеристики выбираемых компонент могут иметь отрицательный знак (затраты на ресурсы). Тогда каждая компонента может быть представлена вектором, координаты которого - ее характеристики. При суммировании векторов (одновременном выборе ряда компонент производства) соответствующие координаты складываются (как и соответствующие им характеристики компонент). Роль целевой функции играет оценка эффективности производства.

В формальной постановке первой задачи значение переменной Х{ отвечает за выбор или невыбор вектора V{. Например, если £ = (1,1,., 1), то все векторы будут выбраны, а если х — (О, О,., 0), то все векторы будут не выбраны. Тем самым, первая задача является задачей выбора подмножества векторов с целью максимизации нормы суммы элементов выбранного подмножества.

Нетрудно заметить, что первая задача полиномиально сводится ко второй задаче: ее решение легко строится из решения второй задачи с набором векторов

В то же время имеет место и обратная сводимость. Тем самым, упомянутые две задачи полиномиально эквивалентны.

Данные задачи упоминаются в статье [12], в которой исследуется условная сходимость векторных рядов в конечномерном евклидовом пространстве. Однако вопрос об отыскании эффективной процедуры решения задачи в работе не рассматривается. Вопрос об эффективности такого алгоритма рассмотрен позже в статье [1]. В ней предполагается возможность достижения временной сложности процедуры 0(nfc1), хотя сам алгоритм не приводится.

Отметим, что минимизационный вариант задачи исследовался Дворецким в [36], который в 1963 г. сформулировал проблему нахождения функции f(k) = sup{ min \\Sv{x)\\2\V eRk,msLx\\v\\2<l}. ze{-l,i}n veV

Эта проблема до сих пор открыта.

С подходами к приближенному решению аналогов предложенных задач на минимум можно ознакомиться в работе [17].

Учитывая эквивалентность задач, в дальнейшем мы ограничимся рассмотрением только второй задачи (когда координаты векторы х принимают значения 1 и —1), которую будем называть задачей разбиения множества векторов.

Обозначим через (а,Ь) скалярное произведение векторов а и Ь из Rfc. Рассмотрим выпуклый полиэдр В = {х G | (\{,х) <1, 1 < i < т} с т гранями Fi, 1 < г < т, такими, что F{ С {ж е | (\i,x) = 1}, где Aj €

Полиэдральной нормой вектора х G Rk называется величина с{х) = maxjO, (Льж),., (Лт,ж) j.

Заметим, что если полиэдр В несимметричен, то полиэдральная норма не является нормой в классическом понимании, так как аксиома \\ах\\ = НЦ^Ц может нарушаться для отрицательных значений а. Такие нормы иногда называют несимметричными нормами. Более подробную информацию о них можно найти в [61]. Если же полиэдр В симметричен, то полиэдральная норма удовлетворяет всем аксиомам нормы. Примерами полиэдральных норм являются нормы 1\ и loo

В дальнейшем под полиэдральным пространством размерности к будем понимать пару с). Полиэдр В в норме с является единичным шаром. Если В — ограниченное множество, то полиэдральную норму с будем называть конечной.

Также исследуется поставленная задача в ^-мерном евклидовом пространстве (R\l2).

Напомним, что для и 6 Rk эта норма определяются следующим образом:

1Mb = у/(щи).

Основным результатом главы являются следующие утверждения:

Рассмотренная задача разбиения множества векторов является полиномиально разрешимой в ^-мерном полиэдральном пространстве (Rk, с) с конечной нормой с, а также в пространстве (Rk,l2)

Основные результаты диссертации докладывались на Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004), на Международной научной студенческой конференции (Новосибирск, 2000), на Международных конференциях по исследованию операций OR2002 (Клаген-фурт, 2002), OR2003 (Гейдельберг, 2003), OR2004 (Тилбург, 2004), на Всероссийской конференции "Методы оптимизации и экономические приложения" (Омск,

2003, 2006), на семинаре проф. Брукера университета г. Оснабрюк (Оснабрюк, 2004), па семинаре по дискретной математике Санкт-Петербургского отделения Института математики им. Стеклова (Санкт-Петербург, 2005), на семинаре Объединенного Института Проблем Информатики (Минск, 2007), на научных семинарах Института математики им. Соболева СО РАН.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Бабурин, Алексей Евгеньевич

Заключение

Проведено исследование возможности модификации алгоритма А. И. Сердю-кова решения евклидовой задачи коммивояжера на максимум с целью улучшения точности алгоритма на подклассах задачи. Результатом явилось построение нового алгоритма, улучшающего оценки точности алгоритма А. И. Сердюкова на достаточно широком классе исходных данных.

Рассмотрена задача отыскания в полном неориентированном взвешенном графе двух (реберно) непересекающихся гамильтоновых циклов максимального суммарного веса. Известно, что данная задача NP-трудна в сильном смысле. Построен алгоритм решения задачи с временной сложностью 0(п3) и гарантированной оценкой точности 3/4.

Проведено исследование метрической задачи отыскания двух реберно непересекающихся гамильтоновых циклов минимального суммарного веса в полном неориентированном взвешенном графе, в котором выполняется неравенство треугольника. Для случаев, когда на ребрах графа задана одна весовая функция и когда весовых функций две, предложены два приближенных алгоритма с временной сложностью 0(п3). Показано, что соответствующие оценки точности асимптотически (с ростом п) равны 9/4 и 12/5.

Представляется интересным продолжение исследований на случай большего (чем два) реберно непересекающихся гамильтоновых циклов. На взгляд автора, увеличение числа несмежных гамильтоновых циклов существенно затруднит разрешение вопросов, связанных с определением сложностного статуса задачи и построение приближенных алгоритмов с хорошими оценками точности, если оставаться только в рамках техники, использованной в данной диссертации.

Рассмотрена задача поиска связного остовного подграфа с заданными степенями вершин максимального суммарного реберного веса в полном взвешенном неориентированном графе. Для решения задачи представлен полиномиальный приближенный алгоритм. Проведен его анализ и обоснованы гарантированные оценки точности получаемых решений задачи в общем случае, а также в частных случаях метрической и евклидовой задач.

Доказана ЛГР-трудность задачи отыскания d-однородного связного остовно-го подграфа максимального веса в полном неориентированном п—вершинном графе. Представлен приближенный полиномиальный алгоритм для ее решения. Проведен вероятностный анализ алгоритма для решения задачи со случайными входными данными (весами ребер) как в случае равномерного распределения весов ребер, так и в случае распределений минорирующего типа. Показано, что алгоритм имеет временную сложность 0(п2 + nd\nnj и отыскивает асимптотически точное решение задачи при d = о(п). В случае d < ^ асимптотически точное решение может быть получено за время 0(п2). Для минимизационной версии задачи к условию асимптотической точности модифицированного алгоритма добавляется дополнительное ограничение на величину разброса значений весов ребер графа.

Исследовалась задача максимизации взвешенной суммы заданного конечного множества векторов из конечномерного нормированного пространства Rk. Приведены и проанализированы точные полиномиальные алгоритмы ее решения в случае, когда в пространстве Rk задана конечная полиэдральная норма, а также норма

Список публикаций автора по теме диссертации

1. Агеев А. А., Бабурин А. Е., Гимади Э. X. Полиномиальный алгоритм с оценкой точности 3/4 для отыскания двух непересекающихся гамильтоновых циклов максимального веса // Дискретный анализ и исследование операций. Серия 1. 2006. Т. 13, № 2. С. 11-20.

2. Агеев А. А., Бабурин А. Е., Гимади Э. X., Коркишко Н. М.

Алгоритмы с константными оценками точности для отыскания двух реберно непересекающихся гамильтоновых циклов экстремального веса // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск. 2003. С. 9-12.

3. Бабурин А. Е., Гимади Э. X. Об асимптотической точности одного алгоритма решения задачи коммивояжера на максимум в евклидовом пространстве // Дискретный анализ и исследование операций. Серия 1. 2002. Т. 9, № 4. С. 23-32.

4. Бабурин А. Е., Гимади Э. X. Алгоритмы с оценками для некоторых обобщений задачи коммивояжера // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения". Т. 1. Математическое программирование. Иркутск: Изд-во ИСЭ СО РАН. 2005. С. 421-428.

5. Бабурин А. Е., Гимади Э. X. Об одном обобщении задачи коммивояжера на максимум // Дискретный анализ и исследование операций. Серия 2. 2006. Т. 13, № 3. С. 3-12.

6. Бабурин А. Е., Гимади Э. X., Коркишко Н. М. Приближенные алгоритмы для отыскания двух реберно непересекающихся гамильтоновых циклов максимального веса // Дискретный анализ и исследование операций. Серия 2. 2004. Т. 12, № 1. С. 11-25.

7. Бабурин А. Е., Пяткин А. В. О полиномиальных алгоритмах решения одной задачи суммирования векторов // Дискретный анализ и исследование операций. Серия 1. 2006. Т. 13, № 2. С. 3-10.

8. Baburin А. Е. On one polynomially solvable problem of vector summation // Proceedings of the 2-nd International Workshop "Discrete Optimization Methods in Production and Logistics" DOM'2004, Omsk. 2004. P. 145-148.

9. Baburin A. E., Gimadi E. Kh. A problem of finding a spanning connected subgraph of maximum weight // Proceedings of the 2-nd International Workshop "Discrete Optimization Methods in Production and Logistics", Omsk. 2004. P. 149 154.

10. Baburin A. E., Gimadi E. Kh. Approximation algorithms for finding a maximum-weight spanning connected subgraph with given vertex degrees //' Operations Research Proceedings 2004, Selected Papers. International Conference OR 2004, Tilburg. Berlin: Springer-Verlag. 2005. P. 343-351.

11. Baburin A. E., Gimadi E. Kh., Korkishko N. M. Algorithms with Performance Guarantees for a Metric Problem of Finding Two Edge-Disjoint Hamiltonian Circuits of Minimum Total Weight // Operations Research Proceedings. Berlin; Heidelberg; New York: Springer-Verlag. 2004. P. 316-323.

Благодарности

В заключение я хочу выразить искреннюю благодарность моему научному руководителю Э. X. Гимади за предложенную тему исследований и поддержку па протяжении всего времени работы над диссертацией. Также я благодарен сотрудникам отдела теоретической кибернетики Института математики СО РАН им. С. Л. Соболева, чьи критические замечания и советы помогли мне получить эти результаты: А. А. Агееву, Н. И. Глебову, М. Г. Пащенко, А. В. Пяткину, а. также С. В. Севастьянову.

Список литературы диссертационного исследования кандидат физико-математических наук Бабурин, Алексей Евгеньевич, 2007 год

1. Белов И. С., Столин Я. Н. Алгоритм в одномашинной задаче календарного планирования // Математическая экономика и функциональный анализ. - М.: Наука, 1974,- С. 248-259.

2. Боровков А. А. К вероятностной постановке двух экономических задач // Докл. АН СССР. 1962. - Т. 146. - С. 983-986.

3. Гимади Э. X. Задача коммивояжера на максимум: условие асимптотической точности алгоритма "иди в самый удаленный город" // Управляемые системы. Сб. науч. тр. — 1989.— С. 11-15.

4. Гимади Э. X. Новая версия асимптотически точного алгоритма решения евклидовой задачи коммивояжера на максимум // Труды XII Байкальской международной конференции. Методы оптимизации и их приложения. — Т. 1.- 2001.-С. 117-124.

5. Гимади Э. X., Перепелица В. А. Асимптотически точный подход к решению задачи коммивояжера // Управляемые системы. Сб. науч. тр. -1974. С. 35-45.

6. Гимади Э. X., Сердюков А. И. Аксиальные задачи о назначении и коммивояжера: быстрые приближенные алгоритмы и их вероятностный анализ // Известия Вузов. Математика. — 1999. — № 12. — С. 19-25.

7. Гимади Э. X., Сердюков А. И. О некоторых результатах для задачи коммивояжера на максимум // Дискрет, анализ и исслед. операций. — 2001.-Т. 8, № 1.-С. 22-39.

8. И. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

9. Кадец М. И. Об одном свойстве векторных ломаных в п—мерном иро-страптсве // Успехи матем. наук. — 1953. — Т. 8, № 1. — С. 139-143.

10. Ковалев М. М., Котов В. М. Субоптимальные алгоритмы для решения задачи коммивояжера // Вестник Белорусского университета, — 1982.— № 1. С. 1-31.

11. Косточка А. В., Сердюков А. И. Полиномиальные алгоритмы с оценками 3/4 и 5/6 для задачи коммивояжера на максимум // Управляемые системы: Сб. науч. тр. — 1985. — № 26. — С. 55-59.

12. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. — М.: Мир, 1982.

13. Петров В. В. Предельные теоремы для сумм независимых случайных величии. — М.: Наука, 1987.

14. Севастьянов С. В. Геометрия в теории расписаний // Модели и методы оптимизации. Тр. АН СССР. Сиб. отд-ние. Институт математики. — 1988.-Т. 10,- С. 226-261.

15. Сердюков А. И. О некоторых экстремальных обходах в графах // Управляемые системы: Сб. науч. тр. — 1984. — № 17. — С. 76-79.

16. Сердюков А. И. Алгоритм с оценкой для задачи коммивояжера на максимум // Управляемые системы: Сб. науч. тр. — 1984. — 25. — С. 80-86.

17. Сердюков А. И. Асимптотически точный алгоритм для задачи коммивояжера на максимум в евклидовом пространстве // Методы целочисленной оптимизации (Управляемые системы). — 1987. — № 27. — С. 79-87.

18. Сердюков А. И. Задача коммивояжера на максимум в конечно-мерных вещественных пространствах // Дискрет, анализ и исслед. операций. 1995.-Т. 2, № 1.-С. 50-56.

19. Angluin D., Valiant L. G. Fast probabilistic algorithms for hamiltonian circuits and matchings //J. Comput. System Sci. — 1979. — Vol. 18. — P. 155-193.

20. Armen C., Stein С. A 2.66.-approximation algorithm for the shortest su-perstring problem. — Manuscript, 1994.

21. Barvinok A. I. Two algorithmic results for the traveling salesman problem // Math. Oper. Res. 1996. - Vol. 21, no. 1.— P. 65-84.

22. Burdyuk V. Y., Trofimov V. N. Generalization of the results of Gilmore and Gomory on the solution of the traveling salesman problem // Eng. Cybernetics. 1976. - no. 11. - P. 12-18.

23. Burkard R. E., Deineko V. G.> van Dal R. et al Well-solvable special cases of the traveling salesman problem: A survey // SIAM Review. — 1998. — Vol. 40, no. 3. P. 496-546.

24. Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem: Tech. Rep. CS-93-13: Carnegie Mellon University, 1976.

25. Cook W. J., Cunninghan W. H., Pulleyblank W. R., Schrijver A.

26. Combinatorial Optimization. — New York: John Wiley Sons, 1998.

27. Croce F. D., Pashos V. Т., Calvo R. W. Approximating the 2-peripatetic salesman problem // 7th Workshop on Modelling and Algorithms for Planning and Scheduling Problems MAPS 2005. (Siena, Italy, June 6-10).- 2005. — P. 114-116.

28. Dantzig G. В., Fulkerson D. R., Johnson S. M. Solution of a large scale salesman traveling problem // Oper. Res. — 1954. — Vol. 2. — P. 393-410.

29. De Brey M. J. D., Volgenant A. Well-solved cases of the 2-peripatetic salesman problem // Optimization. — 1997. — Vol. 39, no. 3. — P. 275-293.

30. De Kort J. B. J. M. Lower bounds for symmetric fc-peripatetic salesman problems // Optimization. 1991. - Vol. 22, no. l.-P. 113-122.

31. De Kort J. B. J. M. Upper bounds for the symmetric 2-peripatetic salesman problem // Optimization. 1992. - Vol. 23, no. 4,- P. 357-367.

32. De Kort J. B. J. M. A branch and bound algorithm for symmetric 2-pcripatetic salesman problems // European J. of Oper. Res.— 1993. — Vol. 10, no. 2.- P. 229-243.

33. Duchenne E., Laporte G., Semet F. Branch-and-cut algorithms for theundirected m-peripatetic salesman problem // European J. of Oper. Res.2005. Vol. 162, no. 3. - P. 700-712.

34. Dvoretzky A. Problem // Proceedings of Symposia in Pure Mathematics, Providence: RL — Vol. 7, Convexity. — Amer. Math. Soc., 1963.

35. Edmonds J., Johnson E. L. Matchings: a well solvable class of integer linear programs // Combinatorial structures and their applications. — New York: Gordon and Breach, 1970. P. 89-92.

36. Engebretsen L. An explicit lower bound for tsp with distances one and two: Tech. Rep. 46: Electronic Colloquium on Computational Complexity, 1999.

37. Fekete S. P. Simplicity and hardness of the maximum traveling salesman problem under geometric distances: Tech. Rep. 98.329: Center for Applied Computer Science, Universitat zu Koln, 2006.

38. Fisher M. L., Nemhauser G. L., Wolsey L. A. An analysis of approximations for finding a maximum weight Hamiltonian circuit // Oper. Res. — 1979. Vol. 27, no. 6,- P. 799-809.

39. Flood M. M. The traveling-salesman problem // Oper. Res. — 1956. — no. 4,- P. 61-75.

40. Fukunaga Т., Nagamochi H. Network design with edge-connectivity and degree constraints: Tech. Rep. 012: Department of Applied Mathematics and Physics, Graduate school of Informatics, Kyoto University, 2006.

41. Gabow H. N. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems // Proc. 15th annual ACM symposium on theory of computing (Boston, April 25-27, 1983).— New York: ACM, 1983. P. 448-456.

42. Gilmori P. С., Gomory R. E. Sequencing a one state-variable machine: A solvable case of the traveling-salesman problem // Oper. Res. — 1964. — no. 12.-P. 665-679.

43. Gimadi E. Kh. On some probability inequalities for some discrete optimization problems // Operations Research Proceedings 2005, Selected Papers. International Conference OR 2005, Tilburg. Springer, Berlin, 2006. - P. 283-289.

44. Harary F. Graph theory — Reading, Massachusetts: Addison-Wesley, 1969.

45. Hassin R., Rubinstein S. Better approximations for max tsp // Inform. Process. Lett. 2000. - Vol. 75. - P. 181-186.

46. Havel V. A note to question of existance of finite graphs: Tech. rep.: Casopis Pest Mat, 1955.

47. Karp R. The probabilistic analysis of some combinatorial search algorithms // Algorithms and complexity. Recent results and new directions. — 1976.1. P. 1-19.

48. Kosaraju S. R., Park J. K., Stein C. Long tours and short superstrings // 35st IEEE symp. on Foundations of Computer Science. — 1994,— P. 166-177.

49. Krarup J. The peripatetic salesman and some related unsolved problems // Combinatorial programming: methods and applications (Proc. NATO Advanced Study Inst., Versailles, 1974). 1975. - P. 173-178.

50. Lawler E. L., Lenstra J. K., Rinnoy Kan A. H., Shmoys D. B. The

51. Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. — Wiley, Chichester, 1985.

52. Melamed 1.1., Sergeev S. I., Sigal I. K. The traveling salsman problem. Approximation algorithms // Automat. Remote Control. — 1990. — P. 1459-1479.

53. Papadimitriou С. H. The euclidean traveling salesman problem is NP-com-plete // Theoret. Comput. Sci 1977. - no. 4,- P. 237-244.

54. Papadimitriou С. H., Yannakakis M. The traveling salesman problem with distances one and two // Math. Oper. Res. — 1993. — no. 18. — P. 1-11.

55. Piersma N. A probabilistic analysis of the capacitated facility location problem // J. Comb. Optim. 1999. Vol. 3, no. 1. P. 31 50.

56. Punnen A., Gutin G. The Traveling Salesman Problem and its variations. — Dortrecht/Boston/London, 2003.

57. Reinelt G. The Traveling Salesman: Computational Solutions for TSP Applications. — Berlin: Springer-Verlag, 1994.

58. Schryver A. Combinatorial Optimization: polyhedra and efficiency. — Berlin: Springer, 2003.

59. Slominski L. Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations // Computing. — 1982. — no. 28. — P. 257-267.

60. Vohra R. V. Probabilistic analysis of the longest hamiltonian tour problem // Networks. — 1988. — Vol. 18, no. 1,- P. 13-18.