Графы многогранников и сводимость задач комбинаторной оптимизации

скачать

 

Пароль для архива: hAwL9ibanBsEARy

 

Максименко Александр Николаевич

Графы многогранников и сводимость задач комбинаторной оптимизации

Специальность - дискретная математика и математическая кибернетика

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

Научный руководитель: доктор физ.-мат. наук, профессор В.А. Бондаренко

Ярославль 2004 г.

Оглавление

Введение 3

1Сложность в комбинаторной оптимизации 12

1.1. Некоторые сведения из теории сводимости задач............................. 12

1.2. Многогранники задач.................................................................................. 18

2.Конусное разбиение и аффинная сводимость 23

2.1. Конусное разбиение................................................................................... 23

2.2. Аффинная сводимость ............................................................................. 26

3.Труднорешаемые задачи 31

3.1. Задача КЛИКА ............................................................................................. 31

3.2. Задача 2-ВЫПОЛНИМОСТЬ ................................................................... 37

3.3. Задача РАЗРЕЗ........................................................................................... 39

3.4. Задача ТРЕХМЕРНОЕ СОЧЕТАНИЕ.................................................... 42

3.5. Задачи РЮКЗАК и РАЗБИЕНИЕ ............................................................ 47

3.6. Задача КОММИВОЯЖЕР.......................................................................... 57

3.6.1. Задача гамильтонов контур.................................................................. 58

3.6.2. Задача гамильтонов цикл..................................................................... 64

3.6.3. Задача коммивояжера

с условием "неравенство треугольника" .............................. 66

3.7.Задача ДЛИННЕЙШИЙ ПУТЬ .................................................................... 67

4.Полиномиально разрешимые задачи 70

4.1. Задача о кратчайшем пути ...................................................................... 70

4.2. Задачи о паросочетанпях......................................................................... 75

Заключение 81

Список литературы 85

Введение

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

Сформулируем условие задачи дискретной оптимизации следующим образом. Задано конечное множество X и функция с : X —>• i?, ставящая в соответствие каждому элементу х множества X некоторое число с(х). Требуется найти такой элемент ж* Е X, на котором данная функция принимает максимальное (или минимальное) значение, то есть для всех х G X выполнено с(ж*) > с(х) (пли с(ж*) < с(х)).

Среди множества всех задач дискретной оптимизации особо выде­ляются задачи комбинаторной оптимизации. Их отличие проявляется в комбинаторном характере множества X. Следуя совету И. Ньютона "при изучении наук примеры полезнее правил", рассмотрим классиче­ский пример — задачу о кратчайшем пути. Наиболее простая ее фор­мулировка выглядит так. Дано: множество из п городов, среди которых выделены два, и расстояния между городами. Требуется найти кратчай­ший путь между выделенными городами. (Предполагается, что кратчай­ший путь может проходить через несколько городов.) В этой задаче X — это множество всех возможных маршрутов. Комбинаторный харак­тер множества X проявляется, в частности, в экспоненциальном росте числа \Х\ всех допустимых решений при росте размерности задачи. Так, для задачи о кратчайшем пути

п-2

\Х\ = (п 2)! ^2 или, приближенно,

к=о

(п - 2)! < \Х\ < е(п - 2)!, где е = 2, 71828 ...

И уже для 20 городов число анализируемых маршрутов превышает 1016. Именно поэтому особое значение имеет проблема поиска алгоритмов, су­щественно более эффективных, чем полный перебор вариантов. К сожа­лению, число известных эффективных алгоритмов можно пересчитать по пальцам. В частности, для решения рассматриваемой задачи при есте­ственном предположении о неотрицательности расстояний между горо­дами можно воспользоваться алгоритмом Мура-Дейкстры [33, 52], или алгоритмом Флойда-Уоршелла [33], каждый из которых имеет полино­миальную трудоемкость. В то же время для большинства известных за­дач комбинаторной оптимизации эффективные алгоритмы до сих пор не найдены. Примером труднорешаемой задачи может служить все та же задача о кратчайшем пути, в которой расстояния могут принимать отрицательные значения. (Такая задача возникает, если под расстояния­ми понимать средства, затрачиваемые на передвижение, и предполагать, что передвижение из одного города в другой может быть прибыльным.) Приведенный пример позволяет оценить, насколько порой бывает труд­но определить, является ли данная задача труднорешаемой, или же для нее можно построить эффективный алгоритм. Одним из аспектов этой проблемы является вопрос о том, какие свойства той или иной задачи характеризуют ее как труднорешаемую. К настоящему времени сфор­мировались два подхода к поиску ответов на этот вопрос.

