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

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

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

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

5.3. Оценки вычислительной сложности

Рассмотрим представленную в п.5.2 формулировку интервальной задачи на графах. Используя понятие "задача", как предикатную переменную, обозначаем его символом  в смысле понятия "массовая задача", которое предложено в книге [27]. Если эта интервальная задача рассматривается как "индивидуальная задача" [27] на конкретном интервально взвешенном графе , то обозначим ее символом ; ее МДР, паретовское множество и ПМА обозначим соответственно символами ,  и .

Пусть  – множество всех (невзвешенных) - вершинных графов.

Определение 5.6. Интервальная задача  с ИЦФ (5.1)-(5.2) называется полной (обладает свойством полноты), если для каждого ее МДР , ,  существуют такие веса , , что выполняются равенства

 .(5.5)

Согласно [27] мы называем интервальную задачу труднорешаемой, если не существует такого алгоритма, который гарантирует нахождение ПМА с полиномиальной вычислительной сложностью. Мощность ПМА  можно рассматривать как нижнюю оценку вычислительной сложности его нахождения. Это означает, что интервальная задача является труднорешаемой в случае, если максимальная мощность ПМА растет экспоненциально с ростом размерности задачи, т.е. с ростом размерности графов, где максимум берется по всем графам .

Как правило, вычисление мощности МДР представляет меньшую трудность по сравнению с вычислением мощности ПМА. Если рассматриваемая задача обладает свойством полноты, то с учетом равенств (5.5) снижается сложность нахождения максимальной мощности ПМА. Представляет интерес найти нетривиальные условия, при выполнении которых рассматриваемая интервальная задача на графах  обладает свойством полноты. С этой целью рассмотрим какое-либо множество , состоящее из ТГ , .

Определение 5.7. Множество ТГ , , называется однородным, если мощности множеств вершин  и ребер  одинаковы для всех ТГ из  и , .

В определении 5.7 свойство однородности не требует, чтобы величины  и  являлись константами, которые не зависят от размерности графа . Допускается, что значения  и  могут быть растущими функциями от . Например, для задачи об остовных деревьях на -вершинных графах множество ,  состоит из всех попарно неизоморфных -вершинных деревьев ( – мощность множества всех таких деревьев) и, при этом, для всех ТГ  выполняются равенства , , . Отметим также, что все 1- элементные множества ТГ вида  являются однородными.

Рассмотрим два интервала  и  на действительной прямой.

Определение 5.8. Бинарное отношение  строгого включения  означает, что выполняются следующие строгие неравенства:

 , .(5.6)

Интервальный вес  называем положительным, если выполняется неравенство . Положительные веса присущи большинству реальных задач дискретной оптимизации.

Теорема 5.2. Всякая интервальная задача на графах с ИЦФ (5.1)-(5.2) является полной в случае, если ее множество ТГ является однородным.

Доказательство. Сначала отметим, что интервалы  и  являются несравнимыми, если для них выполняются неравенства (5.6). Идея доказательства теоремы 5.2 состоит в следующем: ребра какого-либо графа  взвешиваем попарно несравнимыми интервалами; значения этих весов можно определить таким образом, что для всякой пары  значения ИЦФ  и  представляют собой несравнимые интервалы, в силу чего рассматриваемая индивидуальная задача на графе  является полной (см. определение 5.6).

Рассмотрим теперь задачу на графах  с ИЦФ (5.1)-(5.2), для которой множество ТГ ,  является однородным. Тогда из определения 5.7 вытекает, что для каждого графа  все его допустимые решения  содержат одинаковое количество ребер:

 , ,

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

 , ,(5.7)

, .(5.8)

Рассмотрим произвольную пару допустимых решений , , в которых номера ребер множеств ,  образуют соответственно множества , , где . Для этих решений с учетом (5.7) и (5.8) вычислим значения ИЦФ (5.1)-(5.2):

 , ,(5.9)

где

 , ,(5.10)

,  ,(5.11)

