Введение 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 R, ставящая в соответствие каждому элементу х множества X некоторое число с(т). Требуется найти такой элемент ж* Е X. на котором данная функция принимает максимальное (или минимальное) значение, то есть для всех х Е X выполнено с(ж*) > с(т) (или с(ж*) < с(т)).
Среди множества всех задач дискретной оптимизации особо выделяются задачи комбинаторной оптимизации. Их отличие проявляется в комбинаторном характере множества X. Следуя совету И. Ньютона ’’при изучении наук примеры полезнее правил”, рассмотрим классический пример — задачу о кратчайшем пути. Наиболее простая ее формулировка выглядит так. Дано: множество из п городов, среди которых выделены два, и расстояния между городами. Требуется найти кратчайший путь между выделенными городами. (Предполагается, что кратчайший путь может проходить через несколько городов.) В этой задаче X — это множество всех возможных маршрутов. Комбинаторный характер множества X проявляется, в частности, в экспоненциальном росте числа |Х| всех допустимых решений при росте размерности задачи. Так,
для задачи о кратчайшем пути
п—2
|Х| = (п — 2)! 22 или, приближенно,
k=0
(п — 2)! < |Х| < е(п — 2)!, где е = 2, 71828 ...
И уже для 20 городов число анализируемых маршрутов превышает 1016. Именно поэтому особое значение имеет проблема поиска алгоритмов, существенно более эффективных, чем полный перебор вариантов. К сожалению, число известных эффективных алгоритмов можно пересчитать по пальцам. В частности, для решения рассматриваемой задачи при естественном предположении о неотрицательности расстояний между городами можно воспользоваться алгоритмом Мура-Дейкстры [33, 52], или алгоритмом Флойда-Уоршелла [33], каждый из которых имеет полиномиальную трудоемкость. В то же время для большинства известных задач комбинаторной оптимизации эффективные алгоритмы до сих пор не найдены. Примером труднорешаемой задачи может служить все та же задача о кратчайшем пути, в которой расстояния могут принимать отрицательные значения. (Такая задача возникает, если под расстояния¬ми понимать средства, затрачиваемые на передвижение, и предполагать, что передвижение из одного города в другой может быть прибыльным.) Приведенный пример позволяет оценить, насколько порой бывает труд¬но определить, является ли данная задача труднорешаемой, или же для нее можно построить эффективный алгоритм. Одним из аспектов этой проблемы является вопрос о том, какие свойства той или иной задачи характеризуют ее как труднорешаемую. К настоящему времени сформировались два подхода к поиску ответов на этот вопрос.
Первый (в хронологическом порядке) подход основан на теории эффективной (полиномиальной) сводимости задач распознавания свойств, развитой в работах С. Кука, Р. Карпа, Л. Левина (см. монографию Гэри и Джонсона [13]). Эта теория применима в первую очередь для класса NP всех переборных задач. В их число входят, в частности, и такие задачи распознавания, которые можно сформулировать как ’’упрощенный” вариант задач комбинаторной оптимизации. А именно, в условие задачи оптимизации вводится некоторое, наперед заданное число С, а цель задачи распознавания заключается в ответе на вопрос: верно ли, что найдется такой элемент х Е X, для которого с(ж) > С (или с(ж) < С для задачи на минимум). Основным достижением этой теории стало открытие Куком [22] так называемых XF-полных задач, которые в определенном смысле являются самыми сложными в классе NP. Примером здесь может служить задача о кратчайшем пути в варианте распознавания, при условии, что расстояния между городами могут принимать и отрицательные значения: Существует ли такой путь между двумя выделенными городами, длина которого не превышала бы заданного числа С? В результате многочисленных безуспешных попыток поиска эффективных алгоритмов решения таких задач сформировалась гипотеза об их труднорешаемости. И, согласно этой гипотезе, любую задачу, частным случаем которой является XF-полная, принято считать труднорешаемой. Соответственно, если удается показать, что некоторая задача распознавания, допускающая указанную выше формулировку, является труднорешаемой, то и соответствующая оптимизационная задача признается труднорешаемой. В заключение отметим, что список задач, труднорешаемость которых доказана, постоянно пополняется и в настоящее время содержит тысячи задач.
Другой подход к решению поставленной проблемы основан на изучении комбинаторно-геометрических свойств задач и геометрической интерпретации алгоритмов. Первые исследования (см. наир, работу Гей¬ла [10]) в этом направлении основаны на представлении множества X допустимых решений как множества точек в вещественном евклидовом пространстве Rm и на предположении, которое обычно выполнено, что функция цели с(ж) является линейной: с(ж) = (с, ж), где с Е Rm. Такая интерпретация позволяет ввести понятие многогранника М(Х) задачи X, представляющего собой выпуклую оболочку convX. Дальнейшие исследования прежде всего связаны с изучением различных комбинаторных характеристик граничного комплекса (множества всех граней) многогранников задач и использованием этих характеристик в качестве оценок сложности соответствующих задач в тех или иных классах алгоритмов.
Наиболее ярким примером характеристики такого рода служит плотность графа многогранника задачи (напомним, что плотность графа равна максимальному числу его вершин, любые две из которых соединены ребром). Известно (см. монографию Бондаренко [9]), что эта величина является нижней оценкой сложности соответствующей задачи в широком классе алгоритмов прямого типа, использующих линейные сравнения. Установлено [9], что к этому классу относятся такие классические комбинаторные алгоритмы, как алгоритмы сортировки, ’’жадный” алгоритм, различные варианты метода ветвей и границ, метод динамического программирования, алгоритмы типа ’’локальный поиск”, венгерский алгоритм и другие широко распространенные практические методы комбинаторной оптимизации.
Отметим некоторые основные особенности обоих подходов. Заметим, что теория сводимости лишь дает способ сравнения задач по их сложности и указывает ’’самые сложные” задачи, но ничего не говорит о при¬чине их труднорешаемости. В то же время ее преимуществом является относительная простота. Преимуществом же геометрического подхода является возможность вычисления конкретных числовых характеристик сложности задач. Недостаток его состоит в том, что такие вычисления обычно сопряжены с серьезными трудностями. Так, например, Пападимитриу [61] показал, что для многогранника задачи коммивояжера проблема распознавания смежности двух произвольно выбранных вершин является УР-полной.
Особо выделим следующую, объединяющую указанные подходы особенность. Как правило, изучаемая комбинаторно-геометрическая характеристика признается адекватной (подходящей), если она отвечает со-временным представлениям о сложности задач. Соответственно, не вызывает удивления тот факт, что для всех признанно труднорешаемых задач, многогранники которых были изучены, получены экспоненциальные нижние оценки плотности полиэдральных графов (см. работы Белошевского [4], Бондаренко [6,9], Грешнева [11], Максименко [28,30], Симанчёва [35], Барахона и Маджуб [42]). В то же время для графов многогранников полиномиально разрешимых задач установлены полиномиальные (а для некоторых задач линейные) верхние и нижние оценки плотности (см. работы Белова [1,2], Бондаренко [5,8,9] и Шуниковой [7], Максименко [26,27]). Это наталкивает на мысль о том, что между теорией сводимости задач и исследованиями комбинаторных характеристик их многогранников существует некоторая взаимосвязь. Выявление этой взаимосвязи позволило бы объединить указанные подходы в единую теорию и подтвердило бы гипотезу о том, что ’’адекватные” комбинаторные характеристики многогранников труднорешаемых задач экспоненциальны.
За последние два - три десятилетия накопилось большое число результатов, касающихся свойств многогранников задач комбинаторной оптимизации. Прежде всего это связано с тем, что, как известно, комбинатор¬но-геометрические свойства многогранника являются характеристиками сложности соответствующей задачи в том или ином классе алгоритмов. К сожалению, многогранник ассоциируется только с общей задачей, в которой отсутствуют какие либо ограничения на множество исходных данных. Тем не менее, изучение на предмет сложности частных случаев задачи нередко представляет гораздо больший интерес. Именно это послужило причиной появления новой геометрической конструкции — многогранного разбиения пространства исходных данных задачи. Эта структура позволяет исследовать комбинаторно-геометрические свойства таких задач, для которых построение многогранника в явном виде невозможно.
Изучение свойств этой конструкции позволило по новому взглянуть на классическую теорию сводимости задач. Оказалось, что при сведении задачи X к задаче Y множество исходных данных первой задачи, как правило, аффинно отображается в множество исходных данных второй задачи. Так появляется новый тип сводимости — аффинная сводимость задач комбинаторной оптимизации. Одним из замечательных свойств которой является то, что если X ocj У, то многогранное разбиение пространства исходных данных первой задачи аффинно отображается в некоторую часть многогранного разбиения прстранства исходных данных второй задачи. Как следствие, граф G(X) многогранника М(Х) оказывается изоморфным некоторому подграфу графа G(Y) многогранника второй задачи.
Практическая целесообразность введения этого нового типа сводимости задач комбинаторной оптимизации подтверждается описанными в настоящей работе многочисленными экспериментальными данными. Так, на основе классических алгоритмов сведения удалось показать, что наиболее простой для изучения граф многогранника задачи КЛИКА изоморфен графу многогранника задачи максимальная 2- ВЫПОЛНИМОСТЬ и графу многогранника задачи максимальный РАЗ-РЕЗ. Также упомянутый граф оказывается изоморфным некоторым подграфам графов многогранников таких труднорешаемых задач как 3- СОЧЕТАНИЕ, РЮКЗАК, КОММИВОЯЖЕР и ДЛИННЕЙШИЙ ПУТЬ. Кроме того, структура конусного разбиения для задачи КЛИКА оказалась изоморфна некоторой части конусного разбиения задачи РАЗБИЕНИЕ и задачи коммивояжера для длин ребер (дуг) которой выполнено условие ’’неравенства треугольника”.
Опираясь на доказанное в работе утверждение о том, что граф многогранника задачи КЛИКА является полным, были получены экспоненциальные нижние оценки плотности графов многогранников перечисленных выше задач:
6) Плотность графа многогранника задачи ГАМИЛЬТОНОВ ЦИКЛ в настоящей работе оценивается снизу величиной 2^-3/2. Ранее [9]
„ vr_5
плотность оценивалась величиной 22^ .
7) Для графов многогранников МДД) и М(£п) задач ДЛИННЕЙШИЙ ПУТЬ и ДЛИННЕЙШАЯ ЦЕПЬ впервые получены экспоненциальные нижние оценки плотности: р(£'п) > 2V(n-1)/2-1 И р(Сп) > ДДЁ-ЪД
8) Кроме того, были исследованы графы конусных разбиений задачи РАЗБИЕНИЕ и задачи КОММИВОЯЖЕР с условием ’’неравенство треугольника”. Оказалось, что граф для первой задачи совпадает с графом многогранника задачи РЮКЗАК, а граф для второй задачи идентичен графу многогранника задачи КОММИВОЯЖЕР.
Наряду с этим, в работе изучены комбинаторно-геометрические свойства таких полиномиально разрешимых задач как классическая задача о кратчайшем пути (ЗКП), задача о назначениях (ЗН) и задача о паросочетаниях (ЗП) в произвольном графе. Оказалось, что классическая ЗКП аффинно сводится к ЗН. Отсюда следует, в частности, что плотности графов многогранников ЗН и ЗП оцениваются снизу величиной ],
где п — число работников в ЗН. Плотность графа конусного разбиения классической ЗКП вычисляется в настоящей работе непосредственно и оказывается равной [^].
Полученные результаты говорят о перспективности применения и развития предлагаемого подхода. Укажем несколько направлений для дальнейшего развития:
1) По видимому, на практике аффинная сводимость задач влечет за собой не просто изоморфизм подграфу, а подобие многогранника сводимой задачи и некоторой грани многогранника ’’более сложной” задачи. Подтверждение этой гипотезы открывает дополни¬тельные возможности для описания фасет многогранников труднорешаемых задач.
2) Следует попытаться показать, по аналогии с классической теорией сводимости, что граф многогранника любой задачи комбинатор¬ной оптимизации изоморфен некоторому подграфу графа многогранника труднорешаемой задачи.
3) Внимательно ознакомившись с доказательствами свойств аффинной сводимости в разделе 2.2 ’’Аффинная сводимость задач”, можно заметить, что для корректной работы доказанных утверждений условие аффинности отображения исходных данных не является необходимым и достаточно потребовать, чтобы отображение было непрерывным. Это замечание говорит об универсальности подхода.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