Первый (в хронологическом порядке) подход основан на теории эф­фективной (полиномиальной) сводимости задач распознавания свойств, развитой в работах С. Кука, Р. Карпа, Л. Левина (см. монографию Гэри и Джонсона [13]). Эта теория применима в первую очередь для класса NP всех переборных задач. В их число входят, в частности, и такие задачи распознавания, которые можно сформулировать как "упрощен­ный" вариант задач комбинаторной оптимизации. А именно, в условие задачи оптимизации вводится некоторое, наперед заданное число С, а цель задачи распознавания заключается в ответе на вопрос: верно ли, что найдется такой элемент х Е А, для которого с(х) > С (или с(х) < С для задачи на минимум). Основным достижением этой теории стало от­крытие Куком [22] так называемых АР-полных задач, которые в опре­деленном смысле являются самыми сложными в классе NP. Примером здесь может служить задача о кратчайшем пути в варианте распозна­вания, при условии, что расстояния между городами могут принимать и отрицательные значения: Существует ли такой путь между двумя вы­деленными городами, длина которого не превышала бы заданного числа С? В результате многочисленных безуспешных попыток поиска эффек­тивных алгоритмов решения таких задач сформировалась гипотеза об их труднорешаемостп. И, согласно этой гипотезе, любую задачу, част­ным случаем которой является АР-полная, принято считать трудноре­шаемой. Соответственно, если удается показать, что некоторая зада­ча распознавания, допускающая указанную выше формулировку, явля­ется труднорешаемой, то и соответствующая оптимизационная задача признается труднорешаемой. В заключение отметим, что список задач, труднорешаемость которых доказана, постоянно пополняется и в насто­ящее время содержит тысячи задач.

Другой подход к решению поставленной проблемы основан на изуче­нии комбинаторно-геометрических свойств задач и геометрической ин­терпретации алгоритмов. Первые исследования (см. напр. работу Гей-ла [10]) в этом направлении основаны на представлении множества X допустимых решений как множества точек в вещественном евклидовом пространстве Rm и на предположении, которое обычно выполнено, что функция цели с(х) является линейной: с(х) = (с, ж), где с Е Rm. Такая ин­терпретация позволяет ввести понятие многогранника М(Х) задачи А, представляющего собой выпуклую оболочку convX. Дальнейшие иссле­дования прежде всего связаны с изучением различных комбинаторных характеристик граничного комплекса (множества всех граней) много­гранников задач и использованием этих характеристик в качестве оце­нок сложности соответствующих задач в тех или иных классах алгорит­мов.

Наиболее ярким примером характеристики такого рода служит плот­ность графа многогранника задачи (напомним, что плотность графа равна максимальному числу его вершин, любые две из которых соеди­нены ребром). Известно (см. монографию Бондаренко [9]), что эта ве­личина является нижней оценкой сложности соответствующей задачи в широком классе алгоритмов прямого типа, использующих линейные сравнения. Установлено [9], что к этому классу относятся такие клас­сические комбинаторные алгоритмы, как алгоритмы сортировки, "жад­ный" алгоритм, различные варианты метода ветвей и границ, метод ди­намического программирования, алгоритмы типа "локальный поиск", венгерский алгоритм и другие широко распространенные практические методы комбинаторной оптимизации.

