Бесплатно скачать, заказать диплом, курсовую, диссертацию Графы многогранников и сводимость задач комбинаторной оптимизации

У нас уже 176407 рефератов, курсовых и дипломных работ

Сделать закладку на сайт

Заказать диплом, курсовую, диссертацию

Быстрый переход к готовым работам

Мнение посетителей:

Книга жалоб
и предложений

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

Количество страниц	85

ВУЗ	МГИУ

Год сдачи	2010

Бесплатно Скачать	23541.doc

Содержание	Содержание Оглавление Введение 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 проявляется, в частности, в экспоненциальном росте числа \Х\ всех допустимых решений при росте размерности задачи. Так, ВВЕДЕНИЕ 4 для задачи о кратчайшем пути п-2 Х\ = (п — 2)! ^2 &т? ИЛИ5 приближенно, к=о (п - 2)! < \Х\ < е(п - 2)!, где е = 2, 71828 ... И уже для 20 городов число анализируемых маршрутов превышает 1016. Именно поэтому особое значение имеет проблема поиска алгоритмов, существенно более эффективных, чем полный перебор вариантов. К сожалению, число известных эффективных алгоритмов можно пересчитать по пальцам. В частности, для решения рассматриваемой задачи при естественном предположении о неотрицательности расстояний между городами можно воспользоваться алгоритмом Мура-Дейкстры [33, 52], или алгоритмом Флойда-Уоршелла [33], каждый из которых имеет полиномиальную трудоемкость. В то же время для большинства известных задач комбинаторной оптимизации эффективные алгоритмы до сих пор не найдены. Примером труднорешаемой задачи может служить все та же задача о кратчайшем пути, в которой расстояния могут принимать отрицательные значения. (Такая задача возникает, если под расстояниями понимать средства, затрачиваемые на передвижение, и предполагать, что передвижение из одного города в другой может быть прибыльным.) Приведенный пример позволяет оценить, насколько порой бывает трудно определить, является ли данная задача труднорешаемой, или же для нее можно построить эффективный алгоритм. Одним из аспектов этой проблемы является вопрос о том, какие свойства той или иной задачи характеризуют ее как труднорешаемую. К настоящему времени сформировались два подхода к поиску ответов на этот вопрос. Первый (в хронологическом порядке) подход основан на теории эффективной (полиномиальной) сводимости задач распознавания свойств, развитой в работах С. Кука, Р. Карпа, Л. Левина (см. монографию Гэри и Джонсона [13]). Эта теория применима в первую очередь для класса NP всех переборных задач. В их число входят, в частности, и такие ВВЕДЕНИЕ 5 задачи распознавания, которые можно сформулировать как "упрощенный" вариант задач комбинаторной оптимизации. А именно, в условие задачи оптимизации вводится некоторое, наперед заданное число С, а цель задачи распознавания заключается в ответе на вопрос: верно ли, что найдется такой элемент iGl, для которого с(х) > С (или с(х) < С для задачи на минимум). Основным достижением этой теории стало открытие Куком [22] так называемых iVP-полных задач, которые в определенном смысле являются самыми сложными в классе NP. Примером здесь может служить задача о кратчайшем пути в варианте распознавания, при условии, что расстояния между городами могут принимать и отрицательные значения: Существует ли такой путь между двумя выделенными городами, длина которого не превышала бы заданного числа С? В результате многочисленных безуспешных попыток поиска эффективных алгоритмов решения таких задач сформировалась гипотеза об их труднорешаемости. И, согласно этой гипотезе, любую задачу, частным случаем которой является iVP-полная, принято считать трудноре-шаемой. Соответственно, если удается показать, что некоторая задача распознавания, допускающая указанную выше формулировку, является труднорешаемой, то и соответствующая оптимизационная задача признается труднорешаемой. В заключение отметим, что список задач, труднорешаемость которых доказана, постоянно пополняется и в настоящее время содержит тысячи задач. Другой подход к решению поставленной проблемы основан на изучении комбинаторно-геометрических свойств задач и геометрической интерпретации алгоритмов. Первые исследования (см. напр, работу Гей-ла [10]) в этом направлении основаны на представлении множества X допустимых решений как множества точек в вещественном евклидовом пространстве Rm и на предположении, которое обычно выполнено, что функция цели с(х) является линейной: с(х) = (с, ж), где с Е Rm¦ Такая интерпретация позволяет ввести понятие многогранника М{Х) задачи X, ВВЕДЕНИЕ 6 представляющего собой выпуклую оболочку convX. Дальнейшие исследования прежде всего связаны с изучением различных комбинаторных характеристик граничного комплекса (множества всех граней) многогранников задач и использованием этих характеристик в качестве оценок сложности соответствующих задач в тех или иных классах алгоритмов. Наиболее ярким примером характеристики такого рода служит плотность графа многогранника задачи (напомним, что плотность графа равна максимальному числу его вершин, любые две из которых соединены ребром). Известно (см. монографию Бондаренко [9]), что эта величина является нижней оценкой сложности соответствующей задачи в широком классе алгоритмов прямого типа, использующих линейные сравнения. Установлено [9], что к этому классу относятся такие классические комбинаторные алгоритмы, как алгоритмы сортировки, "жадный" алгоритм, различные варианты метода ветвей и границ, метод динамического программирования, алгоритмы типа "локальный поиск", венгерский алгоритм и другие широко распространенные практические методы комбинаторной оптимизации. Отметим некоторые основные особенности обоих подходов. Заметим, что теория сводимости лишь дает способ сравнения задач по их сложности и указывает "самые сложные" задачи, но ничего не говорит о причине их труднорешаемости. В то же время ее преимуществом является относительная простота. Преимуществом же геометрического подхода является возможность вычисления конкретных числовых характеристик сложности задач. Недостаток его состоит в том, что такие вычисления обычно сопряжены с серьезными трудностями. Так, например, Папади-митриу [61] показал, что для многогранника задачи коммивояжера проблема распознавания смежности двух произвольно выбранных вершин является iVP-полной. Особо выделим следующую, объединяющую указанные подходы осо- ВВЕДЕНИЕ 7 бенность. Как правило, изучаемая комбинаторно-геометрическая характеристика признается адекватной (подходящей), если она отвечает современным представлениям о сложности задач. Соответственно, не вызывает удивления тот факт, что для всех признанно труднорешаемых задач, многогранники которых были изучены, получены экспоненциальные нижние оценки плотности полиэдральных графов (см. работы Белошевского [4], Бондаренко [6,9], Грешнева [11], Максименко [28,30], Симанчёва [35], Барахона и Маджуб [42]). В то же время для графов многогранников полиномиально разрешимых задач установлены полиномиальные (а для некоторых задач линейные) верхние и нижние оценки плотности (см. работы Белова [1,2], Бондаренко [5,8,9] и Шуниковой [7], Максименко [26,27]). Это наталкивает на мысль о том, что между теорией сводимости задач и исследованиями комбинаторных характеристик их многогранников существует некоторая взаимосвязь. Выявление этой взаимосвязи позволило бы объединить указанные подходы в единую теорию и подтвердило бы гипотезу о том, что "адекватные" комбинаторные характеристики многогранников труднорешаемых задач экспоненциальны. В настоящей работе изучается основа этой взаимосвязи. Ее установление ведется с двух направлений. С одной стороны, при изучении алгоритмов сведения задач комбинаторной оптимизации обнаруживается следующий любопытный факт. Если задача X сводится к задаче У, то, как правило, пространство исходных данных первой задачи аффин-но отображается в, соответственно, аффинное подмножество исходных данных второй задачи. Так появляется новое понятие аффинной сводимости задач комбинаторной оптимизации. С другой стороны, исследуются свойства относительно мало изученной геометрической конструкции — конусного разбиения пространства исходных данных задачи. Отметим, что это понятие было использовано Бондаренко [5, 6] при установлении взаимосвязи между плотностью ВВЕДЕНИЕ 8 графа многогранника и сложностью соответствующей задачи. Проявление интереса к исследованию свойств этой геометрической конструкции прежде всего связано с известным фактом о том, что конусное разбиение — двойственная к многограннику задачи конструкция. Оказывается, конусное разбиение является более гибким и мощным инструментом для исследования свойств задач, чем их многогранники. Так, с помощью конусного разбиения можно изучать комбинаторно-геометрические характеристики сложности для частных случаев задач, в то время как свойства многогранника характеризуют только общую задачу. Впервые это было обнаружено в работе [28] при исследовании классической задачи о кратчайшем пути, в которой, как известно, накладываются ограничения неотрицательности расстояний. Далее, на основании изложенных фактов делается вывод о том, что при аффинном сведении задачи X к задаче Y конусное разбиение множества исходных данных первой задачи аффинно преобразуется в некоторую часть конусного разбиения множества исходных данных второй задачи. При детальном изучении этого явления обнаруживается, что при аффинном сведении задач граф многогранника М(Х) первой задачи оказывается изоморфным некоторому подграфу графа многогранника M(Y) второй задачи. Таким образом доказывается гипотеза о том, что граф многогранника "более сложной" задачи конструктивно сложнее графа многогранника "простой" задачи. В частности, следствием этого утверждения является соответствующее соотношение плотностей р(Х) и p(Y) графов многогранников задач: р(Х) < p(Y). Так, с возникновением нового понятия аффинной сводимости задач комбинаторной оптимизации появляется и новый подход к изучению сложности задач. По сути своей он похож на классическую теорию сводимости, но, естественно, имеет ряд существенных отличий. Во-первых, новый подход предназначен для изучения задач комбинаторной оптимизации с линейной целевой функцией. Тогда как классическая теория ВВЕДЕНИЕ 9 работает прежде всего с задачами распознавания. Во-вторых, оказывается, что при сведении задач комбинаторной оптимизации крайне трудно нарушить свойство аффинности при преобразовании вектора исходных данных одной задачи в вектор исходных данных другой задачи. Таким образом аффиная сводимость для таких задач наиболее естественна. Третье отличие заключается в понятии сложности. Классическая теория, говоря упрощенно, делит задачи по сложности на три класса: труд-норешаемые, полиномиально разрешимые, и задачи, принадлежность которых к этим двум классам не установлена. В новом подходе сложность задачи можно оценить числом. В частности, плотностью графа ее многогранника. Четвертое, объединяющее свойство: В основе нового подхода, как и в основе классической теории лежит доказательство труд-норешаемости одной определенной задачи. В классической теории это задача ВЫПОЛНИМОСТЬ, а в настоящей работе исследование сложности труднорешаемых задач начинается с непосредственного изучения графа многогранника задачи КЛИКА. Охарактеризовав основную идею работы, перейдем к описанию ее содержания по главам. В первой главе более подробно изложены основы как классической теории сводимости задач, так и геометрического подхода к изучению их сложности. Описано состояние проблемы в настоящий момент. Содержится краткий обзор уже известных результатов, которые в той или иной степени используются далее. Вторая глава посвящена изложению оригинальной методики решения поставленной задачи. В ней содержатся подробные доказательства теоретической основы дальнейших исследований. Вводятся понятия конусного и многогранного разбиения, и понятие аффинной сводимости задач комбинаторной оптимизации. В третьей, наиболее емкой главе приводятся многочисленные "экспериментальные данные", подтверждающие работоспособность предла- ВВЕДЕНИЕ 10 гаемой теории. Глава начинается с непосредственного изучения свойств многогранника "основной" задачи — оптимизационной задачи КЛИКА. Доказывается, что плотность графа этого многогранника совпадает с числом вершин и равна 2™, где п — размерность задачи. Дальнейшее развитие теории аффинной сводимости происходит по классическому сценарию. Конструируется алгоритм сведения "первой" задачи к "еще не изученной" задаче и доказывается, что он удовлетворяет условиям аффинности. Таким образом пополняется список задач с экспоненциальной плотностью полиэдрального графа. Процесс пополнения этого списка существенно облегчается за счет схожести оптимизационных задач и задач распознавания. Это позволяет при конструировании алгоритмов сведения оптимизационных задач пользоваться идеями алгоритмов сведения задач распознавания, известными из классической теории [13]. Тем не менее, некоторые алгоритмы аффинной сводимости в настоящей работе предложены впервые. Структуру этой главы удобно изобразить в виде ориентированного дерева (см. рис. 1). Каждая стрелка на рисунке символизирует алгоритм, сводящий задачу, расположенную в начале стрелки, к задаче, находящейся в конце. В корне дерева расположена "основная" задача КЛИКА. В список исследуемых задач в первую очередь вошли наиболее известные классические задачи. В их числе оптимизационные варианты пяти из шести задач, фигурирующих в [13] как основные iVP-полные задачи. В четвертой главе изучаются комбинаторно-геометричекие свойства полиномиально разрешимых задач: задачи о кратчайшем пути, задачи о назначениях и задачи о паросочетаниях в произвольном графе. Для графа конусного разбиения задачи о кратчайшем пути значение плотности вычисляется непосредственно. Далее показывается, что эта задача аффинно сводится к задаче о назначениях, что позволяет оценить снизу плотность графа многогранника последней задачи и задачи о паросочетаниях. ВВЕДЕНИЕ Как видим, список исследуемых в работе задач достаточно представителен для того, чтобы подтвердить работоспособность предлагаемого подхода. Таким образом, полученные результаты позволяют существенно облегчить изучение свойств графов многогранников задач и открывают новые перспективы для исследований. И, наконец, в заключении подводятся итоги диссертационного исследования, проводится сравнительный анализ с уже известными результатами, формулируются несколько интересных гипотез, требующих для своего решения более внимательного изучения феномена аффинной сводимости. 1. Понятие сложности в комбинаторной оптимизации 1.1. Некоторые сведения из теории сводимости задач Для создания целостного представления о развитии и современном состоянии исследуемой проблемы перечислим в хронологическом порядке наиболее интересные и важные результаты, достигнутые ранее. Начало бурного развития теории сложности задач и алгоритмов прежде всего связано с появлением ЭВМ. Эта связь обусловлена тем, что "в ручную" удается решить только задачи небольшой размерности и современные ассимптотические оценки сложности для таких ситуаций оказываются слишком приближенными. Итак, при решении задач с помощью ЭВМ сформировалось следующее понятие "хорошего" алгоритма: его трудоемкость (максимальное число операций, необходимое для решения задачи) не должна превосходить некоторого полинома от размерности исходных данных задачи. Соответственно, алгоритмы с экспоненциальной от длины входа трудоемкостью принято считать "плохими". Оказалось, что далеко не для всех задач удается построить эффективные алгоритмы. И, естественно, возникла проблема поиска причин труднорешаемости некоторых задач. Наиболее простым объектом для изучения этой проблемы оказались задачи из класса NP. Классическим примером такой задачи служит знаменитая задача коммивояжера (КОММИВОЯЖЕР). В ней рассматривается полный реберно взвешенный граф G(V,E), где V = {г>1,г>2, • • • ,vn} — множество вершин, Е = {е^- = (vi,Vj) : 1 < г < j < п} — множество ребер. На множестве ребер задана функция длин с : Е —>¦ i?, приписывающая каждому ребру ejj Е Е длину с^- = с(е^) Е R. Назовем гамилътоновым цикл, проходящий через каждую вершину графа ровно 1. СЛОЖНОСТЬ В КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ 13 один раз. Задача коммивояжера заключается в ответе на вопрос: Существует ли в графе G такой гамильтонов цикл, суммарная длина ребер которого была бы не меньше некоторого, наперед заданного числа С. Развитие теории сложности прежде всего связано с фундаментальным понятием сводимости задач, суть которого заключается в следующем. Задача X сводится к задаче У, если, упрощенно говоря, первая является частным случаем второй. В качестве примера здесь уместно привести алгоритм [48] сведения задачи коммивояжера к задаче о длиннейшем пути, на который мы будем ссылаться в дальнейшем. Прежде сформулируем задачу о длиннейшем пути (ЗДП) в варианте распознавания. Рассмотрим полный реберно взвешенный граф G'(V', Е'), где V = {v[,v2, ¦ ¦ ¦ ,v'n+1} — множество вершин, две вершины s и t которого выделены. Далее, не уменьшая общности, будем предполагать, что s = v[, a t = v'n+1. Каждому ребру е\- Е Е' приписана некоторая длина bij = Ъ{е\-) Е R. Цель задачи состоит в ответе на вопрос о том, существует ли в графе G такой простой путь без циклов, начинающийся в вершине s и заканчивающийся в t, суммарная длина ребер которого была бы не меньше некоторого, наперед заданного числа В. Теорема 1.1. Задача коммивояжера для графа на п вершинах сводится к задаче длиннейший путь для графа на п + 1 вершинах: КОММИВОЯЖЕР ос ЗДП. Доказательство. Найдем минимальный стгп и максимальный стах веса для ребер графа G задачи коммивояжера: cmin = min{c(e)}, cmax = тах{с(е)}. е<ЕЕ е<ЕЕ Предположим, что ст{п < стах и С > п * стгп, так как в противном случае задача не представляет интереса. Теперь ребрам графа G' задачи 1. СЛОЖНОСТЬ В КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ 14 о длиннейшем пути припишем следующие веса: Cij - cmin + га * (cmax - cmin), если 1 < г < j < га, = < сц - cmin + га * (стаж - стг-„), если 1 < г < j = га + 1, О, если г = 1, j = га + 1. Кроме того, пусть В = С — п * ст{п + га2 * (стах — cmin). Учитывая, что С > га * cmin, получаем В > га2 * (стаж - стг-„). Отсюда следует, что в графе G' длина некоторого пути будет не меньше числа В, только если этот путь состоит из га ребер. Кроме того, нетрудно убедиться, что длина некоторого пути (Vl5 v\ ,... , г/- , v'n+l) удовлетворяет условию решения задачи о длиннейшем пути тогда и только тогда, когда гамильтонов цикл (г>1, г>г-2,... , г>г-п, ^i) удовлетворяет условию решения задачи коммивояжера. Теорема доказана. Этот алгоритм позволяет сделать следующий вывод. Задача о длиннейшем пути для графа на га + 1 вершинах не проще задачи коммивояжера для графа на га вершинах. Аналогичные связи были установлены и для ряда других задач. И следующим шагом в развитии теории сложности стало открытие С. Куком [22] в начале 70-х гг. "самой сложной" в классе NP задачи ВЫПОЛНИМОСТЬ (ВЫП). А точнее, был предложен полиномиальный алгоритм сведения произвольной задачи из класса NP к задаче ВЫП. Это открытие послужило мощным толчком для дальнейшего развития теории полиномиальной сводимости. Теперь, чтобы показать, что некоторая задача X является "самой сложной" в классе NP, достаточно было привести алгоритм сведения задачи ВЫП к данной. Успешное применение этой схемы предоставило возможность пополнять список "самых сложных" задач, которые впредь стали называть NP-полными. Перечислим, следуя [13], пять "основных" iVP-полных задач: Задача 3-выполнимость (3-ВЫП), задача вершинное покрытие (ВП), задача 3-сочетание (3-С), задача РАЗБИЕНИЕ и задача КОММИВОЯЖЕР. В настоящее время принадлежность к классу iVP-полных доказана для сотен внешне непохожих задач. И до сих пор, несмотря на 1. СЛОЖНОСТЬ В КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ 15 значительные усилия большого числа исследователей, полиномиальные алгоритмы решения этих задач так и не найдены. В итоге сформировалась распространенная гипотеза о том, что создание таких алгоритмов в ближайшее время невозможно. Следуя этой гипотезе труднорешаемыми признаны и все те задачи, к которым могут быть сведены iVP-полные. Например, те же iVP-полные задачи, но в варианте оптимизации. Так, труднорешаемой является оптимизационная задача коммивояжера, в которой требуется найти гамильтонов цикл максимальной длины. Здесь, в интересах настоящей работы, необходимо обозначить взаимосвязь между задачами распознавания и оптимизации. Рассмотрим связку из двух задач: 1) Задача оптимизации: Найти аргумент iGl целевой функции с(х) на котором она достигает свое максимальное значение. 2) Задача распознавания: Определить, существует ли такой аргумент х G X, при котором целевая функция с(х) принимает значение, не меньшее некоторого, наперед заданного числа С: с(х) > С; и если существует, то указать такой аргумент. Из условия задач видно, что задача распознавания "проще" задачи оптимизации. С другой стороны, если предположить, что мы умеем решать задачу распознавания, и что целевая функция может принимать только целочисленные значения, причем множество ее значений ограничено: с(х)\ < N, то не представляет труда построение дихотомической процедуры, которая решала бы задачу оптимизации, используя алгоритм решения задачи распознавания не более, чем log2 N раз. Таким образом, при выполнении указанных условий задача оптимизации и задача распознавания оказываются одинаково сложными. Кроме того, оказалось, что даже при несоблюдении указанных условий для задач оптимизации можно построить аналогичную теорию сводимости. Для этого требуется лишь модифицировать известные алгоритмы сведения соответству- 1. СЛОЖНОСТЬ В КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ 16 ющих задач распознавания. Проиллюстрируем суть модификации, сведя оптимизационную задачу коммивояжера к оптимизационной задаче о длиннейшем пути. Прежде скорректируем формулировки задач. Теперь в них требуется найти, соответственно, максимальный гамильто-нов цикл в графе G и длиннейший путь в графе С, ведущий из вершины s в вершину t. Теорема 1.2. Оптимизационная задача коммивояжера (ЗК) для графа на га вершинах сводится к оптимизационной задаче о длиннейшем пути для графа на га + 1 вершинах: ЗК ос ЗДП. Доказательство. Рассуждения проведем в два этапа. Прежде всего заметим, что сформулированная выше задача коммивояжера сводится к своему "частному" случаю, когда на длины ребер с'- = с'(еу) накладываются следующие ограничения: -1 < с\3 < 1. Чтобы свести общую задачу к этому "частному" случаю, достаточно положить Cij = w где \|\|с\|\| = \l ^ V^J' l Очевидно, что такая замена не повлияет на выбор оптимального решения, так как длина каждого гамильтонова цикла лишь умножится на фиксированное число тгтт. На следующем этапе сведем "частный" случай ЗК к ЗДП. Ребрам графа G' задачи о длиннейшем пути припишем следующие веса: с\- + 2га + 1, если 1 < г < j < га, с'и + 2га + 1, если 1 < г < j = га + 1, (1) О, если i = 1, j = га + 1. Нетрудно убедиться, что в графе G' длиннейшим может быть только путь, состоящий из га ребер. Причем, (Vi,^'- ,... , v\ ,v'n+i) — длинней- 1. СЛОЖНОСТЬ В КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ 17 ший путь в графе G' тогда и только тогда, когда (г>х, г>г-2,... , г>г-п, г>х) — длиннейший гамильтонов цикл в графе G. Теорема доказана. Отметим здесь, что любой алгоритм сведения задач оптимизации легко преобразуется в алгоритм сведения задач распознавания. Это следует из того, что задачи распознавания по сути своей "проще" задач оптимизации. В то же время обратное преобразование довольно часто оказывается нетривиальным. В этом смысле приведенный выше пример нетипичен. Приведем еще один замечательный пример сведения задач оптимизации, на который будем неоднократно ссылаться в дальнейшем. Как уже говорилось, задачи оптимизации можно разделить на два типа: задачи на минимум и задачи на максимум. В задаче на минимум требуется найти такой х* Е X, при котором целевая функция с(ж*) достигает на множестве X свое минимальное значение. Замечательное свойство задач оптимизации состоит в том, что задача на минимум сводится к задаче на максимум с тем же множеством допустимых решений X и целевой функцией с'(х) = —с(ж), и наоборот, задача на максимум сводится к задаче на минимум. Соответственно, оказывается достаточным изучить свойства для одного типа задач. Именно поэтому в этой главе и далее, с целью единообразия изложения, под задачами оптимизации подразумеваются задачи на максимум, если не оговорено противное. Заканчивая описание теории сводимости, отметим, что эта теория лишь дает способ сравнения задач по их сложности и указывает "самые сложные" задачи, но ничего не говорит о причине их труднорешаемости. В этом смысле "полярным" является другое направление в исследовании сложности задач, выявляющее глубинные причины их труднорешаемости, и основанное на исследовании геометрических конструкций, ассоциированных с задачами и алгоритмами. 1. СЛОЖНОСТЬ В КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ 18 1.2. Многогранники задач Проиллюстрируем основные идеи геометрического подхода к исследованию сложности задач на примере задачи коммивояжера. Пусть, как и прежде, G(V, Е) — полный реберно взвешенный граф на п вершинах, в котором требуется найти гамильтонов цикл максимальной длины. Рассмотрим множество Хп всех гамильтоновых циклов в этом графе. Это множество еще называют множеством допустимых решений задачи. Построение ассоциированных с задачей геометрических конструкций прежде всего основано на интерпретации множества Хп как множества точек в евклидовом пространстве Rm. Для задачи коммивояжера положим т=\Е\ = ^^ (2) и каждому ребру е^ Е Е поставим в соответствие координату ж^- произвольной точки х = (х^) Е Rm. Теперь для каждого цикла ж Е Хп рассмотрим его характеристический вектор х = (ж^) E R111'. 1, если eij Еж, (J, если e{j (jt x. Обозначим через Хп множество всех таких векторов. Тогда задача коммивояжера с вектором с длин ребер преобразуется в задачу максимизации на множестве Хп линейной функции (скалярного произведения): (с, ж) -Л max, ж Е Хп. Отметим здесь важное обстоятельство. Под термином "задача коммивояжера" подразумевается массовая задача, или совокупность индивидуальных задач. Далее индивидуальной задачей с вектором с исходных данных и фиксированной размерностью п будем называть задачу оптимизации на множестве Хп линейной функции (с, ж). Обозначение: индивидуальная задача [Хп,с]. Массовой задачей Хп назовем совокупность всех индивидуальных задач с фиксированным п и произвольным с. 1. СЛОЖНОСТЬ В КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ 19 Первой, и наиболее известной геометрической конструкцией, основанной на такой интерпретации, является выпуклая оболочка, натянутая на множество X = Хп, которую принято называть многогранником задачи: М{Х) = convX. Дальнейшие исследования многогранников можно условно разбить на два направления. С одной стороны, понятие многогранника позволяет задачу комбинаторной оптимизации (ЗКО) сформулировать как задачу линейного программирования (смотри, например, монографию Емеличева, Ковалева и Кравцова [15]). Это обстоятельство, благодаря открытию в конце 70-х гг. Хачияном [36] (а позднее Кармаркаром [56]) полиномиального алгоритма решения задач линейного программирования (ЗЛП), вселило надежду на отыскание эффективного алгоритма и для решения трудноре-шаемых задач комбинаторной оптимизации. К сожалению, несмотря на многочисленные попытки, описать множество всех гиперграней (фасет) многогранника какой бы то ни было труднорешаемой задачи в общем виде до сих пор никому не удалось. Кроме того, Карпу и Пападими-триу [57] удалось показать, что проблема полного описания всех фасет многогранника труднорешаемой задачи сама по себе является трудно-решаемой. Тем не менее, это направление имеет ряд интересных перспектив и в настоящее время активно развивается (см., например, работы [12,14,17,38,46,59,60,65]. Выявляются все новые и новые семейства линейных ограничений, описывающие гипергани многогранников труд-норешаемых задач. Отметим в связи с этим любопытный факт, упомянутый в монографии Деза и Лоран [14]. По-видимому, феномен возрастания сложности структуры граней при росте размерности задачи является общим для многогранников труднорешаемых задач. Так, многогранник симметричной задачи коммивояжера для п = 9 городов содержит 42104 442 фасеты и более чем 51043 900 866 фасет для п = 10 (см. работу Кристофа и Райнельта [47]). Другое направление прежде всего связано с исследованием комбина- 1. СЛОЖНОСТЬ В КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ 20 торных свойств графа многогранника и использованием их как характеристик сложности соответствующей задачи в определенном классе алгоритмов. Отметим в этой связи ряд работ [9,15,25,37,66,67]. Формальное описание графа многогранника начнем с определения вершины. Точка х Е М(Х) называется вершиной многогранника М(Х), если найдется вектор с Е Rm такой, что для любого у Е М(Х), отличного от ж, выполнено (с, ж) > (с, у). Или, другими словами, х является единственным оптимальным решением для индивидуальной задачи [X, с]. Из определения следует, что множество вершин ext М(Х) многогранника М(Х) является подмножеством множества X: ext М(Х) С I. В дальнейшем будем предполагать, что для каждого допустимого решения iGl найдется вектор исходных данных с Е Rm такой, что это решение является единственным оптимальным для индивидуальной задачи [X, с]. В противном случае, не уменьшая общности, такое решение х можно исключить из множества допустимых решений. Отметим, что это естественное предположение выполнено для всех исследуемых ниже задач. Это означает, в частности, что множество X совпадает с множеством вершин многогранника задачи: X = extM(X). (4) Смежность вершин такого многогранника можно определить следующим образом. Две вершины х,у Е X называются смежными (соединенными ребром), если найдется такой вектор с Е Rm, для которого индивидуальная задача [X, с] имеет ровно два оптимальных решения х и у, или, другими словами, для каждого z E X \ {х,у} выполнено (ж, с) = (у, с) > (2, с). Соответственно, граф G(X) многогранника М(Х) состоит из множества вершин и ребер многогранника. Алгоритмические свойства задач обычно описываются в терминах таких характеристик графов многогранников как степени вершин, диаметр, высота графа и т. д. Но все перечисленные характеристики об-

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

Цена, в рублях: (при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)	1425

Скачать бесплатно	23541.doc

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

15.04.24 Задачи, условия и этапы организации экспериментальной работы

15.04.24 Критерии качества преподавания

15.04.24 Категория нормы в обучающей деятельности

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

© 2006-2022. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.