Содержание к диссертации
Введение
1. Постановка задач и обзор используемых результатов 9
1.1. Постановка задач 9
1.2. Краткий обзор известных результатов 12
2. Анализ полного множества альтернатив 14
2.1. Общая теорема о полном множестве альтернатив 14
2.2. Анализ многокритериальной задачи о пути 16
3. Сложность в смысле Кука-Карпа многокритериальных задач 19
3.1. ЛтР-полнота многокритериальных задач на графах 20
3.2. Замечания о задачах о минимальном остовном дереве и о назначениях 38
3.3. Многокритериальная задача о кратчайших путях для всех пар узлов графа 42
3.4. Задача о рюкзаке 45
4. Анализ лексикографических многокритериальных задач 57
4.1. Метод линейной свертки для лексикографических задач. 57
4.2. Линейные разделяющие алгоритмы 59
4.3. Описание модификации для некоторых известных алгоритмов 04
Список литературы !... G9
- Анализ многокритериальной задачи о пути
- Замечания о задачах о минимальном остовном дереве и о назначениях
- Многокритериальная задача о кратчайших путях для всех пар узлов графа
- Линейные разделяющие алгоритмы
Введение к работе
Дискретные экстремальные задачи в качестве математических моделей широко распространены в экономике, теории управления и других областях. Однако только относительно недавно подобные задачи стали объектом серьезного изучения. Это связано с тем, что для решения задач малой размерности, как правило, достаточно воспользоваться простым перебором всех возможных решений, а с увеличением размерности даже более экономичные алгоритмы оказываются неприемлемыми из-за возрастающих объемов вычислений. Появление быстродействующей вычислительной техники привело к увеличению интереса исследователей к анализу задач данного класса и разработке алгоритмов, эффективно работающих на практике. Вот почему именно во второй половине 20-го века были разработаны наиболее известные методы решения задач дискретной оптимизации, и появилась теория вычислительной сложности задач.
Для того чтобы почувствовать специфику такого типа задач, не останавливаясь на точных формулировках, сравним две широко известные математические модели. Первая - это задача коммивояжера, на которой в течение долгого времени сконцентрировано внимание исследователей и которая явилась в некотором роде краеугольным камнем в изучении задач дискретной оптимизации. Предполагается заданным множество городов и расстояний между ними; коммивояжер, начиная движение из своего населенного пункта, должен найти кратчайший обход всех пунктов, посещая каждый город только один раз.
Вторая - это задача о минимальном остовном дереве, имеет те же входные данные, что и задача коммивояжера, только теперь требуется соединить все города сетью дорог без дополнительных узлов так, чтобы их общая протяженность была минимальной.
Может показаться, что в силу конечности множества допустимых вариантов, решение подобных задач не потребует больших усилий. Но количество анализируемых маршрутов растет очень быстро с увеличением размерности задачи, роль которой в данном случае играет количество городов п (заметим, что для задачи коммивояжера эта величина составляет (п — 1)!/2, а для задачи о минимальном остов-ном дереве - ?in~2). II если для второй задачи известен эффективный "жадный" алгоритм, дающий точное решение и позволяющий с помощью современных ЭВМ строить сети для тысяч городов, то для задачи коммивояжера алгоритма с подобными качествами до сих пор не найдено, несмотря на значительные усилия, приложенные в этом направлении. Более того, существуют достаточно веские причины, лишающие надежды отыскать такой алгоритм в ближайшем будущем.
Перейдем к общей постановке задачи дискретной оптимизации в обычной, однокрнтериальной постановке. Пусть задано конечное множество Л' и функция /, определенная на этом множестве и принимающая действительные значения. Требуется найти такой элемент х* Є X, для которого f(x*) < f(x) для любого элемента х Є X.
Как уже отмечалось, любая задача этого класса, с одной стороны, допускает решение переборным способом в силу конечности множества допустимых решений, но в то же время таит в себе возможность "комбинаторного взрыва". Это связано с тем, что количество вариантов может расти экспоненциально в зависимости от размерности задачи, отчего необходимые для полного перебора затраты машинного времени и памяти делают ее решение практически невозможным, даже на самых современных ЭВМ. Поэтому "хорошим", или эффективным, алгоритмом принято считать полиномиальный алгоритм, то есть такой, временная трудоемкость которого оценивается сверху полиномом от длины входа. Алгоритмы, трудоемкость которых не допускает подобной оценки, традиционно считаются неэффективными и представляют собой варианты полного перебора. В свою очередь, задачи, для которых неизвестны полиномиальные алгоритмы, характеризуются как труднорешаемые.
Оказалось, что число задач комбинаторной оптимизации, допускающих эффективное решение, не так велико, соответственно ограничен и список полиномиальных алгоритмов. Это алгоритмы быстрой сортировки, венгерский метод для задачи о назначениях, "жадный" алгоритм для задачи о минимальном остовном дереве, алгоритм для задачи о кратчайшем пути в графе, алгоритм нахождения максимального паросочетания в произвольном графе. К этому можно также добавить метод ветвей и границ и метод динамического программирования, которые хоть и не всегда являются полиномиальными, но хорошо зарекомендовали себя на практике.
При рассмотрении задач многокритериальной оптимизации речь идет о векторной целевой функции, подлежащей оптимизации на множестве X допустимых решений. Дискретный характер задачи также предполагает конечность множества X. Здесь, так же как и в случае однокритериальной задачи дискретной оптимизации, решение можно искать переборным способом, но при этом возникают все описанные выше трудности.
Специфика многокритериальных задач определяется прежде всего тем, что при к > 2 (к— количество критериев) формулировка задачи связана с предварительным выбором типа упорядоченности в Rk. Для уточнения термина "оптимизация" остановимся на двух типах упорядоченности, которые рассматриваются далее — обычное, покоординатное сравнение векторов и лексикографическое.
Будем писать и < v, где и = (щ,..., u*), v = (i»i,..., t^) если Uj < і',-, і = 1,...,п. Такое отношение определяет в Rk полуупорядоченность.
Лексикографическое неравенство между элементами из Rk будем обозначать и
ВЫПОЛНЯЮТСЯ УСЛОВИЯ Щ = Vi, . . . , Щ = Vi, Щ+і < Vi+\.
Замечание 0.1. Очевидно, что минимальных элементов, в конечном множестве может быть несколько, а лексикографически минимальный — ровно один.
Отметим, что покоординатное сравнение векторов соответствует многокритериальной задаче с равноценными критериями. Лексикографическая же упорядоченность возникает тогда, когда одни критерии векторной функции предпочтительнее других. Проиллюстрируем различия этих задач на простейшем примере. При проектировании дороги, соединяющей два пункта, естественно учитывать два параметра: стоимость ее строительства и протяженность дороги. Если предполагается использовать дорогу относительно недолго, то задача окажется лексикографической, а приоритетным критерием будет стоимость строительства. В случае долговременного использования стоимость строительства и протяженность дороги - это равноценные критерии, поэтому при построении математической модели естественнее ввести обычное отношение полуупорядоченности.
Ясно, что изучение сложности возникающих таким образом задач представляет особый интерес в случаях, когда соответствующие од-нокрнтерпальные задачи полиномиально разрешимы. Это следует из того, что однокрнтернальная задача всегда является частным случаем многокритериальной.
Теория многокритериальных задач развита в работах Дубова Ю. А. Травкина С.II. [1], Подиновского В.В., Ногина В.Д., Гаврилова В.М. [2], [3], Березовского Б.А. [4], большое количество результатов приведено в обзорной статье Емеличева В.А. и Перепелицы В. А. [5].
Обзор публикаций, посвященных задачам многокритериальой оптимизации, позволяет выделить несколько направлений, на которых в основном сосредоточены исследования. ,
Получение множества решений по Парето с помощью детального учета конструкции множества допустимых решений X. В каче стве примера можно привести следующие публикации: в работе Guerriero F., Musmanno R. [G] предложен псевдополиномиальный алгоритм отыскания множества Парето минимальных элементов для многокритериальной задачи о кратчайшем пути; в работе Djordje D. [7] рассматривается псевдополиномиальный алгоритм для многокритериальной задачи о рюкзаке.
Исследование возможности получения оптимального решения пу тем перехода от многокритериальной задачи к однокритериаль- ной с аддитивным целевым критерием. Установлено, что, исполь зуя линейную свертку критериев, можно находить все оптимумы Парето (эффективные решения) в многокритериальной задаче линейного программирования. Упомянем также работы Крав цова М.К. и Янушкевича О.А. [8], Емеличева В.А. и Янушкевича
О.A. [9], где указана общая формула для оптимумов Парето, находимых сверткой критериев в случае, когда множество векторных (достижимых) оценок конечно. В работе Кравцова М.К. [10] показано, что существуют задачи, которые нельзя разрешить в классе алгоритмов линейной свертки критериев. Кроме того, следует упомянуть публикации: Меламеда И.И. и Сигала И.Х. [11-13], Емелнчева В.А., Кравцова М.К. [14], Емеличева В.А., Кравцова М.К., Янушкевича О.А. [15,16], Смирнова М.М. [17].
Получение решения для лексикографической многокритериальной задачи. Это направление исследований представлено работами Емеличева В.А., Кравцова М.К., Янушкевича О.А., Гирлиха Э., Червака Ю.Ю., Червака О.Ю. [18-20].
Анализ сложности многокритериальных задач (см. Емеличев В.А., Перепелица В.А., Сергиенко И.В. [21]- [23]).
Приближенные методы отыскания элементов, входящих в Паре-товское множество. В качестве примера можно привести следующие публикации: Емеличева В.А. и Перепелицы В.А. [24], Gengui Z. и Mutsio G. [25]
Целью настоящей работы является дальнейшее исследование многокритериальных задач как в обычной покоординатной, так и в лексикографической постановке. В частности, рассматриваются наиболее известные задачи из теории графов, для которых в однокрите-рнальной постановке существуют полиномиальные алгоритмы.
Содержательная часть работы разделена на несколько глав.
Первая глава посвящена краткому обзору уже известных результатов, которые в той или иной степени будут использоваться в дан-нон работе. В ней же приводится развернутая постановка рассматриваемых далее задач.
Во второй главе изучается вопрос о мощности множества минимальных элементов в f(X).
Предположим, что рассматривается произвольное конечное множество -Е", на котором определена функция с : Е —> R2. Обозначим через X множество всех непустых его подмножеств, |Х| = 2'^1 — 1, и положим
Для сформулированной модели устанавливаются следующие утверждения:
Теорема. Для любого конечного множества Е существует такая функция с : Е —> Л2, для которой множество {/(#) : ж Є А'} состоит из попарно несравнимых элементов, или, иначе, Ar = Л".
Теорема. Пусть Хт — множество всех подмножеств J51, содержащих по т элементов, 1 < т < п = \Е\. Тогда существует такая положительная функция с : Е —> R2, для которой множество {/(х) : х Є Хт) состоит из попарно несравнимых элементов.
В Третьей главе рассматривается вопрос о сложности многокритериальных задач, для которых в однокритериальной постановке известны полиномиальные алгоритмы. Кроме того, приводятся результаты, показывающие, что труднорешаемость многокритериальных дискретных задач определяется именно наличием более одного критерия, а не сложностью множества допустимых элементов.
В конце главы описывается алгоритм с псевдополиномиальной временной сложностью для двухкритериальной задачи нахождения всех Парето-мннимальных элементов, ассоциированных со всевозможными путями между всеми парами вершин графа G = (V, Е). .
Четвертая глава посвящена рассмотрению лексикографических многокритериальных задач.
Здесь описывается и обосновывается конструкция, позволяющая алгоритмы для однокритериальных задач трансформировать для многокритериальных. При этом временная сложность, по сравнению с однокрнтерпальным случаем, увеличивается не более чем в к раз, где к - количество критериев. Приведены примеры использования алгоритма для наиболее известных многокритериальных задач на графах.
1. Постановка задач и обзор используемых результатов
1.1. Постановка задач
Как уже отмечалось во Введении, математическая постановка дискретной многокритериальной задачи предполагает, что задано конечное множество допустимых значений X, на котором определена векторная целевая функция f:X-*Rk. (1)
Учитывая сказанное о типах упорядоченности в Rk, уточним формулировки задач, о которых пойдет речь ниже. Но сначала напомним следующее определение. Элемент и* Є У назовем минимальным в У, где У - полуупорядоченое множество, если из условий и < и* и и Є Y следует, что и = и*.
Задача 1. Требуется найти подмножество X* С X всех таких элементов я*, для каждого из которых значение /(#*) минимально в множестве Y = /(А) = {/(я) : х Є X} С Л*. (2)
Задача 2. Для заданного у* Є Rk выяснить, существует ли х* Є А", для которого f(x*) < у*. ,
Задача 3. Требуется найти х* Є А, для которого значение f(x*) лексикографически минимально в У.
В работе будет использоваться терминология и обозначения из [2G]. В частности, элемент х* Є X, для которого f(x*) минимален в /(А), принято называть паретовским минимумом, или минимумом по Парето, функции / на множестве А". Множество А^*, состоящее из всех паретовских минимумов, называется паретовским множеством, или множеством минимальных по Парето элементов. II таким образом, подмножество А"0 С X* является полным множеством альтернатив, если его мощность |J\TJ минимальна и выполняется равенство: /(А0) = /(А*).
Здесь и далее для определенности рассматриваются задачи вида 1-3 как задачи минимизации. Переход от задачи на минимум к задаче максимизации легко осуществляется заменой целевой функции / на (—/), а у*, соответственно на {—у*)- Ясно также, что подобной замене могут подвергаться не все функции - компоненты /j, г = 1,..., &, где / = (/і,..., /д.), а лишь некоторые из них; при этом все дальнейшие выводы содержательно сохраняются.
Отметим, что сложность решения Задачи 1 в определенной степени оценивается мощностью множества Х, так как само перечисление элементов множества Лг может оказаться алгоритмически трудоемким.
Другой подход к анализу сложности задач основан на идеях Кука-Карпа теории iVF-полных задач [27]. Эта теория работает с задачами распознавания свойств (именно в таком виде и сформулирована Задача 2). Не останавливаясь подробно на точных определениях, напомним, что в соответствии с этой теорией иерархия задач по возрастанию сложности выглядит следующим образом: полиномиально разрешимые задачи; задачи iVP-полные, но разрешимые алгоритмами с псевдополи-номнальной временной трудоемкостью; — задачи, NP-полные в сильном смысле. Диссертацию можно структурировать:
Задача 1 рассматривается в Главе 2
Анализ многокритериальной задачи о пути
Рассмотрим произвольное конечное множество Е, на котором определена функция с: Е —ї R2. Обозначим через X множество всех непустых его подмножеств, Х = 2 1 — 1, и положим Теорема 2.1. Для любого конечного множества Е существует такал функция с : Е — R2, для которой множество Y = {f(x): х Є Л"} состоит из попарно несравнимых элементов, то есть Х = X. Доказательство. Обозначим \Е\ = п и положим Е = {ei,..., еп}. Функцию с определим равенствами (см. рис. 1 на стр. 23) Покажем, что предложенная функция является искомой. Сначала докажем, что для всяких двух различных непустых подмножеств х ,х" Є X выполняются неравенства fi(x ) ф h{x") и /2(-0 ф f2(x"). Легко заметить, что двоичное представление любого Ci(e) = 2г содержит 1 только в і разряде, остальные разряды содержат нули. Разные числа имеют разное двоичное представление. Отметим, что сумму весов элементов, входящих в любое непустое подмножество, можно записать как где pi последовательность степеней весов элементов, входящих в данное подмножество. Двоичное представление числа В содержит 1 только в тех разрядах, которые входят в последовательность pi, остальные разряды содержат нули. Аналогичные рассуждения можно провести и для критерия с2(е). Следовательно fi(x ) ф fi{x") и /г ) ф /г (#- ), что и требовалось доказать. При этом, если fi(x ) /і(ж"), то /2(я ) І2{х") и наоборот. Из этих строгих неравенств следует, что f(x ) и f(x") несравнимы, то есть .Y = X. Теорема доказана. Поведение полного множества альтернатив оказывается брлее сложным, если дополнительно потребовать, чтобы функция с удовлетворяла неравенствам: В этом случае утверждение Теоремы 2.1 в общем виде перестает быть верным. Даже для \Е\ = 2, Теорема 2.1, при условии положительной функции с, не верна. Действительно, пусть с{е\) = («і, 6і), с{е2) = (а2,Ь2), тогда с(е{) + с(е2) с(е\) и с(е{) + с(е2) с(е2) для любых неотрицательных весов а\, Ъ\, а2,62. Однако при ограничениях (9) справедлив следующий аналог Теоремы 2.1. Теорема 2двоичное представление. Отметим, что сумму весов элементов, входящих в любое непустое подмножество, можно записать как где pi последовательность степеней весов элементов, входящих в данное подмножество. Двоичное представление числа В содержит 1 только в тех разрядах, которые входят в последовательность pi, остальные разряды содержат нули. Аналогичные рассуждения можно провести и для критерия с2(е).
Следовательно fi(x ) ф fi{x") и /г ) ф /г (#- ), что и требовалось доказать. При этом, если fi(x ) /і(ж"), то /2(я ) І2{х") и наоборот. Из этих строгих неравенств следует, что f(x ) и f(x") несравнимы, то есть .Y = X. Теорема доказана. Поведение полного множества альтернатив оказывается брлее сложным, если дополнительно потребовать, чтобы функция с удовлетворяла неравенствам: В этом случае утверждение Теоремы 2.1 в общем виде перестает быть верным. Даже для \Е\ = 2, Теорема 2.1, при условии положительной функции с, не верна. Действительно, пусть с{е\) = («і, 6і), с{е2) = (а2,Ь2), тогда с(е{) + с(е2) с(е\) и с(е{) + с(е2) с(е2) для любых неотрицательных весов а\, Ъ\, а2,62. Однако при ограничениях (9) справедлив следующий аналог Теоремы 2.1. Теорема 2.2. Пусть Хт — множество всех подмножеств Е, содержащих по т элементов, 1 т п = \Е\. Тогда существует такая положительная функция с : Е — R, для которой множество Ym = f(Xm) состоит из попарно несравнимых элементов. Доказательство. Рассмотрим функцию с, которая построена в ходе доказательства Теоремы 2.1, то есть задана функция с. Тогда для построения искомой функции с достаточно к каждому вектору (8) прибавить вектор вида (М, М), где Л/ 2п 1. В результате, во-первых, функция с окажется положительной, то есть будет выполнено условие (9), а во-вторых, вес всех элементов из Ут возрастет ровно на (тМ, тМ), и, следовательно, внутри множества Ут они останутся попарно несравнимы, что и требовалось доказать. Теорема доказана. Из Теоремы 2.2 непосредственно вытекают упомянутые выше факты относительно двухкрнтериальных задач об остовном дереве и о назначениях [21,33,50,51]. Иначе говоря из Теоремы 2.2 непосредственно вытекает, что существуют индивидуальные двухкрите-рпальные задачи об остовном дереве, о назначениях, о рюкзаке для которых множество допустимых решений совпадает с полным множеством альтернатив.2. Пусть Хт — множество всех подмножеств Е, содержащих по т элементов, 1 т п = \Е\. Тогда существует такая положительная функция с : Е — R, для которой множество Ym = f(Xm) состоит из попарно несравнимых элементов. Доказательство. Рассмотрим функцию с, которая построена в ходе доказательства Теоремы 2.1, то есть задана функция с. Тогда для построения искомой функции с достаточно к каждому вектору (8) прибавить вектор вида (М, М), где Л/ 2п 1. В результате, во-первых, функция с окажется положительной, то есть будет выполнено условие (9), а во-вторых, вес всех элементов из Ут возрастет ровно на (тМ, тМ), и, следовательно, внутри множества Ут они останутся попарно несравнимы, что и требовалось доказать. Теорема доказана. Из Теоремы 2.2 непосредственно вытекают упомянутые выше факты относительно двухкрнтериальных задач об остовном дереве и о назначениях [21,33,50,51]. Иначе говоря из Теоремы 2.2 непосредственно вытекает, что существуют индивидуальные двухкрите-рпальные задачи об остовном дереве, о назначениях, о рюкзаке для которых множество допустимых решений совпадает с полным множеством альтернатив. Действительно, например, для многокритериальной задачи о минимальном остовном дереве, т = \V\ — 1, а множество всех остовных деревьев является подмножеством множества Хт. Далее, исходя из конструктивных доказательств Теоремы 2.1 и ее следствия, легко построить такую положительную функцию с : Е — R?, что веса всех остовных деревьев будут попарно несравнимы.
Замечания о задачах о минимальном остовном дереве и о назначениях
В данном разделе будут приведены некоторые соображения о том, что если псевдополнномиальные алгоритмы, решающие данные задачи, и существуют, то они обещают быть не слишком простыми. Эти соображения основаны на том факте, что задачи о минимальном остовном дереве и о назначениях, в отличие от задачи о кратчайшем пути, не обладает свойством наследственности. То есть некоторый минимальный по Парето лес или паросочетанпе могут не содержать ни одного минимального по Парето подлеса или паросо-четания для двудольного графа меньшего размера. Для иллюстрации приведем следующие примеры: для задачи о минимальном остовном дереве рассмотрим граф G = {V, Е) на четырех вершинах, в котором существует мини мальный по Парето лес, каждая связная компонента которого содержит ровно 3 ребра и не содержащий ни одного минималь ного по Парето подлеса, каждая связная компонента которого имеет ровно 2 ребра. На множестве ребер Е = {еі2, еіз, ей, егз, 24 е34, } графа G определим функцию Cij = (ci(e;j),C2(ejj)) со следующими весами: Ci2 = (4,0), с13 = (10,10), с14 = (0,4), с23 = (10,10), с24 = (1,1), с34 = (2,2). Полученный граф изображен на рисунке 8 на стр. 40. Для данного графа минимальными по Парето лесами, каждая связная компонента которых содержит ровно 3 ребра, являются (СМ. piIC. 9 На СТр. 40) Следующие Леса {Єі2, Є24, Є34}, { 12, е , Є34І {еі4,Є24, ?34}. Минимальными по Парето деревьями, каждая связная компонента которых содержит ровно 2 ребра, (см. рис. 10 на стр. 40) в этом случае являются следующие леса {еі2,Є24}, {ен,Є24}? { ?24,?34}. Легко заметить, что лес {еі2, єн, Є34} не содержит ни одного минимального по Парето подлеса. Отметим, что аналогичный пример для графа на трех вершинах невозможен. для задачи о назначениях рассмотрим двудольный граф G = (V, U, Е) у которого \V\ = \U\ = 3, а множество ребер Е = = UJLi{(i n щ)щ {v\, щ)} U{(u2 «і), (из» u2)}.
На множестве ребер Е определим двумерную функцию су = (ci(v,-,Kj),C2(u,-,и,)) со следующими весами: сц = С22 = ?зз = (5,5), сіг = (15,15), сгі = (1,1), сз2 = (2,2), сіз = (3,3) (см. рис. 11 на стр. 41) Легко увидеть, что минимальным по Парето для данного графа G является следующее паросочетание {(иг, ui), (из, иг), (і ь из)} (см. рис. 12 на стр. 41). Не составляет труда убедиться, что Парето минимальными паросочетаниями размера 2 являются следующие графы: {(ui,ui),(u2,u2)}, {(щ, «і), («з, «з)}, {( 2, «г), («з, з)} (см. рис. 12 на стр. 41) Таким образом, в данных задачах затруднено использование для построения псевдополиномиальных алгоритмов идей метода динамиче где он с успехом может быть применен [34]. ассоциированных со всевозможными путями 7rst из узла s в узел t в графе G = (V,E), а через Pst множество Парето-минимальных элементов в Hst. Ниже рассматривается задача отыскания совокупности P = {((8,t),Pet):{81t)eVxV,8jkt}. В работе [29] для однокритериального случая приведен полиномиальный алгоритм (алгоритм Флойда-Уоршела), который находит длину кратчайшего пути для каждой пары различных узлов s,t в графе G. Алгоритм работает с матрицей расстояний D = {dij} размера V х V. В начале работы элементы матрицы принимаются равными длинам дуг графа G = (V, Е). В ходе работы алгоритма значения ячеек матрицы модифицируются. Ядром алгоритма является выполнение так называемой операции треугольника. Определение 3.1. Операцией треугольника для фиксированного узла к назовем последовательность действий: которые выполняются для всех i,j — 1,..., V, отличных от к. Эта операция для каждой пары і и j заменяет значение dij величиной dik + dkj, если она меньше. Легко видеть, что последовательно перебирая в качестве к все узлы графа, получим длину кратчайшего пути из пункта і в пункт j. Приведем теперь описание алгоритма для отыскания совокупности множеств Р = {{(s,t),P8t) : (s, ) Є VxV,s ф і) Парето-минимальных путей из s в t. ВХОД АЛГОРИТМА массивы V узлов и Е дуг графа G; массивы {сі(е), є Є Е} и {с2(е), є Є "}, задающие двумерную функцию неотрицательных весов. ВЫХОД АЛГОРИТМА: совокупность Р. В процессе работы алгоритма на каждом шаге строится матрица D = {d;j}, которая отличается от классического варианта [32]. Принципиальные отличия состоят в следующем: - во-первых, в качестве метки используется упорядоченная пара чисел Л = (ci,C2) или (оо,оо) ; - во-вторых, каждая ячейка d{j содержит массив меток Л.
AСмысл метки Л = (ci,C2), помещенной на к-ом шаге в массив ячейки djj, описывается следующими условиями: (a) существует путь 7Гу из пункта і в пункт j по узлам с номерами, меньшими или равными fc, вес (сі(7г ),С2(7г )) которого равен (сьс2); (b) не существует пути 7Г из пункта і в пункт j по узлам с номерами, не превосходящими /г, для которого выполнялось бы неравенство (сі{тг),с2(п)) Х. В начале работы алгоритма в элементы d{j матрицы D помещаются метки весов дуг графа G или (оо, ос), если дуги в графе нет. циклов, каждый из которых выполняется \V\ раз. Самый "верхний" цикл гарантирует просмотр всех пунктов в качестве фиксированного узла к; два других цикла обеспечивают выбор всех пар узлов 5, t. Внутри всех циклов находится операция "шаг", которая отыскивает Парето-мншшальные пути из s в t по узлам с номерами меньшими или равными к. Отметим, что операция "шаг" зависит от следующих данных: - текущего фиксированного пункта к; - от текущей пары узлов (s, ), для которой отыскиваем кратчайший путь по узлам с номерами, не превосходящими к. Рассмотрим подробнее процедуру "шаг", которая состоит из четырех процедур. Процедура 1. Формируется множество меток Лі, которое ассоциируется с множеством Hst для путей, содержащих узел к. Процедура 2. Формируется множество Лг, которое получается объединением массива dst и множества Ль Процедура 3. В множестве Лг определяется подмножество Лз С Лг всех Парето-миннмальных элементов. Процедура 4- Множество Лз ассоциируется с элементом dst матрицы D. ПРАВИЛО окончания работы алгоритма. Процесс завершается, когда к становится равным \V\. Сформированная к этому времени матрица D = {dij} служит выходом алгоритма. Другими словами, каждый элемент d матрицы содержит множество .Р -, то есть {((/, j),Pij)} является элементом совокупности Р (см. [42]) Доказательство. Докажем по индукции, что после операции "шаг" для А; = ко массив dst содержит веса всех Парето-минимальных путей из пункта s в пункт t по узлам с номерами, не превосходящими к. Для А о = 1 утверждение очевидно. Допустим, что предположение индукции верно для к = ко — 1, и рассмотрим операцию "шаг" для к = А о. После выполнения процедуры 1 получим множество меток, ассоциирующихся с путями из пункта s в пункт t, проходящих через узел с номером к. Процедура 2 гарантирует получения множества Лг, которое содержит
Многокритериальная задача о кратчайших путях для всех пар узлов графа
В работе [29] для однокритериального случая приведен полиномиальный алгоритм (алгоритм Флойда-Уоршела), который находит длину кратчайшего пути для каждой пары различных узлов s,t в графе G. Алгоритм работает с матрицей расстояний D = {dij} размера V х V. В начале работы элементы матрицы принимаются равными длинам дуг графа G = (V, Е). В ходе работы алгоритма значения ячеек матрицы модифицируются. Ядром алгоритма является выполнение так называемой операции треугольника. Определение 3.1. Операцией треугольника для фиксированного узла к назовем последовательность действий: которые выполняются для всех i,j — 1,..., V, отличных от к. Эта операция для каждой пары і и j заменяет значение dij величиной dik + dkj, если она меньше. Легко видеть, что последовательно перебирая в качестве к все узлы графа, получим длину кратчайшего пути из пункта і в пункт j. Приведем теперь описание алгоритма для отыскания совокупности множеств Р = {{(s,t),P8t) : (s, ) Є VxV,s ф і) Парето-минимальных путей из s в t. ВХОД АЛГОРИТМА массивы V узлов и Е дуг графа G; массивы {сі(е), є Є Е} и {с2(е), є Є "}, задающие двумерную функцию неотрицательных весов. В процессе работы алгоритма на каждом шаге строится матрица D = {d;j}, которая отличается от классического варианта [32]. Принципиальные отличия состоят в следующем: - во-первых, в качестве метки используется упорядоченная пара чисел Л = (ci,C2) или (оо,оо) ; - во-вторых, каждая ячейка d{j содержит массив меток Л. Смысл метки Л = (ci,C2), помещенной на к-ом шаге в массив ячейки djj, описывается следующими условиями: (a) существует путь 7Гу из пункта і в пункт j по узлам с номерами, меньшими или равными fc, вес (сі(7г ),С2(7г )) которого равен (сьс2); (b) не существует пути 7Г из пункта і в пункт j по узлам с номерами, не превосходящими /г, для которого выполнялось бы неравенство (сі{тг),с2(п)) Х. В начале работы алгоритма в элементы d{j матрицы D помещаются метки весов дуг графа G или (оо, ос), если дуги в графе нет. циклов, каждый из которых выполняется \V\ раз. Самый "верхний" цикл гарантирует просмотр всех пунктов в качестве фиксированного узла к; два других цикла обеспечивают выбор всех пар узлов 5, t. Внутри всех циклов находится операция "шаг", которая отыскивает Парето-мншшальные пути из s в t по узлам с номерами меньшими или равными к. Отметим, что операция "шаг" зависит от следующих данных: - текущего фиксированного пункта к; - от текущей пары узлов (s, ), для которой отыскиваем кратчайший путь по узлам с номерами, не превосходящими к. Рассмотрим подробнее процедуру "шаг", которая состоит из четырех процедур. Процедура 1. Формируется множество меток Лі, которое ассоциируется с множеством Hst для путей, содержащих узел к.
Процедура 2. Формируется множество Лг, которое получается объединением массива dst и множества Ль Процедура 3. В множестве Лг определяется подмножество Лз С Лг всех Парето-миннмальных элементов. Процедура 4- Множество Лз ассоциируется с элементом dst матрицы D. ПРАВИЛО окончания работы алгоритма. Процесс завершается, когда к становится равным \V\. Сформированная к этому времени матрица D = {dij} служит выходом алгоритма. Другими словами, каждый элемент d матрицы содержит множество .Р -, то есть {((/, j),Pij)} является элементом совокупности Р (см. [42]) Доказательство. Докажем по индукции, что после операции "шаг" для А; = ко массив dst содержит веса всех Парето-минимальных путей из пункта s в пункт t по узлам с номерами, не превосходящими к. Для А о = 1 утверждение очевидно. Допустим, что предположение индукции верно для к = ко — 1, и рассмотрим операцию "шаг" для к = А о. После выполнения процедуры 1 получим множество меток, ассоциирующихся с путями из пункта s в пункт t, проходящих через узел с номером к. Процедура 2 гарантирует получения множества Лг, которое содержит метки Парето-минимальных путей из s в t по узлам с номерами, меньшими чем fc, и метки всех путей, в которых присутствует узел к. Процедура 3 производит выбор из множества, полученного в результате процедуры 2, всех Парето-минимальных элементов. Следовательно, в полученном множестве содержатся веса Парето-минимальных путей из s в t по узлам с номерами, не превосходящими к. Процедура 4 ассоциирует множество, полученное в результате процедуры 3, с элементом dst. Теорема доказана. Для доказательства утверждения обозначим через S сумму числовых параметров, то есть сумму весов всех его дуг. Работа алгоритма заключается в выполнении операции "шаг" У3 раз. Смысл операции "шаг" заключается в формировании элементов d матрицы D. Очевидно, что число элементов в d не превосходит S. Следовательно, на формирование одного элемента d требуется не более 52 арифметических операций. Значит, трудоемкость всего алгоритма составляет 0(F3S2). Теорема доказана. Одной из классических дискретных по праву считается»задача о Рюкзаке. Это обуславливается тем фактом, что при простом множестве допустимых решений задача является NP-полной. Однако популярность данной задачи объясняется существованием для нее алгоритма с псевдополиномиальной временной сложностью. Это обстоятельство позволяет на практике при разумном ограничении на числовые параметры решать задачу за приемлемое (полиномиальное) время. Стандартную постановку задачи о Рюкзаке можно найти в монографии [27]. Заданы положительные числа В\, B i и множество Е = {ei,.. . еп} на котором определены размер с"і(е,) и стоимость С2(е,) для каждого { Є Е.
Требуется выяснить, существует ли такое подмножество А[ С Е, что Легко заметить, что данная задача является задачей двухкрите-риальнон дискретной оптимизации с векторной целевой функцией с= (ci(et-),c2(e,-)). Более общим случаем задачи о Рюкзаке является следующая задача. Задача А. Заданы множество Е — {ei,.. .еп}, на котором определена к—мерная функция с = С(ЄІ) и вектор С Є Rk. Требуется выяснить, существует ли непустое подмножество А\ С Е, для которого выполняется следующее условие: В случае k = 1 Задача А является полиномиально разрешимой с помощью тривиального алгоритма. У сформулированной задачи множество допустимых решений остается по-прежнему простым. Данный характер множества связан с тем фактом, что выбор элементов из Е происходит без учета каких-либо связей между элементами из Е. Легко заметить, что сформулированная выше задача NP-полна. К ней за полиномиальное время можно свести задачу о Рюкзаке. Так как в качестве векторной целевой функции определяется с = (ci(et), —сг(е,-),0,.. .,0), а в качестве вектора оценок С = (Di,— D2, 0,... ,0). Отметим, что в случае положительной векторной целевой функции для Задача А существует тривиальный алгоритм с полиномиальной временной сложностью. Не менее важной, но менее изученной является следующая постановка задачи о Рюкзаке. Задача В. Заданы множество Е = {ei,.. .еп}, на котором определена к—мерная функция с = с(ег-), вектор С Є Rk и натуральное т. Требуется выяснить, существует ли подмножество АСЕ, для которого выполняются следующие условия: В случае k = 1 Задача В является полиномиально разрешимой с помощью тривиального алгоритма. Ниже будет показано, что при к 1 Задача В становится NP-полной. Содержательной версией рассматриваемой задачи при к — 2 мо жет служить, например, следующая ситуация. Имеется т вакансий, требующих одинаковых навыков и умений, и множество претенден «. тов. Каждого претендента можно оценить двухмерным вектором с = (сі, С2); где с\ - требуемая претендентом зарплата, c i - стоимость его обучения. Можно ли так выбрать т претендентов, чтобы суммарная зарплата на содержание всего коллектива не превосходила заданной величины Сі, а суммарная стоимость обучения была бы не больше, чем Сг Предварительно рассмотрим вспомогательную задачу. Задача С. Заданы множество Р — {pi,.. .,pq}, натуральное число т, и для каждого элемента pi Є Р определен вес w{pi) 0. , Требуется выяснить, существует ли такое подмножество S множества Р, для которого Доказательство. Легко убедиться, что Задача С входит в класс NP. Это следует из того, что недетерминированному алгоритму нужно только угадать подмножество 5 и за полиномиальное время проверить, что все его элементы принадлежат множеству Р и выполняются следующие условия:
Линейные разделяющие алгоритмы
В этом разделе рассмотрим иной метод, позволяющий модифицировать алгоритмы для однокритериального случая в алгоритмы лексикографической оптимизации. В отличие от метода линейной свертки временная трудоемкость модифицированного предлагаемым методом алгоритма возрастает не более чем в к раз, где к - количество критериев. Обычно множество допустимых решений X, фигурирующее в задаче оптимизации, удается интерпретировать как множество векторов m-мерного пространства Rm\ при этом функция цели / является линейной по х Є X. Проиллюстрируем указанное утверждение с помощью задачи коммивояжера. Задан полный ориентированный граф G = (V, Л), узлы (города) которого занумерованы: V = {1,...,п}; на множестве А его дуг определена действительная функция с : А — R; c(i,j) = C{j— вес дуги (г, j) А. Задача коммивояжера заключается в отыскании гамилыпонова контура, суммарный вес дуг которого минимален. Положим т = \А\ = п(п — 1) и рассмотрим Rm— вещественное евклпдовое пространство, выбрав произвольно взаимно однозначное соответствие между множеством А и множеством номеров координат точек. Для каждого гамильтонова контура в графе G рассмотрим его характеристический вектор в Rm, положив равными единице те координаты, для которых соответствующие дуги входят в контур, остальные - равными нулю. Обозначим через Хп множество всех таких векторов, АГ„ = (п — 1)!. В этих обозначениях сформулированная выше задача коммивояжера с вектором с весов дуг превращается в задачу минимизации на множестве Хп линейной функции (скалярного произведения): Под термином "задача коммивояжера" подразумевается массовая задача. Массовый характер ее обусловлен множественностью значений двух разнородных параметров - числа городов п и функции весов с. С учетом сказанного Задачу 3 можно сформулировать следующим образом. Задано конечное множество X С Ят с функцией цели / : X — Rk,f(x) = (/i(x),..., Д(л:)), где fi(x) = (с,-,х). Требуется найти такой х Є А", что для любого х Є X в лексикографическом смысле выполняется неравенство f(x ) f(x). Большинство задач комбинаторной оптимизации допускают указанное описание.
Широкий класс алгоритмов однокритериальной оптимизации образуют те из них, которые используют линейные сравнения для решения задачи. Такие алгоритмы принято называть линейными разделяющими алгоритмами, формальное описание которых, по-видимому, впервые было приведено в работе [39], (см. также [40]). Напомнил! определение линейного разделяющего алгоритма для од-нокрнтериального случая. Определение 4.1. Линейным разделяющим алгоритмом (деревом.) задачи X, X С Rm называется ориентированное дерево, обладающее следующими свойствами: 1) в каждый узел, за исключением одного, называемого корнем, входит ровно одна дуга; дуг, входящих в корень, нет; 2) для каждого узла либо имеются две выходящих из него дуги, либо таких дуг нет вообще; в первом случае узел называется внутренним, во втором - внешним, или листом; 3) каждому внутреннему узлу соответствует некоторый линейный функционал (вектор) w в Rm; 4) каждому листу соответствует некоторый элемент множества X ; 5) каждой дуге d соответствует число sgnd, равное 1 либо -1; две дуги, выходящие из одного узла, имеют различные значения; 6) для каждой цепи W = w\diW2 l2...widix, соединяющей корень и лист ( в обозначении цепи перечислены соответствующие ее узлам векторы; дуга di выходит из узла w i — 1,...,J), и для любого с Є Rm из неравенств (wi,c)sgndi 0, і = 1,...,7, следует включение, с Є S(x), где S(x) = {с Є Rm : (с,х) (с}у), при любом у Є X}. Работа алгоритма заключается в последовательном применении к с линейных функционалов, при этом выбор на і-ом шаге функционала wi происходит в зависимости от знака линейной формы (ш;_і, с), где « ;_! - функционал, используемый на предыдущем (і-І)-ом шаге. Условно процесс решения индивидуальной задачи представляет собой последовательное прохождение некоторой цепи W в бинарном дереве, описываемом определением 4.1. Окончанию процесса соответствует переход в узел, являющийся листом. Элемент х Є X соответствующий этому листу, является решением индивидуальной задачи, что определяется условием б) в определении 4.1. Заметим, что линейными разделяющими алгоритмами являются, в частности, алгоритм Мура-Дейкстры, решающий задачу о кратчайшем пути, жадный алгоритм для задачи о минимальном остов-ном дереве, венгерский алгоритм для задачи о назначениях и многие другие известные алгоритмы [40]. Опишем модификацию линейного разделяющего алгоритма для лек сикографической Задачи 3.
Структурно модифицированный алгоритм представляет бинарное дерево, совпадающее с тем, которое фигурирует в определении 4.1. Модификация заключается в том, что все сравнения, используемые в алгоритме, выполняются в лексикографическом смысле. С учетом этого функционирование модифицированного алгоритма решения индивидуальной лексикографической задачи происходит аналогично сказанному выше для однокритериального случая. Пусть / = (CI,...,Q) набор m-мерных векторов, определяющих к-мерную целевую функцию индивидуальной лексикографической задачи. Последовательно, начиная с корня, осуществляется применение функционалов, соответствующих вершинам линейного разделяющего алгоритма, к / и лексикографическое сравнение результата с нулевым вектором. В зависимости от этого происходит переход к очередной вершине. Работа алгоритма заканчивается после перехода в висячую вершину; соответствующий этой вершине элемент х Є X объявляется решением индивидуальной лексикографической задачи. Уточним характер вычислений на отдельном шаге алгоритма. Пусть w - функционал, соответствующий і-ой вершине линейно разделяющего дерева, тогда i-ый шаг имеет следующий вид. Применяем вначале функционал w к с\ и сравниваем результат с нулем. Если (w, С\) ф 0, то данный шаг заканчивается и происходит переход по одной из выходящих дуг в зависимости от знака (tt , с\) в следующий узел. Если
Похожие диссертации на О сложности некоторых многокритериальных дискретных задач
