Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Дискретная оптимизация и моделирование в условиях неопределенности данных

Перепелица В. А., Тебуева Ф. Б.,

3.5.3. Вычислительная сложность многокритериальных задач

Математическая постановка многокритериальной задачи об остовном состоит в следующем. Для данного графа  множество всех его остовных деревьев  представляет собой множество допустимых решений (МДР), на котором определена векторная целевая функция (ВЦФ)

 ,(3.15)

которая состоит из критериев

 , , (3.16)

вида (3.9)-(3.12) и определяет собой паретовское множество . Искомым является полное множество альтернатив (ПМА) . Подмножество  называется ПМА, если его мощность  минимальна и при этом выполняется равенство , где .

Анализу вычислительной сложности нахождения ПМА для многокритериальных задач об остовных деревьях предпошлём следующий иллюстративный пример. Рассмотрим полный 3-вершинный граф (треугольник) , , в котором пары весов ,  его ребер  имеют следующие значения: , ; ; , , МДР  состоит из остовных деревьев , , которые определяются следующими множествами ребер: , , . Пусть на этом МДР определена ВЦФ

 ,(3.17)

состоящая из минимизируемых (максимизируемых) весовых критериев (3.9). Для вышеуказанных значений весов эта ВЦФ принимает следующие значения: , , . Очевидно, что для рассматриваемой индивидуальной задачи об остовных деревьях её ПМА и ПМ совпадают с МДР:

 .(3.18)

В терминологии [30] равенство (3.18) означает, что рассматриваемая индивидуальная задача обладает свойством полноты. Если массовая задача (в понятиях [27]) об остовных деревьях является полной, то максимальная мощность искомого ПМА равна , . Нижняя оценка вычислительной сложности нахождения ПМА полной задачи растет экспоненциально с ростом её размерности. С учётом потенциально возможной труднорешаемости многокритериальных задач, особый интерес представляет выявление таких видов ВЦФ (3.15)-(3.16), когда нахождение ПМА имеет полиномиальную вычислительную сложность.

Рассмотрим 2-критериальную задачу об остовных деревьях с ВЦФ (3.17), которая состоит из критерия MINSUM (3.9) и критерия MINMAX (3.10):

 , .(3.19)

Является справедливой следующая

Теорема 3.2. Задача об остовных деревьях с ВЦФ (3.17), (3.19) разрешима с полиномиальной вычислительной сложностью, которая не превосходит .

Доказательство. Пусть в данном графе  каждому ребру  приписаны два веса , . Тогда по аналогии с (3.13) занумеруем эти ребра в порядке убывания (невозрастания) второго веса:

 , .

Область значений этих весов представим в виде упорядоченного множества

 , ,(3.20)

где , . С учётом последовательности (3.20) через  обозначим такой подграф данного графа , который получен в результате удаления из  всех таких ребер , у которых второй вес . Выделим такое значение , что  является связным, а  не является связным.

В последовательности подграфов

 (3.21)

для каждого ребра  пару весов ,  заменим на их свертку

 .(3.22)

Применив к каждому подграфу последовательности (3.21) алгоритм Прима, получим последовательность оптимальных (для подграфов , , которые 1- взвешены свёрткой (3.22)) остовных деревьев

 .(3.23)

В контексте доказательства теоремы 3.2 рассматриваем значение свертки (3.22), которое определено таким образом, что вклад второго веса  всякого ребра в значении второго критерия  представляет собой дробь из полуинтервала . Для всякого остовного дерева из (3.23) это соотношение обеспечивает оптимум по первому критерию  и при этом неулучшаемость значения второго критерия  (3.19) при сохранении оптимального значения . Таким образом, последовательность (3.23) представляет собой последовательность элементов из ПМ  (возможно с повторением). С учетом определения последовательности (3.20) и конструктивного определения последовательности (3.23) можно утверждать, что в ПМ не найдется элемента  такого, что значение  не принадлежит области  значений оптимумов (3.23). Следовательно, последовательность (3.23) содержит ПМА  рассматриваемой задачи с ВЦФ (3.17), (3.19). Верхняя оценка  нахождения этого ПМА получается по аналогии с алгоритмом , относящемся к теореме 3.1. Эта оценка вытекает их анализа трудоемкости построения последовательности (3.21) и проверки на связность её графов.

