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

РОССИЙСКАЯ АКАДЕМИЯ НАУ1 СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им С Л СОБОЛЕВА

На правах рукописи

БАБУРИН Алексей Евгеньевич

АЛГОРИТМЫ С ОЦЕНКАМИ ДЛЯ НЕКОТОРЫХ МОДИФИКАЦИЙ ЗАДАЧ КОММИВОЯЖЕРА И РАЗБИЕНИЯ МНОЖЕСТВА

(01 01 09 - дискретная математика и математическая кибернетика)

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск 2007

003069802

Работа выполнена в Институте математики им. С. Л Соболева СО РАН.

Научный руководитель- д ф -м.н , профессор Э. X. Гимади Официальные оппоненты д ф -м.н , профессор В. А Емеличев

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

и математической геофизики СО РАН

Защита состоится " 23 " мая 2007 г в 16 часов на заседании диссертационного совета Д 003 015.01 в Институте математики им С. Л Соболева СО РАН (пр. Академика Коптюга, 4, 630090 Новосибирск).

С диссертацией можно ознакомиться в библиотеке Института математики СО РАН.

Автореферат разослан " 23 " апреля 2007 г.

Ученый секретарь диссертационного совета доктор физ -мат наук

Ю В Шамардин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Диссертация посвящена исследованию ряда за,-дач комбинаторной оптимизации, представляющих интерес как с точки зрения теории, так и с практической стороны

Для задач, которые являются NP-трудными, особый интерес представляет построение приближенных алгоритмов с априорными оценками точности

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные" результаты диссертации докладывались на Российской конференции ''Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004), на Международной научной студенческой конференции (Новосибирск, 2000), на Международных конференциях по исследованию операций (Ж2002 (Клагенфурт, 2002), СЖ2003 (Гей-дельберг, 2003), (Ж2004 (Тилбург, 2004), на Всероссийской конференции "Методы оптимизации и экономические приложения' (Омск, 2003, 2006), на семинаре проф Брукера университета г. Оснабрюк (Оснабрюк, 2004), на семинаре по дискретной математике Санкт-Петербургского отделения Института математики им Стеклова (Санкт-Петербург, 2005), на семина-

ре Объединенного Института Проблем Информатики (Минск, 2007), на научных семинарах Института математики им Соболева СО РАН

Публикации. По теме диссертации автором опубликовано 11 работ Структура и объем работы. Диссертация изложена на 98 страницах, содержит введение, три главы, -заключение, список публикаций автора по теме диссертации, благодарности и список литературы, содержащий 63 наименования.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

В первой главе рассматриваются задачи поиска гамильтоновых циклов экстремального веса

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

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

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

В разделе 1.1 рассматривается евклидова задача коммивояжера на максимум

В пункте 111 приводится постановка задачи.

Пусть задан набор точек X = (xi,x2, ,хп) сRk. Определим вес W гамильтонова цикла, порожденного перестановкой а е Sn и обозначаемого как

Т1-1 г=1

где р(*, *) — метрика Я*

Требуется максимизировать И7 (с) по всем перестановкам ст го ,5П

В пунктах 1.1 2 и 1.1.3 описывается известный полиномиальный асимптотически точный алгоритм А И Сердюкова, выявляются возможности по его модификации с целью улучшения оценок точности Для решения задачи предлагается и исследуется новый алгоритм с временной сложностью 0(п3)

