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

• Автор: Максименко, Александр Николаевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Ярославль
• Количество страниц: 92 с.

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

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

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

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

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

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

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

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

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

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

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

3.5. Задачи РЮКЗАК и РАЗБИЕНИЕ
3.6. Задача КОММИВОЯЖЕР
3.6.1. Задача гамильтонов контур
3.6.2. Задача гамильтонов цикл
3.6.3. Задача коммивояжера
с условием ”неравенство треугольника”
3.7. Задача ДЛИННЕЙШИЙ ПУТЬ
4. Полиномиально разрешимые задачи
4.1. Задача о кратчайшем пути
4.2. Задачи о паросочетаниях
Заключение
Список литературы
Стремление к выбору наиболее выгодной (оптимальной) сделки среди некоторого множества возможных особенно ярко проявляется в условиях рыночной экономики. Видимо поэтому наибольшее внимание задачам дискретной оптимизации уделялось и уделяется именно в странах, поддерживающих развитие свободных рыночных отношений. Благодаря тому, что удельный вес таких стран в современном мире постоянно растет, проблемы эффективного решения вышеназванных задач приобретают все большую актуальность.
Сформулируем условие задачи дискретной оптимизации следующим образом. Задано конечное множество X и функция с : X Л, ставящая в соответствие каждому элементу х множества X некоторое число с(х). Требуется найти такой элемент х* € X, на котором данная функция принимает максимальное (или минимальное) значение, то есть для всех х € X выполнено с(х*) > с(х) (или с(х*) < с(х)).
Среди множества всех задач дискретной оптимизации особо выделяются задачи комбинаторной оптимизации. Их отличие проявляется в комбинаторном характере множества X. Следуя совету И. Ньютона ’’при изучении наук примеры полезнее правил”, рассмотрим классический пример — задачу о кратчайшем пути. Наиболее простая ее формулировка выглядит так. Дано: множество из п городов, среди которых выделены два, и расстояния между городами. Требуется найти кратчайший путь между выделенными городами. (Предполагается, что кратчайший путь может проходить через несколько городов.) В этой задаче X — это множество всех возможных маршрутов. Комбинаторный характер множества X проявляется, в частности, в экспоненциальном росте числа |Х| всех допустимых решений при росте размерности задачи. Так,

для задачи о кратчайшем пути

|Х| = (п — 2)! X) или> приближенно, к—О
(п - 2)! < Х < е(п - 2)!, где е = 2,71828
И уже для 20 городов число анализируемых маршрутов превышает 1016. Именно поэтому особое значение имеет проблема поиска алгоритмов, существенно более эффективных, чем полный перебор вариантов. К сожалению, число известных эффективных алгоритмов можно пересчитать по пальцам. В частности, для решения рассматриваемой задачи при естественном предположении о неотрицательности расстояний между городами можно воспользоваться алгоритмом Мура-Дейкстры [33,52], или алгоритмом Флойда-Уоршелла [33], каждый из которых имеет полиномиальную трудоемкость. В то же время для большинства известных задач комбинаторной оптимизации эффективные алгоритмы до сих пор не найдены. Примером труднорешаемой задачи может служить все та же задача о кратчайшем пути, в которой расстояния могут принимать отрицательные значения. (Такая задача возникает, если под расстояниями понимать средства, затрачиваемые на передвижение, и предполагать, что передвижение из одного города в другой может быть прибыльным.) Приведенный пример позволяет оценить, насколько порой бывает трудно определить, является ли данная задача труднорешаемой, или же для нее можно построить эффективный алгоритм. Одним из аспектов этой проблемы является вопрос о том, какие свойства той или иной задачи характеризуют ее как труднорешаемую. К настоящему времени сформировались два подхода к поиску ответов на этот вопрос.
Первый (в хронологическом порядке) подход основан на теории эффективной (полиномиальной) сводимости задач распознавания свойств, развитой в работах С. Кука, Р. Карпа, Л. Левина (см. монографию Гэри и Джонсона [13]). Эта теория применима в первую очередь для класса Л^Р всех переборных задач. В их число входят, в частности, и такие
3. ТРУДНОРЕШАЕМЫЕ ЗАДАЧИ

ной” задачи трехмерное сочетание (3-С) к задаче РАЗБИЕНИЕ, являющийся одновременно доказательством АЛ-полноты последней. Покажем, как можно модифицировать этот алгоритм для сведения оптимизационной задачи 3-С к оптимизационной задаче РЮКЗАК. С этой целью сформулируем оптимизационную задачу 3-С в более подходящем виде. В пространстве Дга, где т = п3, координаты точек в котором интерпретируются как ячейки кубической пхпхп матрицы, рассмотрим множество Тп всех таких матриц, состоящих из нулей и единиц, в каждой ” плоской” пхп матрице (срезе кубической матрицы) которых ровно один элемент равен единице. Другими словами, для каждого х = (х,д) £ Т„ и для всех i,j,l 6 (1,те) выполнено
п п п п п п
1212х*1=1212 х& =1212 хч‘
(=1 }=х 1=11=1 з=1 ;
Индивидуальная задача Тп,Ъ с матрицей Ь = (Ь;д) £ Дт исходных данных заключается в отыскании среди этих кубических матриц такой матрицы х' 6 Тп, что для всех хеТп выполнено (х',Ь) > (х,Ь).
Теперь рассмотрим задачу о рюкзаке для тп + 2 предметов. Для первых ш координат произвольной точки у £ Дт+2 наряду с традиционным обозначением у* (к = 1,2 ш) будем, по аналогии с задачей 3-С, использовать следующее:
Уч1 = У к, к = (г- 1)п2 + (; - 1)п + /, 6 (1,п).
Обозначение последних двух координат ут+ и ут+2 останется традиционным.
Из семейства многогранников задачи о рюкзаке особо выделим один ’’наиболее сложно устроенный” многогранник. С этой целью определим отделяющую гиперплоскость Н. Потребуем, чтобы эта гиперплоскость проходила через центр единичного куба, то есть положим
-5 = где е = С1,1’...,!). (15)