Теорема 3.2. доказана.

Рассмотрим теперь такие ВЦФ (3.17), в которых первый критерий  является весовым вида (3.9) или (3.10), а второй критерий  является комбинаторным вида (3.11) или (3.12). Используя комбинаторный критерий в виде ограничения (количество вариантов этого ограничения не превосходит (), получаем, согласно примечания 3.6, сведение рассматриваемой задачи к NP-трудной задаче [27]. Таким образом является справедливой

Теорема 3.3. Если ВЦФ 2-критериальной задачи об остовных деревьях состоит из критерия весового вида и комбинаторного критерия степени или диаметра, то проблема нахождения ПМА этой задачи является NP-трудной.

Осуществим теперь обоснование одного достаточного условия, при выполнении которого многокритериальная задача об остовных деревьях является полной в том смысле, что для всякого связного n-вершинного графа существует такое -взвешивание,  его ребер, при котором имеет место совпадение ПМА, ПМ и МДР (3.18).

Лемма 3.1. Многокритериальная задача об остовных деревьях обладает свойством полноты, если её ВЦФ (3.15) содержит пару критериевMINSUM или MAXSUM.

Доказательство. Рассмотрим какой-либо связной -вершинный граф . Если мощность его МДР , то свойство полноты (3.18), очевидно, выполняется. При  осуществим 2- взвешивание ребер  следующим образом. Сначала перенумеруем их индексом , , т.е. , после чего вычислим их веса ,  следующим образом:

 , , ,(3.24)

где . Отмечая равенство количества ребер остовного дерева

  ,(3.25)

из (3.24) и (3.25) получаем одинаковые, т.е. независящее от выбора остовного дерева  значение сумм

 , .(3.26)

Перенумеруем индексом  остовные деревья данного графа и рассмотрим для какой либо пары ,  разность . Для всякой такой пары выполняются соотношения

 , .(3.27)

В силу определения (3.24) и равенств (3.27) максимальные элементы множеств  и  не совпадают. Пусть максимальный элемент объединения () принадлежит . Тогда из (3.24)-(3.27) вытекают строгие неравенства , , которые означают, что всякая пара является векторно несравнимой по ВЦФ (3.17), то есть выполняется свойство полноты (3.18).

Лемма 3.1 доказана для числа критериев MINSUM . Аналогичным является её доказательство и в случае, когда ВЦФ состоит из критериевMAXSUM. Отсюда вытекает и полное доказательство этой леммы в силу того, что если пара  является векторно несравнимой по ВЦФ (3.17), то эта несравнимость остаётся и в случае пополнения этой ВЦФ другими критериями. Лемма 3.1 доказана полностью.

Примечание 3.7. При доказательстве леммы 3.1 существенным является то, что все допустимые решения  задачи об остовных деревьях имеют одинаковое, т.е. независящее от элементов  количество ребер:

 , .(3.28)

Величина  зависит только от размерности задачи, для остовного дерева . Тогда лемма 3.1 оказывается справедливой для всякой задачи, удовлетворяющей условию (3.28), например, для задач коммивояжера, о совершенных паросочетаниях и др.

Из леммы 3.1 вытекает, что для многокритериальной задачи об остовных деревьях максимальная мощность искомого ПМА на полном -вершинном графе согласно [50] достигает значения  (экспоненциальное возрастание от размерности задачи), если её ВЦФ содержит не менее двух весовых критериев вида (3.9). Отсюда является справедливой

Теорема 3.4. Многокритериальная задача об остовных деревьях является труднорешаемой, если её ВЦФ содержит хотя бы пару критериевMINSUM или MAXSUM.

Примечание 3.8. Для отмеченных в примечании 3.7 многокритериальных задач, удовлетворяющих условию (3.28), также являются справедливыми утверждения об их труднорешаемости, аналогичные теореме 3.4.