Алгоритмы с оценками для некоторых модификаций задач коммивояжера и разбиения множества

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

На вопрос, для чего надо иметь представление о сложности решаемых задач, наиболее наглядный ответ дан во введении к книге [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) и гарантированной оценкой точности ¾.

В следующем разделе диссертации рассматривается задача 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{dii = 1,., п].

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

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

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

Приближенный алгоритм называется асимптотически точным в классе задач J] = U{Pnn =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)\2V eRk, msLx\v\2

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

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

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

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

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

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

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

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

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

1Mb = у/(щи).

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

1. Агеев А. А., Бабурин А. Е., Гимади Э. X. Полиномиальный алгоритм с оценкой точности ¾ для отыскания двух непересекающихся гамильтоновых циклов максимального веса // Дискретный анализ и исследование операций. Серия 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. BerlinHeidelbergNew York: Springer-Verlag. 2004. P. 316−323.

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

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