Отметим некоторые основные особенности обоих подходов. Заметим, что теория сводимости лишь дает способ сравнения задач по их сложно­сти и указывает "самые сложные" задачи, но ничего не говорит о при­чине их труднорешаемости. В то же время ее преимуществом является относительная простота. Преимуществом же геометрического подхода является возможность вычисления конкретных числовых характеристик сложности задач. Недостаток его состоит в том, что такие вычисления обычно сопряжены с серьезными трудностями. Так, например, Папади-митриу [61] показал, что для многогранника задачи коммивояжера про­блема распознавания смежности двух произвольно выбранных вершин является iVP-полной.

Особо выделим следующую, объединяющую указанные подходы осо­бенность. Как правило, изучаемая комбинаторно-геометрическая харак­теристика признается адекватной (подходящей), если она отвечает со­временным представлениям о сложности задач. Соответственно, не вы­зывает удивления тот факт, что для всех признанно труднорешаемых задач, многогранники которых были изучены, получены экспоненци­альные нижние оценки плотности полиэдральных графов (см. работы Белошевского [4], Бондаренко [6,9], Грешнева [11], Максименко [28,30], Симанчёва [35], Барахона и Маджуб [42]). В то же время для графов многогранников полиномиально разрешимых задач установлены полино­миальные (а для некоторых задач линейные) верхние и нижние оценки плотности (см. работы Белова [1,2], Бондаренко [5,8,9] и Шуниковой [7], Максименко [26,27]). Это наталкивает на мысль о том, что между тео­рией сводимости задач и исследованиями комбинаторных характеристик их многогранников существует некоторая взаимосвязь. Выявление этой взаимосвязи позволило бы объединить указанные подходы в единую тео­рию и подтвердило бы гипотезу о том, что "адекватные" комбинаторные характеристики многогранников труднорешаемых задач экспоненциаль­ны.

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

С другой стороны, исследуются свойства относительно мало изучен­ной геометрической конструкции — конусного разбиения пространства исходных данных задачи. Отметим, что это понятие было использова­но Бондаренко [5, 6] при установлении взаимосвязи между плотностью графа многогранника и сложностью соответствующей задачи. Проявле­ние интереса к исследованию свойств этой геометрической конструкции прежде всего связано с известным фактом о том, что конусное разбие­ние — двойственная к многограннику задачи конструкция. Оказывается, конусное разбиение является более гибким и мощным инструментом для исследования свойств задач, чем их многогранники. Так, с помощью ко­нусного разбиения можно изучать комбинаторно-геометрические харак­теристики сложности для частных случаев задач, в то время как свой­ства многогранника характеризуют только общую задачу. Впервые это было обнаружено в работе [28] при исследовании классической задачи о кратчайшем пути, в которой, как известно, накладываются ограничения неотрицательности расстояний.

Далее, на основании изложенных фактов делается вывод о том, что при аффинном сведении задачи X к задаче Y конусное разбиение мно­жества исходных данных первой задачи аффинно преобразуется в не­которую часть конусного разбиения множества исходных данных вто­рой задачи. При детальном изучении этого явления обнаруживается, что при аффинном сведении задач граф многогранника М(Х) первой зада­чи оказывается изоморфным некоторому подграфу графа многогранни­ка M(Y) второй задачи. Таким образом доказывается гипотеза о том, что граф многогранника "более сложной" задачи конструктивно слож­нее графа многогранника "простой" задачи. В частности, следствием этого утверждения является соответствующее соотношение плотностей р(Х) и p(Y) графов многогранников задач: р(Х) < p(Y).