При решении задачи коммивояжера на максимум удалось использовать следующее специальное свойство евклидова пространства Пусть даны два отрезка (ребра) 1} — {х3,у3), 1{ — (х;,у{) в Ик и а < к/2 — угол между ними Тогда справедливо неравенство

^(ж^аи) + +

> шах|г«(-Г3),'ш(/(), соб — (и>(13) +

где ги—расстояние между точками в евклидовом пространстве

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

Лемма 1 Пусть в евклидовом пространстве Екс фиксированной размерностью к задано произвольное множество из £ прямолинейных отрезков Тогда наименьший угол между двумя отрезками из этого множества ограничен сверху константой а(к,Ь) такой, что а(к, Ь) —> 0 при ¿-»оо При этом

8Шз£!М< т*

тах

2 - £2/(А:-1) '

где константа 7 к за висит лишь от размерности пространства Пк.

Одним из основных этапов алгоритма А И Сердюкова является процедура разбиения максимального паросочетания М на множество легких и тяже лых ребер Далее производится соединение пар ребер из паросо-ченания, данный процесс производится только над подмножеством тяжелых ребер М Распространение данного процесса на все ребра паросочетания М сопровождается уменьшением количества "свободных" (еще не

б

задействованных) ребер и по лемме 1 дает все меньшие и меньшие оценки суммарного веса получаемых соединяющих ребер, что в итоге приводит к ухудшению эффективности алгоритма Оказывается, что при наложении некоторых достаточно слабых ограничений на исходный граф, данный процесс допускает эффективное продолжение на все паросочетание М Это, в свою очередь, делает ненужными последующие шаги алгоритма А. И Сердкжова.

Основным результатом в пункте 1.1.3 является следующая теорема, обосновывающая качественные характеристики нового предложенного алгоритма

Теорема 1 При выполнении условия

8к{Х) =

о(п2) 0(ф

к = 2, к = 3, к> 3,

о(п*2-')

(где 5к{Х) — отношение диаметра множества X к длине наименьшего отрезка, соединяющего две различные точки этого множетсва) алгоритм Ах находит асимптотически точное решение задачи отыскания максимального взвешенного гамилътонова обхода заданного множества точек X, состоящего из п точек в евклидовом пространстве Ик. При более сильном ограничении

*к(Х) <

С2п С1 г

СкпТ+

5

по

к = 2, к = 3, ^ к> 3,

(где С к — константа, зависящая только от размерности пространства Нк) обладает лучшими оценками точности по сравнению с алгоритмом А. И Сердюкова

В разделе 1.2 рассматриваются задачи отыскания в полном неориентированном взвешенном графе двух (реберно) непересекающихся гамиль-тоновых циклов экстремального веса

В пункте 1 2.1 приводится общая постановка задач Дан полный п-вершинный неориентированный граф <7 = (V, Е) На ребрах графа заданы две функции №1 £-»й+и«2 Е —> Я+. Требуется найти в графе в

такие два реберно непересекающихся гамильтонова цикла Ях и Яг, чтобы достигала минимума (или максимума) величина W\(H{) + И^Яг), где = £ебЯ«;,(е), г £{1,2}

В пункте 12 2 рассматривается случай, когда весовые функции ребер и №2 совпадают и требуется максимизировать величину И7](Ях) + И/2(Я2)

Предлагается полиномиальный алгоритм А г приближенного решения поставленной задачи В основе алгоритма лежит общая идея, впервые реализованная А И Сердюковым при построении приближенного алгоритма для нахождения одного гамильтонова цикла максимального веса в полном неориентированном взвешенном графе с теми же оценками временной сложности и точности Алгоритм Сердюкова в исходном графе находит два подграфа - 2-фактор и паросочетание, суммарный вес которых не менее чем в 3/2 раза больше веса оптимального решения Затем ребра этих подграфов перераспределяются между двумя частичными турами, произвольно дополняемыми до гамильтоновых циклов Максимальный из построенных циклов (по весу входящих в него ребер) дает решение с оценкой точности 3/4 Нетрудно понять, что прямое применение этой схемы к решению поставленной задачи не приводит к успеху, поскольку построенные таким образом частичные туры могут содержать одинаковые ребра. В настоящей диссертации представлен алгоритм, в котором в качестве исходного подграфа, подвергающегося разбиению на два непересекающихся по ребрам частичных тура, используется либо кубический подграф (при четном п), либо "почти кубический" подграф (при нечетном тг) максимального веса Более того, найденные реберно непересекающиеся частичные туры в дальнейшем удается дополнить до непересекающихся по ребрам гамильтоновых циклов, что далеко не всегда возможно в случае произвольных реберно непересекающихся частичных туров

Для построенного алгоритма доказывается следующая теорема-

Теорема 2 Алгоритм Л2 .за время 0(п3) находит допустимое решение задачи отыскания в полном неориентированном, взвешенном, графе двух реберно непересекающихся, гам,ильтоновы,х циклов максимального веса, вес которого составляет не м,енее 3/4 от веса оптимального решения

В пункте 12 3 рассматривается случай, когда весовые функции ребер u>i и W2 совпадают Будем обозначать для удобства эту функцию через w Также предполагается, что для функции w выполняется неравенство треугольника w(i,j) < w(i, k) + w(j, k) для любых трех вершин г, j, k е V,

те исходная задача является метрической Требуется минимизировать величину ИМЯ,) + И^Ят)

Для данной задачи предлагается приближенный алгоритм Л3, основанный на построении первого цикла с помощью алгоритма Косточки-Сердюкова приближенного решения метрической задачи коммивояжера на минимум Второй цикл получается определенной перестройкой порядка следования вершин в первом цикле, при этом способ построения второго цикла различается для случаев четного и нечетного числа п вершин в исходном графе

Для предложенного алгоритма доказывается следующая теорема-

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

д — / 9/4, если п нечетно,

\ 9/4 + 3/п в противном сл/учае

В пункте 12 4 рассматривается случай, когда весовые функции IV х и и>2 различны Также предполагается, что для каждой из них выполняется неравенство треугольника Требуется минимизировать величину (#1)+

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

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

Теорема 4 В случо,е двух весовых функций алгоритм А4 находит приближенное решение метрической задачи отыскания в полном неориентированном взвешенном; графе двух реберно непересекающихся гам,ильтоно-вых циклов м,инималъного суммарного веса за время, 0{п3) с гарантированной оценкой точности

д < Г (12/5), если п крат,но 5,

~ \ (12/5) (1 + 1/п) в противном случае

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

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

В пункте 2.1 1 приводится постановка задачи. Задан полный неориентированный граф С(у, Е) без петель с п вершинами На ребрах графа определена весовая функция ги Е —» Д+, а для вершин графа заданы такие натуральные числа ¿г (г = 1, , п), 1 < ¿г < п, что набор (¿1, , с1п) является графическим разбиением их суммы ]СГ=1 ¿г В графе С{у, Е) требуется найти связный остовный подграф с максимальным суммарным весом ребер и заданными степенями вершин ¿г (г = 1, , п), 1 < ¿г < п Данная задача обозначается далее как СБИР

В пункте 2 12 описывается новый алгоритм А$ приближенного решения СБОР Алгоритм основан на нахождении точного решения релаксации исходной задачи (без условия связности решения) с применением алгоритма Габова Компоненты связности полученного решения претерпевают процедуру "склейки", в ходе которой степени вершин остаются неизменными, граф приобретает свойство связности, а потеря веса, вызванная изменением состава ребер в ходе выполнения этой процедуры, минимальна

Пункт 2.1 3 посвящен анализу построенного алгоритма Основным результатом этого анализа является следующая теорема

Теорема 5 Алгоритм А$ находит приближеннее решение СБИР за время 0(тп2) с оценкой точности

9

Д > 1 -

d(d + 1)'

где d = тт{с/г|?, = 1, , n}, т — 2Г=1 При решении метрической CSDP оценка точности алгоритма составляет

Д>1 1

d(d+ 1)

При решении евклидовой CSDP оценка точности алгоритма составляет

d(d + 1)

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

В пугаете 2 2 1 приводится постановка задачи Задан С{у, Е) — полный неориентированный граф без петель с п вершинами Определена функция ■ш Е —> В+ и натуральное число й, 1 < с1 < п Требуется найти в графе <3 связный остовный ¿-однородный подграф С? максимального суммарного веса

В пункте 2.2 2 обосновывается NР-трудность поставленной задачи для произвольного й

В пункте 2.2 3 предлагается новый полиномиальный алгоритм А6 приближенного решения данной задатт. Алгоритм основан на декомпозиции исходной задачи и применении известных эвристик к решению ряда полученных задач коммивояжера и назначения Данный алгоритм имеет временную сложность 0(п2 + псПпп)

В пункте 2 2 4 проведен общий вероятностный анализ построенного алгоритма Ас Для исследования качества приближенного алгоритма используется идея построения алгоритмов с оценками (е, 6), предложенная Э X Гимади, Н И. Глебовым и В А Перепелицей

Пусть К. — некоторый класс оптимизационных задач Посредством Р*(5') обозначим оптимальное значение целевой функции для задачи 5" б /С Будем считать, что рассматривается задача на минимум и Е* (8) > О для всех 5 е К,

Пусть заданы класс задач К. и некоторое семейство V вероятностных мер, определенных на К.. Будем говорить, что алгоритм Л имеет оценки (е,<5) относительно V, если

Р{Рл(5)>(1+£)Р*(-5)}<<5

для всех Р е V

Будем далее говорить о классах /Сп задач размерности п, семействах Р„, оценках (еп, 5п) и их свойствах в зависимости от параметра п

Алгоритм А называется асимптотически точным на классе задач /С, если существуют такие последовательности 5П), что для любого п алгоритм А удовлетворяет оценкам (еп, 5п) на подмножестве /Сп с /С и при этом еп -* О, (5П —> 0 при п —> оо

Параметры еп и 6п могут трактоваться как оценки относительной погрешности и вероятности несрабатывания алгоритма соответственно Аналогичным образом определяется понятие асимптотической точности при решении задачи на максимум

. *iiU

d - 1N 2"

В пункте 2 2 5 анализ алгоритма Лб проводится для класса 1Стах(0,1) задач отыскания максимального (относительно суммарного веса ребер) d-регулярного остовного связного подграфа в полном неориентированном графе с элементами матрицы расстояний, являющимися независимыми случайными величинами, распределенными равномерно на отрезке [0,1] Доказывается следующее утверждение-

Лемма 2 Алгоритм Aq решения задач из класса /Сшах(0,1) за время 0(п2 + nd\nn) находит приближенное решение со следующим,и оценками относительной погрешности

£п = 'ШГ{1 + п)

v вероятности несрабатывания

\ п /

где 0 < q < d - 1, x{d) = |(d - 2) ^d - 3 - p(d - 1)^

Из леммы 2 непосредственно следует

Теорема 6 Алгоритм, AG для, решения задач из класса К.тах{0,1) является, асимптотически точным при d = о(п)

В пункте 2 2 6 полученный результат обобщен на случай так называемых распределений минорирующего типа. Рассмотрим

класс /СтаХ(0,1) матриц расстояний, элементы которых распределены независимо на отрезке [0,1] с функцией распределения F(x) такой, что F(x) < х при 0 < х < 1 Тогда распределение F(x) совпадает с распределением величины /(f), где f е /[0,1], /- монотонно возрастающая функция, при этом /(0) = 0, /(1) = 1, f (x) > х при 0 < х < 1

Теорема 7 Алгоритм Aq решения исходной задачи я,вляется асимптотически точным на классе /Стаз-(0,1) при d = о[п).

В пункте 2 2 7 получены следующие обобщения упомянутых ранее результатов

Утверждение 1 Если d = о(п), то для произвольных О < ап <Ъп алгоритм Ag является, асимптотически точным на классе задач 1Стах(ап, Ъп) при тех otee оценках точности, вероятности несрабатывания и временной сложности, "то и для класса 1Стах(0,1)

Алгоритм AG легко модифицировать в приближенный алгоритм А! для решения задачи на минимум на классе ¡Стгп(ап,Ьп)

/Стгп(ап, Ъп) — класс матриц расстояний, элементы которых распределены независимо на отрезке [а„, Ьп\ с функцией распределения F{х) такой, что F(x) > ПРИ ап < х < bn

Отличие алгоритма А'6 от алгоритма A<¡ заключается в том, что на шагах 1 и 2 выбор очередного ребра (элемента матрицы) осуществляется исходя из минимизационных соображений Результатом вероятностного анализа в этом случае является следующее утверждение

Утверждение 2 Если d = о(п), то для произвольных О < ап <Ьп алгоритм A'q, асимптотически точен на классе задач 1Стгп{ап,Ьп) с оценкой относительной погрешности

и с теми же оценками вероятности несрабатывания и временной сложности, 'что и для класса, К^гпах (ап, Ъп), при дополнительном требовании па разброс элементов матрицы расстояний между вершинами (отношение границ Ьп и ап)

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

В разделе 3.1 приводится постановка задачи Пусть в векторном пространстве Нк с нормой || ||», которое будем обозначать через (Як,|| ||*), задано конечное семейство ненулевых векторов V — {г^, г>2, ,ип} Определим функцию Бу{х) = ^2г=1угхг Переменной X = (XI,Х2, ,хп) € {—1,1}п Для заданного семейства входных векторов V требуется найти вектор х е {-1,1}", максимизирующий функцию ]|5у (а:)||*

Обозначим через {а, Ь) скалярное произведение векторов а и Ь из Кк Рассмотрим выпуклый полиэдр В — {х е Л* | (Хг,х) < 1, 1 < г < т} с

т гранями Г,, 1 < г < т, такими, что 1'\ с {х е | (А,, а;) = 1}, где

Полиэдральной норм,ой вектора х е 11к называется величина

с{х) = шах|о, (Ах,ж), , (Ат,ж)}

В дальнейшем под полиэдральным пространством размерности к будем понимать пару (В.*,с)

В разделе 3.2 описывается полиномиальный алгоритм, находящий точное решение задачи разбиения множества векторов в полиэдральном пространстве {Як,с) с конечной нормой.

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

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

Ортогональной гиперплоскостью для ненулевого вектора чей' называется гиперплоскость, заданная уравнением (у, х) — 0 Она является (к — 1)-мерным подпространством, состоящим из векторов, ортогональных вектору и Семейством областей принадлежности решения (ОПР) для данных ненулевых векторов VI, ,ип назовем семейство максимальных по включению связных подмножеств пространства Ик, не пересекающихся с ортогональными гиперплоскостями векторов ух,у2, ,уп Заметим, что области принадлежности решения являются конусами в пространстве Пк

Набор векторов пространства Ик, содержащий ровно по одному вектору из каждой области семейства ОПР, назовем семейством представителей ОПР для векторов тл, ь°2, , ип

Предлагаемый алгоритм строит для исходных векторов у\,ь2, ,ип семейство XV представителей ОПР. Для каждого вектора и) £ IV строится решение ху, задачи такое, что

_ Г 1, если (и),иг) > О, т ~ \ -1 в противном случае