где константа .

Рассмотрим множества  и , выделим в них максимальные элементы , . Поскольку  и , то , в силу чего . Пусть имеет место строгое неравенство , тогда с учетом равенства мощностей  для значений (5.10) и (5.11) выполняются следующие соотношения:

 .(5.12)

Сравнивая (5.12) и (5.6), согласно определению 5.8 можем утверждать, что для ИЦФ (5.1)-(5.2) ее интервальные значения (5.9) являются несравнимыми. Таким образом, с учетом произвольного выбора графа  и  получаем, что согласно определения 5.8 и неравенств (5.12) рассматриваемая интервальная задача является полной.

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

Рассматривая класс однородных множеств ТГ , условимся нумеровать их индексом , т.е. мы рассматриваем класс . В терминологии [27] это означает, что класс  определяет собой класс массовых задач на графах. Например, в [68] значения  соответствуют следующим задачам:

 – задача о совершенных паросочетаниях;

– задача об остовных деревьях;

 – задача коммивояжера;

 – задача покрытия графа звездами одинаковой степени, т.е. , где  – - вершинная звезда, где  кратно . Для всякого множества ТГ при фиксированном значении  можно вычислить максимум мощности МДР . Например, в [83] мощность дизъюнктивных форм имеет оценку , где  размерность матрицы,  – минимальное число единиц в строке. В [68] ,  этот максимум определяется следующими формулами:

 , , .(5.13)

Исходным решением интервальной задачи оптимизации на графах является ПМА (см. определение 5.3), более точно, перечисление всех элементов ПМА, т.е., представление каждого элемента  в явном виде [3], [30]. С учетом (5.13) это означает, что для представленных выше задач проблема нахождения ПМА является труднорешаемой [27] или (используя терминологию [2]) она имеет экспоненциальную вычислительную сложность. Заключительному следствию из теоремы 5.2 предпошлем два замечания. Во-первых, если для двух множеств ТГ  и  выполняется строгое включение , то для всякого графа  выполняется (вообще говоря, нестрогое) включение . Во-вторых, для всех известных задач оптимизации на графах [1], [2], [3], [5], [7], [27], [65], [87] мощность МДР  растет экспоненциально с ростом  в случае, когда  – полный граф. С учетом этих замечаний из теоремы 5.2 вытекает

Следствие 5.1. Для известных однородных множеств ТГ  соответствующие задачи оптимизации на графах с ИЦФ (5.1)-(5.2) являются трудно разрешаемыми.

Рассмотрим общий случай, когда граф  и множество ТГ  являются произвольными, т.е. , а  не является однородным в смысле определения 5.7 и, кроме того, веса ребер графа  могут быть и отрицательными, в частности, .

Лемма 5.1. Для всякой пары "граф " множество ТГ , для которой является непустым МДР , существуют такие веса  ребер , что каждая пара допустимых решений  является несравнимой по значению ИЦФ (5.1)-(5.2).

Доказательство. По аналогии с (5.7), (5.8) перенумерованные индексом , , ребра  взвесим интервалами следующего вида: , где , . Для каких-либо допустимых решений  в паре множеств ,  определим максимальный номер  такой, что  принадлежит одному из этих множеств (для определенности будем полагать, что ) и не принадлежит другому (). Из того, что  вытекает выполнение строгих неравенств  или, что то же самое, выполнение строгого включения  (см. определение 5.8). Это включение является утверждением леммы 5.1 согласно определению 5.1 и с учетом произвольного выбора пары .

Лемма 5.1 доказана.

Согласно определению 5.6, всякая индивидуальная задача оптимизации на графах является полной в случае, если ее МДР является пустым или состоит из единственного элемента. Тогда из леммы 5.1 следует, что является справедливой

Теорема 5.3. Всякая задача оптимизации на графах  с произвольными интервальными весами и ИЦФ (5.1)-(5.2) является полной для любого множества ТГ.

Из теоремы 5.3 вытекает

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