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

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

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

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

5.5. Статистически эффективные алгоритмы

На основании теоремы 5.1 методы решения многокритериальных задач можно использовать для интервальных задач. Среди методов отыскания паретовских оптимумов наиболее распространенными являются алгоритмы линейной свертки критериев (ЛСК) вида: , где . Если все критерии ,  являются минимизируемыми (максимизируемыми) и принимают положительные значения  , то элемент  является паретовским оптимумом, если на нем значение ЛСК  достигает минимума (максимума). Известно [2], что многокритериальные задачи на графах неразрешимы с помощью алгоритмов ЛСК. Вместе с тем всякая индивидуальная - критериальная задача разрешима с помощью алгоритма ЛСК, если она обладает следующим свойством : «ПМА этой задачи состоит из одного элемента, т.е. мощность ». В частности, если какая-либо индивидуальная интервальная задача оптимизации на графах с ИЦФ (5.1)-(5.2) обладает свойством , то для соответствующей 2- критериальной задачи с ВЦП (5.3)-(5.4) существует такой вектор , при котором линейная свертка критериев (5.4) достигает требуемого экстремума на элементе , причем .

Представленную выше задачу  покрытия графов  звездами из 1-элементного множества ТГ  рассмотрим при условии, которое в некотором смысле является полярно противоположным условию (5.17), а именно, множество , в котором  – это звезда с числом вершин,

 , (5.18)

где  – это независящая от  константа и  кратно .

Предлагаемый алгоритм  состоит из следующих этапов.

Этап 1. В данном -вершинном графе  произвольным образом  выделяем подмножество  центров звезд искомого покрытия, , , . Оставшееся подмножество  обозначаем через , , . Удалив из графа  все ребра, кроме ребер вида , , , получаем 2-дольный граф . Далее подмножество  произвольным образом разбиваем на  равномощных подмножеств ,  и индуцируем в  2-дольные подграфы  с равномерными долями ,, . В этих подграфах интервальные веса  ребер  заменяем соответственно на числа , .

Этап 2. Для определенности полагаем, что ИЦФ (5.1)-(5.2) является максимизируемой (). В каждом подграфе  находим оптимальное совершенное паросочетание  с помощью подходящего алгоритма [65]. Ребра этих паросочетаний помечаем звездочкой *: , .

Этап 3. По номерам вершин ,  отмеченных ребер  выделяем в исходном графе  соответствующие ребра, которые также помечаем звездочкой. По определению этапа 2 помеченные ребра в исходном графе  образуют реберное покрытие этого графа -вершинными звездами, т.е. по завершению этапа 3 получаем допустимое решение  задачи  на графе .

Введем необходимые обозначения:

·  – множество всех - вершинных 2-дольных графов , , у которых ребра взвешены интервалами  из множества , , где интервал  является максимальным, т.е. для него выполняется бинарное отношение предпочтения лучше  для всех  (см. определение 5.1);

·  – 2-дольный - вершинный случайный граф [12], [44] с равномощными долями , , в котором для всякой пары вершин , ,  ребро  появляется с вероятностью ;

· сколь угодно медленно растущая функция от , причем  при , .

Для множества  и случайного графа  из теоремы 4.17 [44] вытекают следствия, которые сформулируем в виде следующих утверждений.

Утверждение 5.1. Если получаемые на выходе этапа 2 невзвешенные графы ,  рассматривать в качестве реализации случайного графа , то каждый из них почти всегда, т.е. с вероятностью ,  при  содержит совершенное паросочетание при условии, что значение

 .(5.19)

В терминологии [44] свойство «граф содержит совершенное паросочетание» является „монотонным по ребрам”. Для всякого монотонного по ребрам свойства в статье [44] установлена взаимосвязь между достаточными условиями наличия этого свойства «почти всегда» в реализациях случайного графа и «для почти всех графов» из множества вида . В силу этой взаимосвязи с учетом (5.19) является справедливым

Утверждение 5.2. В случае выполнения неравенства

 (5.20)

почти все графы  содержат такие совершенные паросочетания, у которых каждое ребро взвешено максимальным интервалом .

С учетом неравенства (5.18) количество получаемых на выходе этапа 2 графов  ограничено сверху константой . Тогда из утверждений 5.1 и 5.2 следует, что являются справедливыми следующие

Утверждение 5.3. В случае выполнения условия (5.19) почти всегда, т.е. с вероятностью ,  при  каждая из  реализаций случайного графа  содержит совершенное паросочетание. В случае выполнения неравенства (5.20) почти все 2-дольные графы , получаемые на выходе этапа 2, содержат также совершенные паросочетания, у которых ребра взвешены максимальными интервалами .

С учетом равенства  и соотношения (5.18) условие (5.20) принимает вид

.(5.21)

Тогда из утверждения 5.4 вытекает, что является справедливой

Теорема 5.5. Если ребра графов  взвешены интервалами из множества , то при выполнении неравенств (5.18), (5.21) алгоритм  почти всегда находит для этих графов покрытие - вершинными звездами, представляющее собой одноэлементное ПМА.

Согласно общепринятому определению в условиях теоремы 5.5 алгоритм  является статистически эффективным, так как его вычислительная сложность ограничена сверху полиномом третьей степени от  [65].