Из набора построенных решений задачи выбирается оптимальное

В разделе показано, что такой алгоритм является точным и имеет временную сложность 0(к2пк)

Основные результаты диссертации опубликованы в работах

1. Агеев А. А., Бабурин А. Е., Гимади Э. Х- Полиномиальный алгоритм с оценкой точности 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 subgiaph of maximum weight // Proceedings of the 2-nd International Workshop "Discrete Optimization Methods m Production and Logistics", Omsk 2004 P 14&-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 Papeis International Conference OR 2004, Tilburg Berlin Springer-Veilag 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 Mimmum Total Weight // Operations Research Proceedings Berlin, Heidelberg, New York Springer-Verlag 2004 P 316-323

Бабурин Алексей Евгеньевич

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 17 04.07. Формат 60x84 1/16. "Усл. печ л 1,0 Уч-изд л 1,0 Тираж 100 экз Заказ № 56

Отпечатано в ООО "Омега Принт" 630090, Новосибирск, пр Лаврентьева, 6

Введение

Глава 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. Гимади за предложенную тему исследований и поддержку па протяжении всего времени работы над диссертацией. Также я благодарен сотрудникам отдела теоретической кибернетики Института математики СО РАН им. С. Л. Соболева, чьи критические замечания и советы помогли мне получить эти результаты: А. А. Агееву, Н. И. Глебову, М. Г. Пащенко, А. В. Пяткину, а. также С. В. Севастьянову.

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.