Помощь студентам в учебе
Графы многогранников и сводимость задач комбинаторной оптимизации
|
Введение 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
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], каждый из которых имеет полиномиальную трудоемкость. В то же время для большинства известных за¬дач комбинаторной оптимизации эффективные алгоритмы до сих пор не найдены. Примером труднорешаемой задачи может служить все та же задача о кратчайшем пути, в которой расстояния могут принимать отрицательные значения. (Такая задача возникает, если под расстояниями понимать средства, затрачиваемые на передвижение, и предполагать, что передвижение из одного города в другой может быть прибыльным.) Приведенный пример позволяет оценить, насколько порой бывает трудно определить, является ли данная задача труднорешаемой, или же для нее можно построить эффективный алгоритм. Одним из аспектов этой проблемы является вопрос о том, какие свойства той или иной задачи характеризуют ее как труднорешаемую. К настоящему времени сформировались два подхода к поиску ответов на этот вопрос.
Первый (в хронологическом порядке) подход основан на теории эффективной (полиномиальной) сводимости задач распознавания свойств, развитой в работах С. Кука, Р. Карпа, JI. Левина (см. монографию Гэри и Джонсона [13]). Эта теория применима в первую очередь для класса NP всех переборных задач. В их число входят, в частности, и такие задачи распознавания, которые можно сформулировать как ”упрощенный” вариант задач комбинаторной оптимизации. А именно, в условие задачи оптимизации вводится некоторое, наперед заданное число С, а цель задачи распознавания заключается в ответе на вопрос: верно ли, что найдется такой элемент х Е X, для которого с(х) > С (или с(х) < С для задачи на минимум). Основным достижением этой теории стало открытие Куком [22] так называемых iVP-полных задач, которые в определенном смысле являются самыми сложными в классе NP. Примером здесь может служить задача о кратчайшем пути в варианте распознавания, при условии, что расстояния между городами могут принимать и отрицательные значения: Существует ли такой путь между двумя вы¬деленными городами, длина которого не превышала бы заданного числа С? В результате многочисленных безуспешных попыток поиска эффективных алгоритмов решения таких задач сформировалась гипотеза об их труднорешаемости. И, согласно этой гипотезе, любую задачу, частным случаем которой является iVP-полная, принято считать труднорешаемой. Соответственно, если удается показать, что некоторая задача распознавания, допускающая указанную выше формулировку, является труднорешаемой, то и соответствующая оптимизационная задача признается труднорешаемой. В заключение отметим, что список задач, труднорешаемость которых доказана, постоянно пополняется и в настоящее время содержит тысячи задач.
Другой подход к решению поставленной проблемы основан на изучении комбинаторно-геометрических свойств задач и геометрической интерпретации алгоритмов.
Сформулируем условие задачи дискретной оптимизации следующим образом. Задано конечное множество X и функция с : X —>• i?, ставящая в соответствие каждому элементу х множества X некоторое число с(х). Требуется найти такой элемент х* Е X, на котором данная функция принимает максимальное (или минимальное) значение, то есть для всех х G X выполнено с(х*) > с(х) (или с(х*) < с(х)).
Среди множества всех задач дискретной оптимизации особо выделяются задачи комбинаторной оптимизации. Их отличие проявляется в комбинаторном характере множества X. Следуя совету И. Ньютона ”при изучении наук примеры полезнее правил”, рассмотрим классический пример — задачу о кратчайшем пути. Наиболее простая ее формулировка выглядит так. Дано: множество из п городов, среди которых выделены два, и расстояния между городами. Требуется найти кратчайший путь между выделенными городами. (Предполагается, что кратчайший путь может проходить через несколько городов.) В этой задаче X
— это множество всех возможных маршрутов. Комбинаторный характер множества X проявляется, в частности, в экспоненциальном росте числа Х всех допустимых решений при росте размерности задачи. Так, для задачи о кратчайшем пути
п—2
Х = (п — 2)! ^2 или, приближенно,
к=о
(п — 2)! < Х < е(п — 2)!, где е = 2, 71828 ...
И уже для 20 городов число анализируемых маршрутов превышает 1016. Именно поэтому особое значение имеет проблема поиска алгоритмов, существенно более эффективных, чем полный перебор вариантов. К сожалению, число известных эффективных алгоритмов можно пересчитать по пальцам. В частности, для решения рассматриваемой задачи при естественном предположении о неотрицательности расстояний между городами можно воспользоваться алгоритмом МураДейкстры [33, 52], или алгоритмом Флойда-Уоршелла [33], каждый из которых имеет полиномиальную трудоемкость. В то же время для большинства известных за¬дач комбинаторной оптимизации эффективные алгоритмы до сих пор не найдены. Примером труднорешаемой задачи может служить все та же задача о кратчайшем пути, в которой расстояния могут принимать отрицательные значения. (Такая задача возникает, если под расстояниями понимать средства, затрачиваемые на передвижение, и предполагать, что передвижение из одного города в другой может быть прибыльным.) Приведенный пример позволяет оценить, насколько порой бывает трудно определить, является ли данная задача труднорешаемой, или же для нее можно построить эффективный алгоритм. Одним из аспектов этой проблемы является вопрос о том, какие свойства той или иной задачи характеризуют ее как труднорешаемую. К настоящему времени сформировались два подхода к поиску ответов на этот вопрос.
Первый (в хронологическом порядке) подход основан на теории эффективной (полиномиальной) сводимости задач распознавания свойств, развитой в работах С. Кука, Р. Карпа, JI. Левина (см. монографию Гэри и Джонсона [13]). Эта теория применима в первую очередь для класса NP всех переборных задач. В их число входят, в частности, и такие задачи распознавания, которые можно сформулировать как ”упрощенный” вариант задач комбинаторной оптимизации. А именно, в условие задачи оптимизации вводится некоторое, наперед заданное число С, а цель задачи распознавания заключается в ответе на вопрос: верно ли, что найдется такой элемент х Е X, для которого с(х) > С (или с(х) < С для задачи на минимум). Основным достижением этой теории стало открытие Куком [22] так называемых iVP-полных задач, которые в определенном смысле являются самыми сложными в классе NP. Примером здесь может служить задача о кратчайшем пути в варианте распознавания, при условии, что расстояния между городами могут принимать и отрицательные значения: Существует ли такой путь между двумя вы¬деленными городами, длина которого не превышала бы заданного числа С? В результате многочисленных безуспешных попыток поиска эффективных алгоритмов решения таких задач сформировалась гипотеза об их труднорешаемости. И, согласно этой гипотезе, любую задачу, частным случаем которой является iVP-полная, принято считать труднорешаемой. Соответственно, если удается показать, что некоторая задача распознавания, допускающая указанную выше формулировку, является труднорешаемой, то и соответствующая оптимизационная задача признается труднорешаемой. В заключение отметим, что список задач, труднорешаемость которых доказана, постоянно пополняется и в настоящее время содержит тысячи задач.
Другой подход к решению поставленной проблемы основан на изучении комбинаторно-геометрических свойств задач и геометрической интерпретации алгоритмов.
За последние два - три десятилетия накопилось большое число результатов, касающихся свойств многогранников задач комбинаторной оптимизации. Прежде всего это связано с тем, что, как известно, комбинаторно-геометрические свойства многогранника являются характеристиками сложности соответствующей задачи в том или ином классе алгоритмов. К сожалению, многогранник ассоциируется только с общей задачей, в которой отсутствуют какие либо ограничения на множество исходных данных. Тем не менее, изучение на предмет сложности частных случаев задачи нередко представляет гораздо больший интерес. Именно это послужило причиной появления новой геометрической конструкции — многогранного разбиения пространства исходных данных задачи. Эта структура позволяет исследовать комбинаторно-геометрические свойства таких задач, для которых построение многогранника в явном виде невозможно.
Изучение свойств этой конструкции позволило по новому взглянуть на классическую теорию сводимости задач. Оказалось, что при сведении задачи X к задаче Y множество исходных данных первой задачи, как правило, аффинно отображается в множество исходных данных второй задачи. Так появляется новый тип сводимости — аффинная сводимость задач комбинаторной оптимизации. Одним из замечательных свойств которой является то, что если X ос^ У, то многогранное разбиение пространства исходных данных первой задачи аффинно отображается в не-которую часть многогранного разбиения прстранства исходных данных второй задачи. Как следствие, граф G(X) многогранника М(Х) оказывается изоморфным некоторому подграфу графа G(Y) многогранника второй задачи.
Практическая целесообразность введения этого нового типа сводимости задач комбинаторной оптимизации подтверждается описанными в настоящей работе многочисленными экспериментальными данными. Так, на основе классических алгоритмов сведения удалось показать, что наиболее простой для изучения граф многогранника задачи КЛИКА изоморфен графу многогранника задачи максимальная 2- ВЫПОЛНИМОСТЬ и графу многогранника задачи максимальный РАЗ¬РЕЗ. Также упомянутый граф оказывается изоморфным некоторым под¬графам графов многогранников таких труднорешаемых задач как 3- СОЧЕТАИИЕ, РЮКЗАК, КОММИВОЯЖЕР и ДЛИННЕЙШИЙ ПУТЬ. Кроме того, структура конусного разбиения для задачи КЛИКА оказалась изоморфна некоторой части конусного разбиения задачи РАЗБИЕНИЕ и задачи коммивояжера для длин ребер (дуг) которой выполнено условие ”неравенства треугольника”.
Опираясь на доказанное в работе утверждение о том, что граф многогранника задачи КЛИКА является полным, были получены экспоненциальные нижние оценки плотности графов многогранников перечисленных выше задач.
Изучение свойств этой конструкции позволило по новому взглянуть на классическую теорию сводимости задач. Оказалось, что при сведении задачи X к задаче Y множество исходных данных первой задачи, как правило, аффинно отображается в множество исходных данных второй задачи. Так появляется новый тип сводимости — аффинная сводимость задач комбинаторной оптимизации. Одним из замечательных свойств которой является то, что если X ос^ У, то многогранное разбиение пространства исходных данных первой задачи аффинно отображается в не-которую часть многогранного разбиения прстранства исходных данных второй задачи. Как следствие, граф G(X) многогранника М(Х) оказывается изоморфным некоторому подграфу графа G(Y) многогранника второй задачи.
Практическая целесообразность введения этого нового типа сводимости задач комбинаторной оптимизации подтверждается описанными в настоящей работе многочисленными экспериментальными данными. Так, на основе классических алгоритмов сведения удалось показать, что наиболее простой для изучения граф многогранника задачи КЛИКА изоморфен графу многогранника задачи максимальная 2- ВЫПОЛНИМОСТЬ и графу многогранника задачи максимальный РАЗ¬РЕЗ. Также упомянутый граф оказывается изоморфным некоторым под¬графам графов многогранников таких труднорешаемых задач как 3- СОЧЕТАИИЕ, РЮКЗАК, КОММИВОЯЖЕР и ДЛИННЕЙШИЙ ПУТЬ. Кроме того, структура конусного разбиения для задачи КЛИКА оказалась изоморфна некоторой части конусного разбиения задачи РАЗБИЕНИЕ и задачи коммивояжера для длин ребер (дуг) которой выполнено условие ”неравенства треугольника”.
Опираясь на доказанное в работе утверждение о том, что граф многогранника задачи КЛИКА является полным, были получены экспоненциальные нижние оценки плотности графов многогранников перечисленных выше задач.