Так, с возникновением нового понятия аффинной сводимости задач комбинаторной оптимизации появляется и новый подход к изучению сложности задач. По сути своей он похож на классическую теорию сво­димости, но, естественно, имеет ряд существенных отличий. Во-первых, новый подход предназначен для изучения задач комбинаторной опти­мизации с линейной целевой функцией. Тогда как классическая теория работает прежде всего с задачами распознавания. Во-вторых, оказыва­ется, что при сведении задач комбинаторной оптимизации крайне труд­но нарушить свойство аффинности при преобразовании вектора исход­ных данных одной задачи в вектор исходных данных другой задачи. Та­ким образом аффиная сводимость для таких задач наиболее естественна. Третье отличие заключается в понятии сложности. Классическая тео­рия, говоря упрощенно, делит задачи по сложности на три класса: труд-норешаемые, полиномиально разрешимые, и задачи, принадлежность ко­торых к этим двум классам не установлена. В новом подходе сложность задачи можно оценить числом. В частности, плотностью графа ее мно­гогранника. Четвертое, объединяющее свойство: В основе нового под­хода, как и в основе классической теории лежит доказательство труд-норешаемости одной определенной задачи. В классической теории это задача ВЫПОЛНИМОСТЬ, а в настоящей работе исследование слож­ности труднорешаемых задач начинается с непосредственного изучения графа многогранника задачи КЛИКА.

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

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

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

В третьей, наиболее емкой главе приводятся многочисленные "экс­периментальные данные", подтверждающие работоспособность предла­гаемои теории. 1лава начинается с непосредственного изучения свойств многогранника "основной" задачи — оптимизационной задачи КЛИКА. Доказывается, что плотность графа этого многогранника совпадает с числом вершин и равна 2", где п — размерность задачи.

Дальнейшее развитие теории аффинной сводимости происходит по классическому сценарию. Конструируется алгоритм сведения "первой" задачи к "еще не изученной" задаче и доказывается, что он удовлетво­ряет условиям аффинности. Таким образом пополняется список задач с экспоненциальной плотностью полиэдрального графа. Процесс пополне­ния этого списка существенно облегчается за счет схожести оптимиза­ционных задач и задач распознавания. Это позволяет при конструирова­нии алгоритмов сведения оптимизационных задач пользоваться идеями алгоритмов сведения задач распознавания, известными из классической теории [13]. Тем не менее, некоторые алгоритмы аффинной сводимости в настоящей работе предложены впервые.

Структуру этой главы удобно изобразить в виде ориентированного дерева (см. рис. 1). Каждая стрелка на рисунке символизирует алгоритм, сводящий задачу, расположенную в начале стрелки, к задаче, находящей­ся в конце. В корне дерева расположена "основная" задача КЛИКА. В список исследуемых задач в первую очередь вошли наиболее известные классические задачи. В их числе оптимизационные варианты пяти из шести задач, фигурирующих в [13] как основные iVP-полные задачи.

В четвертой главе изучаются комбинаторно-геометричекие свой­ства полиномиально разрешимых задач: задачи о кратчайшем пути, за­дачи о назначениях и задачи о паросочетаниях в произвольном графе. Для графа конусного разбиения задачи о кратчайшем пути значение плотности вычисляется непосредственно. Далее показывается, что эта задача аффинно сводится к задаче о назначениях, что позволяет оце­нить снизу плотность графа многогранника последней задачи и задачи о паросочетаниях.


КЛИКА, ВЕРШИННОЕ ПОКРЫТИЕ, НЕЗАВИСИМОЕ МНОЖЕСТВО


2-ВЫПОЛНИМОСТЬ


РАЗРЕЗ


3-СОЧЕТАНИЕ


КОММИВОЯЖЕР


РЮКЗАК, РАЗБИЕНИЕ

ДЛИННЕЙШИЙ ПУТЬ


Рис. 1. Диаграмма сведения трудно-решаемых задач.

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

1. Понятие сложностив комбинаторной оптимизации

1.1. Некоторые сведения из теории сводимости за­дач

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

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

Наиболее простым объектом для изучения этой проблемы оказались задачи из класса NP. Классическим примером такой задачи служит зна­менитая задача коммивояжера (КОММИВОЯЖЕР). В ней рассматрива­ется полный реберно взвешенный граф G(V,E), где V = {г>1,г>2, • • • ,vn} — множество вершин, Е = {е^- = (vi,Vj) : 1 < г < j < п} — мно­жество ребер. На множестве ребер задана функция длин с : Е —>• i?, приписывающая каждому ребру е^- Е Е длину с^- = c(e;j) Е R. Назовем гамилътоновым цикл, проходящий через каждую вершину графа ровно