Содержание к диссертации
Введение
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 —> і?, ставящая в соответствие каждому элементу х множества X некоторое число с(х). Требуется найти такой элемент ж* Є X, на котором данная функция принимает максимальное (или минимальное) значение, то есть для всех х Є X выполнено с(ж*) > с(х) (или с(ж*) < с(х)).
Среди множества всех задач дискретной оптимизации особо выделяются задачи комбинаторной оптимизации. Их отличие проявляется в комбинаторном характере множества X. Следуя совету И. Ньютона "при изучении наук примеры полезнее правил", рассмотрим классический пример — задачу о кратчайшем пути. Наиболее простая ее формулировка выглядит так. Дано: множество из п городов, среди которых выделены два, и расстояния между городами. Требуется найти кратчайший путь между выделенными городами. (Предполагается, что кратчайший путь может проходить через несколько городов.) В этой задаче X — это множество всех возможных маршрутов. Комбинаторный характер множества X проявляется, в частности, в экспоненциальном росте числа \Х\ всех допустимых решений при росте размерности задачи. Так,
ВВЕДЕНИЕ
для задачи о кратчайшем пути
га-2
\Х\ = (п — 2)! ^ ^у, или, приближенно,
к=0
(п - 2)! < |Х| < е(п - 2)!, где е = 2, 71828 ...
И уже для 20 городов число анализируемых маршрутов превышает 1016. Именно поэтому особое значение имеет проблема поиска алгоритмов, существенно более эффективных, чем полный перебор вариантов. К сожалению, число известных эффективных алгоритмов можно пересчитать по пальцам. В частности, для решения рассматриваемой задачи при естественном предположении о неотрицательности расстояний между городами можно воспользоваться алгоритмом Мура-Дейкстры [33, 52], или алгоритмом Флойда-Уоршелла [33], каждый из которых имеет полиномиальную трудоемкость. В то же время для большинства известных задач комбинаторной оптимизации эффективные алгоритмы до сих пор не найдены. Примером труднорешаемои задачи может служить все та же задача о кратчайшем пути, в которой расстояния могут принимать отрицательные значения. (Такая задача возникает, если под расстояниями понимать средства, затрачиваемые на передвижение, и предполагать, что передвижение из одного города в другой может быть прибыльным.) Приведенный пример позволяет оценить, насколько порой бывает трудно определить, является ли данная задача труднорешаемои, или же для нее можно построить эффективный алгоритм. Одним из аспектов этой проблемы является вопрос о том, какие свойства той или иной задачи характеризуют ее как труднорешаемую. К настоящему времени сформировались два подхода к поиску ответов на этот вопрос.
Первый (в хронологическом порядке) подход основан на теории эффективной (полиномиальной) сводимости задач распознавания свойств, развитой в работах С. Кука, Р. Карпа, Л. Левина (см. монографию Гэри и Джонсона [13]). Эта теория применима в первую очередь для класса NP всех переборных задач. В их число входят, в частности, и такие
ВВЕДЕНИЕ
задачи распознавания, которые можно сформулировать как "упрощенный" вариант задач комбинаторной оптимизации. А именно, в условие задачи оптимизации вводится некоторое, наперед заданное число С, а цель задачи распознавания заключается в ответе на вопрос: верно ли, что найдется такой элемент х Є X, для которого с(х) > С (или с(х) < С для задачи на минимум). Основным достижением этой теории стало открытие Куком [22] так называемых iVP-полных задач, которые в определенном смысле являются самыми сложными в классе NP. Примером здесь может служить задача о кратчайшем пути в варианте распознавания, при условии, что расстояния между городами могут принимать и отрицательные значения: Существует ли такой путь между двумя выделенными городами, длина которого не превышала бы заданного числа С? В результате многочисленных безуспешных попыток поиска эффективных алгоритмов решения таких задач сформировалась гипотеза об их труднорешаемости. И, согласно этой гипотезе, любую задачу, частным случаем которой является iVP-полная, принято считать трудноре-шаемой. Соответственно, если удается показать, что некоторая задача распознавания, допускающая указанную выше формулировку, является труднорешаемой, то и соответствующая оптимизационная задача признается труднорешаемой. В заключение отметим, что список задач, труднорешаемость которых доказана, постоянно пополняется и в настоящее время содержит тысячи задач.
Другой подход к решению поставленной проблемы основан на изучении комбинаторно-геометрических свойств задач и геометрической интерпретации алгоритмов. Первые исследования (см. напр. работу Гей-ла [10]) в этом направлении основаны на представлении множества X допустимых решений как множества точек в вещественном евклидовом пространстве Rm и на предположении, которое обычно выполнено, что функция цели с(х) является линейной: с(х) = (с, ж), где с Є Rm. Такая интерпретация позволяет ввести понятие многогранника М(Х) задачи X,
ВВЕДЕНИЕ
представляющего собой выпуклую оболочку 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).
Так, с возникновением нового понятия аффинной сводимости задач комбинаторной оптимизации появляется и новый подход к изучению сложности задач. По сути своей он похож на классическую теорию сводимости, но, естественно, имеет ряд существенных отличий. Во-первых, новый подход предназначен для изучения задач комбинаторной оптимизации с линейной целевой функцией. Тогда как классическая теория
ВВЕДЕНИЕ
работает прежде всего с задачами распознавания. Во-вторых, оказывается, что при сведении задач комбинаторной оптимизации крайне трудно нарушить свойство аффинности при преобразовании вектора исходных данных одной задачи в вектор исходных данных другой задачи. Таким образом аффиная сводимость для таких задач наиболее естественна. Третье отличие заключается в понятии сложности. Классическая теория, говоря упрощенно, делит задачи по сложности на три класса: труд-норешаемые, полиномиально разрешимые, и задачи, принадлежность которых к этим двум классам не установлена. В новом подходе сложность задачи можно оценить числом. В частности, плотностью графа ее многогранника. Четвертое, объединяющее свойство: В основе нового подхода, как и в основе классической теории лежит доказательство труд-норешаемости одной определенной задачи. В классической теории это задача ВЫПОЛНИМОСТЬ, а в настоящей работе исследование сложности труднорешаемых задач начинается с непосредственного изучения графа многогранника задачи КЛИКА.
Охарактеризовав основную идею работы, перейдем к описанию ее содержания по главам.
В первой главе более подробно изложены основы как классической теории сводимости задач, так и геометрического подхода к изучению их сложности. Описано состояние проблемы в настоящий момент. Содержится краткий обзор уже известных результатов, которые в той или иной степени используются далее.
Вторая глава посвящена изложению оригинальной методики решения поставленной задачи. В ней содержатся подробные доказательства теоретической основы дальнейших исследований. Вводятся понятия конусного и многогранного разбиения, и понятие аффинной сводимости задач комбинаторной оптимизации.
В третьей, наиболее емкой главе приводятся многочисленные "экспериментальные данные", подтверждающие работоспособность предла-
ВВЕДЕНИЕ
гаемой теории. Глава начинается с непосредственного изучения свойств многогранника "основной" задачи — оптимизационной задачи КЛИКА. Доказывается, что плотность графа этого многогранника совпадает с числом вершин и равна 2", где п — размерность задачи.
Дальнейшее развитие теории аффинной сводимости происходит по классическому сценарию. Конструируется алгоритм сведения "первой" задачи к "еще не изученной" задаче и доказывается, что он удовлетворяет условиям аффинности. Таким образом пополняется список задач с экспоненциальной плотностью полиэдрального графа. Процесс пополнения этого списка существенно облегчается за счет схожести оптимизационных задач и задач распознавания. Это позволяет при конструировании алгоритмов сведения оптимизационных задач пользоваться идеями алгоритмов сведения задач распознавания, известными из классической теории [13]. Тем не менее, некоторые алгоритмы аффинной сводимости в настоящей работе предложены впервые.
Структуру этой главы удобно изобразить в виде ориентированного дерева (см. рис. 1). Каждая стрелка на рисунке символизирует алгоритм, сводящий задачу, расположенную в начале стрелки, к задаче, находящейся в конце. В корне дерева расположена "основная" задача КЛИКА. В список исследуемых задач в первую очередь вошли наиболее известные классические задачи. В их числе оптимизационные варианты пяти из шести задач, фигурирующих в [13] как основные iVP-полные задачи.
В четвертой главе изучаются комбинаторно-геометричекие свойства полиномиально разрешимых задач: задачи о кратчайшем пути, задачи о назначениях и задачи о паросочетаниях в произвольном графе. Для графа конусного разбиения задачи о кратчайшем пути значение плотности вычисляется непосредственно. Далее показывается, что эта задача аффинно сводится к задаче о назначениях, что позволяет оценить снизу плотность графа многогранника последней задачи и задачи о паросочетаниях.
ВВЕДЕНИЕ
КЛИКА,
ВЕРШИННОЕ ПОКРЫТИЕ,
НЕЗАВИСИМОЕ МНОЖЕСТВО
2-ВЫПОЛНИМОСТЬ
РАЗРЕЗ
3-СОЧЕТАНИЕ
КОММИВОЯЖЕР
РЮКЗАК, РАЗБИЕНИЕ
ДЛИННЕЙШИЙ ПУТЬ
Рис. 1. Диаграмма сведения труднорешаемых задач.
Как видим, список исследуемых в работе задач достаточно представителен для того, чтобы подтвердить работоспособность предлагаемого подхода. Таким образом, полученные результаты позволяют существенно облегчить изучение свойств графов многогранников задач и открывают новые перспективы для исследований. И, наконец, в заключении подводятся итоги диссертационного исследования, проводится сравнительный анализ с уже известными результатами, формулируются несколько интересных гипотез, требующих для своего решения более внимательного изучения феномена аффинной сводимости.
1. Понятие сложности
в комбинаторной оптимизации
1.1. Некоторые сведения из теории сводимости задач
Для создания целостного представления о развитии и современном состоянии исследуемой проблемы перечислим в хронологическом порядке наиболее интересные и важные результаты, достигнутые ранее.
Начало бурного развития теории сложности задач и алгоритмов прежде всего связано с появлением ЭВМ. Эта связь обусловлена тем, что "в ручную" удается решить только задачи небольшой размерности и современные ассимптотические оценки сложности для таких ситуаций оказываются слишком приближенными. Итак, при решении задач с помощью ЭВМ сформировалось следующее понятие "хорошего" алгоритма: его трудоемкость (максимальное число операций, необходимое для решения задачи) не должна превосходить некоторого полинома от размерности исходных данных задачи. Соответственно, алгоритмы с экспоненциальной от длины входа трудоемкостью принято считать "плохими". Оказалось, что далеко не для всех задач удается построить эффективные алгоритмы. И, естественно, возникла проблема поиска причин труднорешаемости некоторых задач.
Наиболее простым объектом для изучения этой проблемы оказались задачи из класса NP. Классическим примером такой задачи служит знаменитая задача коммивояжера (КОММИВОЯЖЕР). В ней рассматривается полный реберно взвешенный граф G(V,E), где V = {г>і,г>2, ,vn} — множество вершин, Е = = (vi,Vj) : 1 < г < j < п} — множество ребер. На множестве ребер задана функция длин с : Е —> і?, приписывающая каждому ребру е^- Є Е длину с^- = с(е^) Є R. Назовем гамилътоновым цикл, проходящий через каждую вершину графа ровно
Многогранники задач
Проиллюстрируем основные идеи геометрического подхода к исследованию сложности задач на примере задачи коммивояжера. Пусть, как и прежде, G(V, Е) — полный реберно взвешенный граф на п вершинах, в котором требуется найти гамильтонов цикл максимальной длины. Рассмотрим множество Хп всех гамильтоновых циклов в этом графе. Это множество еще называют множеством допустимых решений задачи. Построение ассоциированных с задачей геометрических конструкций прежде всего основано на интерпретации множества Хп как множества точек в евклидовом пространстве Rm. Для задачи коммивояжера положим и каждому ребру е - Є Е поставим в соответствие координату ж - произвольной точки ж = (xij) Є Rm. Теперь для каждого цикла ж Є Хп рассмотрим его характеристический вектор х = (ж ) Є Rm: Обозначим через Хп множество всех таких векторов. Тогда задача коммивояжера с вектором с длин ребер преобразуется в задачу максимизации на множестве Хп линейной функции (скалярного произведения): Отметим здесь важное обстоятельство. Под термином "задача коммивояжера" подразумевается массовая задача, или совокупность индивидуальных задач. Далее индивидуальной задачей с вектором с исходных данных и фиксированной размерностью п будем называть задачу оптимизации на множестве Хп линейной функции (с, ж). Обозначение: индивидуальная задача [Хп,с]. Массовой задачей Хп назовем совокупность всех индивидуальных задач с фиксированным п и произвольным с. Первой, и наиболее известной геометрической конструкцией, основанной на такой интерпретации, является выпуклая оболочка, натянутая на множество X = Хп, которую принято называть многогранником задачи: М(Х) = convX. Дальнейшие исследования многогранников можно условно разбить на два направления. С одной стороны, понятие многогранника позволяет задачу комбинаторной оптимизации (ЗКО) сформулировать как задачу линейного программирования (смотри, например, монографию Емеличева, Ковалева и Кравцова [15]). Это обстоятельство, благодаря открытию в конце 70-х гг. Хачияном [36] (а позднее Кармаркаром [56]) полиномиального алгоритма решения задач линейного программирования (ЗЛП), вселило надежду на отыскание эффективного алгоритма и для решения трудноре-шаемых задач комбинаторной оптимизации.
К сожалению, несмотря на многочисленные попытки, описать множество всех гиперграней (фасет) многогранника какой бы то ни было труднорешаемой задачи в общем виде до сих пор никому не удалось. Кроме того, Карпу и Пападими-триу [57] удалось показать, что проблема полного описания всех фасет многогранника труднорешаемой задачи сама по себе является трудно-решаемой. Тем не менее, это направление имеет ряд интересных перспектив и в настоящее время активно развивается (см., например, работы [12,14,17,38,46,59,60,65]. Выявляются все новые и новые семейства линейных ограничений, описывающие гипергани многогранников труд-норешаемых задач. Отметим в связи с этим любопытный факт, упомянутый в монографии Деза и Лоран [14]. По-видимому, феномен возрастания сложности структуры граней при росте размерности задачи является общим для многогранников труднорешаемых задач. Так, многогранник симметричной задачи коммивояжера для п = 9 городов содержит 42104 442 фасеты и более чем 51043 900 866 фасет для п = 10 (см. работу Кристофа и Райнельта [47]). Другое направление прежде всего связано с исследованием комбина торных свойств графа многогранника и использованием их как характеристик сложности соответствующей задачи в определенном классе алгоритмов. Отметим в этой связи ряд работ [9,15,25,37,66,67]. Формальное описание графа многогранника начнем с определения вершины. Точка х Є М(Х) называется вершиной многогранника М(Х), если найдется вектор с Є Rm такой, что для любого у Є М(Х), отличного от ж, выполнено (с, ж) (с, у). Или, другими словами, х является единственным оптимальным решением для индивидуальной задачи [X, с]. Из определения следует, что множество вершин ext М(Х) многогранника М(Х) является подмножеством множества X: ext М(Х) С І. В дальнейшем будем предполагать, что для каждого допустимого решения х Є X найдется вектор исходных данных с Є Rm такой, что это решение является единственным оптимальным для индивидуальной задачи [X, с]. В противном случае, не уменьшая общности, такое решение х можно исключить из множества допустимых решений. Отметим, что это естественное предположение выполнено для всех исследуемых ниже задач. Это означает, в частности, что множество X совпадает с множеством вершин многогранника задачи: Смежность вершин такого многогранника можно определить следующим образом. Две вершины х,у Є X называются смежными (соединенными ребром), если найдется такой вектор с Є -Rm, для которого индивидуальная задача [X, с] имеет ровно два оптимальных решения х и у, или, другими словами, для каждого z Є X \ {х,у} выполнено (ж, с) = (у, с) (z,c).
Соответственно, граф G{X) многогранника М(Х) состоит из множества вершин и ребер многогранника. Алгоритмические свойства задач обычно описываются в терминах таких характеристик графов многогранников как степени вершин, диаметр, высота графа и т. д. Но все перечисленные характеристики об наруживают свою несостоятельность при попытке использования их в качестве характеристики сложности задач. На настоящий момент, по-видимому, известна только одна приемлемая характеристика сложности такого рода. Это плотность графа, или максимальное число его вершин, любые две из которых смежны. В монографии Бондаренко [9] показано, что плотность графа многогранника является нижней оценкой сложности соответствующей задачи в широком классе алгоритмов прямого типа, использующих линейные сравнения. К этому классу относятся такие классические комбинаторные алгоритмы, как "жадный" алгоритм, алгоритмы сортировки, варианты метода ветвей и границ, метод локального поиска, метод динамического программирования, венгерский метод и многие другие широко известные методы комбинаторной оптимизации. Кроме того, были исследованы (см. [9]) графы многогранников следующих труднорешаемых о кубическом подграфе. И для всех этих задач удалось получить экспоненциальные нижние оценки плотности графов многогранников. В то же время, для многогранников таких полиномиально разрешимых задач, как задачи сортировки, задачи о паросочета-ниях и задача о минимальном остовном дереве были получены [1,2,5,7,8] полиномиальные верхние оценки плотности графов. Разумеется, класс алгоритмов прямого типа не охватывает множество всех "естественных" алгоритмов. В качестве примера [9] можно рассмотреть задачу максимизации многочлена P(t) = с\Ь+с\12 + с? + с на множестве точек Т = {ti, 2? ж}5 гЛе h t i /v- Нетрудно сконструировать алгоритм, решающий эту задачу за время 0(log2 N). С другой стороны, многогранник этой задачи, вершинами которого служат точки Х{ = (ti,t ,tj,tj) Є і?45 і = 1,2,..., iV, принадлежит клас
Аффинная сводимость
Понятие аффинной сводимости появилось благодаря следующим, не противоречащим здравому смыслу, общим свойствам алгоритмов сведения задач комбинаторной оптимизации. Прежде всего заметим, что построение алгоритма сведения массовой задачи У С Rm комбинаторной оптимизации к задаче У С Rn предполагает определение правила, по которому каждой индивидуальной задаче [У, с] ставится в соответствие индивидуальная задача [У, 6]. Учитывая, что на входе алгоритма произвольным является только вектор с исходных данных, приходим к выводу о том, что алгоритм задает некоторое преобразование А, действующее из множества Rm исходных данных первой задачи в множество Rn исходных данных второй задачи. Кроме того, указанный алгоритм, как правило, для каждого допустимого решения ж Є У подбирает его "двойника" у Є У таким образом, чтобы выполнялось следующее условие: Для любого с Є -Rm, произвольно взятый ж Є У является решением индивидуальной задачи [У, с] тогда и только тогда, когда его "двойник" у Є У является решением задачи [У, 6], где Ь = А(с). Ниже правило, по которому подбирается "двойник" для произвольного ж Є У, будем обозначать В : У — У. Предполагая эти свойства выполненными, далее аффинным будем называть такой алгоритм сведения, для которого преобразование А аффинно. Определение. Будем говорить, что задача (У, S) для многогранного множества исходных данных S С Rm аффинно сводится к задаче У = (У, Rn), где т п, если найдутся 1) невырожденное аффинное отображение A : S — Г, действующее взаимно-однозначно из S в некоторое многогранное множество Т С Rn (В данном случае аффинное отображение можно задать формулой = A(s) = Ks + d, где Є Г, s Є 5, d Є Rn и К — матрица размера n х т, причем rang К = ш), 2) и взаимно-однозначное соответствие В : X — У между множеством X и некоторым подмножеством У С У такие, что для каждого вектора s Є S выполнено следующее условие: ?/о является решением задачи [У, A(s)], тогда и только тогда, (5) когда /о Є У и XQ = В 1(уо) — решение задачи [X, s]. Для таких задач введем обозначение: (X, 5) ос У.
Перечислим свойства аффинной сводимости. Свойство 2.7. Множество Т из определения аффинной сводимости аффинно подобно многогранному множеству S. Это следует из невырожденности отображения А. Свойство 2.8. Для любого х Є X и у = В(х) Є У полиэдры K(x,S) и К(у,Т) тоже аффинно подобны. Обозначаем K(x,S) К(В(х),Т). Это свойство вытекает из невырожденности аффинного отображения А и условия (5). Свойство 2.9. Грань вида K(xi,S)C\K(x2,S), гдех\ х Є X, аффинное отображение А переводит в подобную грань К(уі,Т) ПК(у2,Т), где ух = В(х{), /2 = В(х2). і і Свойство 2.10. Р K(x{,S) П К(уі,Т), где Х{ Є X, уі = В{х{), для г=1 г=1 1 і /. Это свойство является естественным обобщением предыдущих трех свойств. Теперь, опираясь на указанные свойства, сформулируем ряд утверждений. Теорема 2.11. Пусть (X,S) ОСА У и A : S — Т , тогда Gs(X) = GT{Y) G{Y). Справедливость этой теоремы следует из свойств 2.8 и 2.9. А пользуясь теоремой 2.6 получаем Следствие 2.12. Пусть (X,Qm) ОСА Y, тогда G(X) G(Y). Следствие 2.13. Пусть (X,Qm) ОСА Y, тогда р{Х) p(Y), где р() - плотность графа соответствующего многогранника. Чтобы пояснить, как будут использоваться только что доказанные утверждения в дальнейшем, приведем простой пример. Покажем, что задача коммивояжера (ЗК) аффинно сводится к задаче о длиннейшем пути (ЗДП). Для этого воспользуемся алгоритмом сведения этих задач, подробно изложенном при доказательстве теоремы 1.2. С целью облегчения дальнейшего изложения введем специальные обозначения. Множества допустимых решений задач будем обозначать большими каллиграфическими буквами. Пусть 1їп — множество гамильтоновых циклов в графе G на п вершинах (обозначение происходит от первой буквы английского названия задачи: Hamilton s circuit).
Теперь, воспользовавшись формулой (3) (см. стр. 18), определим множество X = 1їп характеристических векторов указанных гамильтоновых циклов. Далее именно 1їп и будем называть множеством допустимых решений задачи гамильтонов цикл (симметричной задачи коммивояжера). Как было сказано выше (см. уравнение (2)), X = HneRm,m = fii. Для ЗДП, как и ранее, рассмотрим граф G на п + 1 вершинах. Пусть Cn+i — множество всех простых путей без циклов в графе С, ведущих из вершины s = v i в вершину t = v n+1 (обозначение множества происходит от английского Longest path). Множество Y = n+i характеристических векторов указанных путей определим по аналогии с задачей коммивояжера. Точка у = (yij) Є Rm+n где 1 і j n + 1, принадлежит множеству У, если и только если найдется такой путь у Є Сп+і, что Вспомним, что доказательство теоремы 1.2 разбито на два этапа. На первом этапе общая ЗК сводится к своему "частному" случаю (X,Q), когда множество исходных данных представляет собой куб Q = Qm, где т = " з . Надо сказать, что этот этап "сжатия множества исходных данных" довольно часто приходится использовать явно или не явно при
Задача трехмерное сочетание
В этой главе рассматривается многогранник известной задачи ТРЕХМЕРНОЕ СОЧЕТАНИЕ, или 3-С, которая включена в [13] в число основных iVP-полных задач. В оптимизационном варианте эта задача известна под названием "трехиндексная задача назначений" [18] благодаря аналогии с классической задачей о назначениях. Приведем следующий вариант формулировки этой задачи. Рассматривается трехдольный граф G3 = G (U, V, W, Е), множество вершин которого разбито на три равные по количеству вершин доли U, V и W, где \U\ = \V\ = \W\ = т [Е — множество ребер графа G3, которое мы опишем чуть ниже). Обозначим вершины в этих множествах следующим образом: Трехмерным ребром, или 3-ребром такого графа будем называть тройку вершин eiji = (ui,Vj,wi), содержащую по одной вершине из каждой доли. Множество всех таких 3-ребер графа G3 обозначим через Е. Будем говорить, что вершины щ, Vj и wi инцидентны 3-ребру (щ, Vj, wi). И, наоборот, ребро (iii,Vj,wi) инцидентно входящим в него вершинам. Каждому 3-ребру графа G3 приписан вес 6 -/ = b(e{ji) Є R. Рассмотрим такой набор 3-ребер х С Е, что каждая вершина графа инцидентна ровно одному 3-ребру из этого набора. Набор 3-ребер ж, удовлетворяющий этому условию, называется трехмерным сочетанием, или 3-сочетанием. Очевидно, что каждое 3-сочетание содержит ровно т 3-ребер. Обозначим множество всех 3-сочетаний графа G3 через Тт. (От первой буквы английского названия задачи: Three-Matching). Задача об оптимальном трехмерном сочетании заключается в отыскании такого 3-сочетания жТш, суммарный вес ребер которого был бы максимален. Многогранник этой задачи определим в соответствии с монографией [9]. Рассмотрим пространство Rk, где к = т3, координаты произ вольной точки х = (xiji) Є Rk в котором интерпретируются как ячейки кубической m х m х m-матрицы. Каждому 3-сочетанию х поставим в соответствие точку х Є Rk, координаты которой определим следующим образом: множество Тт всех таких точек. Индивидуальная задача [Тт,Ь] с вектором Ъ = (6jj/) Є -Rfc исходных данных состоит в отыскании точки х Є 7 і, максимизирующей скалярное произведение (ж, 6).
Известно [9], что плотность р(Тт) графа многогранника М(Тт) оценивается снизу экспоненциальной величиной: Ниже будет описан алгоритм сведения оптимизационной задачи КЛИКА к оптимизационной задаче 3-С, позволяющий установить более высокую оценку плотности. Конструкция этого алгоритма основана на идее, почерпнутой из монографии [9]. Пусть (Сп, Q) — задача КЛИКА для графа на п вершинах, множество исходных Теорема 3.7. Задача КЛИКА (Cn,Q) аффинно сводится к задаче трехмерное сочетание 1 т, где т = - —-: Доказательство. Введем новые обозначения вершин трехдольного rpa()aG3( 7,V,W,): 3. ТРУДНОРЕШАЕМЫЕ ЗАДА ЧИ Для каждой вершины м - (1 г j п) зададим множество Dij инцидентных к ней 3-ребер следующим образом: 1) которые в дальнейшем будем обозначать а и а\{ соответственно. Обозначим множество всех таких 3-ребер через D = (J D . l i j n Пусть с = (cij) Є Rm — вектор исходных данных для задачи КЛИКА. По прежнему, сц — вес г -ой вершины, а с - — вес ребра, соединяющего і-ю и j-ю вершины; причем по условию — 1 с - 1. Тогда 3-ребрам а\-припишем веса с - с теми-же индексами: Веса остальных 3-ребер из множества D обнулим: А остальным 3-ребрам из множества Е\ D припишем большие по абсолютному значению отрицательные веса: Величина — п2 гарантирует, что в максимальное 3-сочетание будут входить только ребра из описанного выше множества D. Учитывая, что в 3-сочетание не могут входить 3-ребра инцидентные одной и той-же вершине, несложно сделать вывод о том, что в максимальное 3-сочетание обязательно войдет ровно одно из двух 3-ребер инцидентных вершине иц: а ., или а\{. Будем называть такие 3-ребра, для 1 г п, "выбирающими 3-ребрами". Покажем, что максимальное 3-сочетание в описанном графе Сг3 однозначно задается набором входящих в него выбирающих 3-ребер. Лемма 3.8. Пусть жЕТш — максимальное 3-сочетание в графе G , тогда справедливы следующие утверждения: Доказательство. Докажем справедливость первого утверждения. Предположим, что в максимальное 3-сочетание входит 3-ребро а\-. Заметим, что это 3-ребро инцидентно вершине Wij_\. Теперь воспользуемся тем, что в 3-сочетание не могут входить разные 3-ребра инцидентные одной и той же вершине. Рассмотрим 3-ребро, входящее в максимальное 3-сочетание и инцидентное вершине uij_\. Очевидно, оно входит в Dij_i и не может быть инцидентно вершине Wij_\. Методом исключения находим, что это либо 3-ребро а\-ъ либо а \-х. Далее, учитывая, что оба этих 3-ребра инцидентны вершине « --2, в результате аналогичных рассуждений получаем, что в максимальное 3-сочетание входит одно из двух 3-ребер: либо а\-_ либо af-2. Действуя далее по индукции получаем, что 3-ребро, инцидентное вершине иц, не может быть инцидентно вершине иоц. Но в множество Da входит только одно 3-ребро с таким свойством, это а\{. Итак, в максимальное 3-сочетание входит ребро а\{. Для того, чтобы показать, что и а у"- входит в максимальное 3-сочетание, заметим, что 3-ребро а\- инцидентно вершине vi+\j. Но тогда 3-ребро, входящее в максимальное 3-сочетание и инцидентное вершине Wi+ij, является одним из двух 3-ребер: либо а+1 , либо af+1-. Действуя
Задача коммивояжера с условием "неравенство треугольника"
В этом пункте изучаются комбинаторно-геометрические свойства конусного разбиения для задачи ГЦ с часто встречающимся на практике дополнительным ограничением, накладываемым на множество исходных данных задачи. Это условие носит название неравенства треугольника и заключается в следующем. Для каждой тройки различных вершин Vi,Vj,vi Є V графа G(V,E) задачи ГЦ требуется выполнение условия: где bij = Ь(еу), как и раньше, — длина ребра, соединяющего вершины Vi и Vj. Очевидно, что множество всех целевых векторов b = (bij) Є -Rm, n(n—l) m = -4 —-, удовлетворяющих описанной системе линейных неравенств, представляет собой многогранный конус с вершиной в начале координат. Обозначим этот конус А. Т. о. исследуемая задача есть задача (1їп,А). Теорема 3.21. Задача гамилътпонов цикл, длины дуг в которой выбираются из отрезка [—1,1], аффинно сводится к задаче коммивояжера с "неравенством треугольника": (l-in,Q) ос (Н„,А). Доказательство. Пусть с = () Є Rm — вектор длин ребер для задачи (l-i,Q). Соответственно, —1 с - 1. Определим теперь аффинное отображение А, связывающее вектор с с вектором Ь = (6 -) Є Rm исходных данных задачи (1-і, А). Прежде всего заметим, что в результате такого преобразования выбор оптимального решения задачи не изменится, так как длина каждого га-мильтонова цикла в "новом" графе лишь увеличится на Зп. Теперь воспользуемся тем, что 2 Ь 4. Это означает, что для любой тройки различных чисел i,j,l Є {1,2,...,п} выполнено условие (28). Таким образом, указанное аффинное отображение равномерно по всем координатным осям сдвигает куб Q так, чтобы он оказался полностью внутри множества А. Теорема доказана. Следствие 3.22. Граф G{Hn) многогранника задачи гамилътпонов цикл в точности совпадает с графом G (l-in) конусного разбиения задачи коммивояжера с условием "неравенство треугольника". Как уже было сказано, для единообразия изложения все обсуждаемые в данной работе задачи рассматриваются в варианте максимизации. Именно с этой целью в этом разделе исследуются свойства задачи о длиннейшем пути, а не ее более знаменитого "двойника" — задачи о кратчайшем пути для произвольных длин ребер (дуг). Дело в том, что множество допустимых решений для обеих задач одно и то же, следовательно, многогранники этих задач идентичны. Известно, что задача о длиннейшем пути может быть сформулирована как для ориентированного, так и для неориентированного графа. Далее первую задачу будем называть задачей о длиннейшем пути (ДП), а вторую — задачей о длиннейшей цепи (ДЦ). В разделе 2.2 "Аффинная сводимость задач" в качестве примера было показано, что задача коммивояжера (l-in,Q) аффинно сводится к задаче о длиннейшей цепи Сп+\. Таким образом, для вычисления нижней оценки плотности графа многогранника M(Cn+i) остается лишь воспользоваться оценкой (27) плотности графа многогранника М{Нп) для задачи гамильтонов цикл. Следствие 3.23.
Плотность полиэдрального графа задачи ДЦ на п вершинах экспоненциальна: Теперь сформулируем задачу о длиннейшем пути в ориентированном графе и определим ее многогранник. Рассмотрим полный ориентированный граф G(V, А), где V = {г і, г 2,... , vn}, две вершины которого выделены, для определенности будем считать, что это v\ и vn. Обозначим через С п множество всех простых путей без циклов, начинающихся в вершине v\ и заканчивающихся в vn. Каждый такой путь не содержит ни одной дуги, входящей в v\ и ни одной дуги, выходящей из vn. Исключим из рассмотрения указанные дуги и будем считать, что \А\ = (п — 1)(п — 2) + 1. Каждой дуге а у, где і Є {1, 2,... , п — 1} и j Є {2, 3,... , п}, приписана некоторая длина Cij Є R. Под длиной пути х Є С п понимается сумма длин составляющих этот путь дуг. Цель задачи состоит в отыскании такого пути х Є С п длина которого максимальна. С целью определения многогранника этой задачи положим т = \А\ и рассмотрим Rm. И, как и прежде, для каждого пути х Є С п рассмотрим его характеристический вектор х = (ж ) Є -Rm, положив Заметим, что упоминавшийся выше алгоритм сведения задачи ГЦ к задаче ДЦ (смотри теорему 1.2) с минимальными изменениями можно использовать для сведения задачи ГК к задаче ДП. В связи с этим пред ставляется достаточным привести только окончательные формулировки аналогичных утверждений. Теорема 3.24. Несимметричная задача коммивояжера для п — 1 городов, длины дуг в которой выбираются из отрезка [—1,1], аффинно сводится к задаче длиннейший путь для п городов: (7-l n_i,Q) ос С п. Следствие 3.25. Граф G{H n_i) многогранника задачи гамилътонов контур изоморфен некоторому подграфу графа G(C n) многогранника задачи о длиннейшем пути. И, воспользовавшись оценкой (26), получаем
