Примеры сетевых топологий
Введение к сложности анализа надежности
Вычислительные задачи, которыми чаще всего занимаются специалисты по численным методам, можно разделить на две группы: задачи распознавания, такие как определение, содержит ли граф гамильтонов цикл, и задачи оптимизации, такие как нахождение минимальной стоимости маршрута коммивояжера. Задачи анализа надежности в корне отличаются от двух последних. При вычислении надежности приходится учитывать не только топологию сети, но и потоки данных в ней. Следовательно, анализ их сложности включает соображения, которые связаны, но отличаются от механизма, используемого при рассмотрении проблем распознавания и оптимизации: классы P, NP и NP-полный.
Чтобы наиболее простым образом свести задачи анализа надежности к более знакомым комбинаторным проблемам, рассмотрим частный случай задачи анализа надежности, которая возникает, когда все индивидуальные компоненты надежности равны, т.е. pi для всех i. В этом случае Rel(SBS,p) можно записать в виде полинома по степеням p:
Rel(SBS,p)=
Этот полином является полиномом надежности. Задача по его вычислению называется задачей анализа функциональной надежности, где в качестве входных данных используется представление SBS, а на выходе получается вектор {Fi}.
Общий член в полиноме надежности Fipm-i(1-p)i представляет собой вероятность того, что работает ровно m-i компонентов сети и функционирует система в целом. Таким образом, можно интерпретировать Fi так:
Fi=|{S:|S|=i и ?(T-S)=1}|.
Отсюда видно, что проблема определения коэффициентов Fi является задачей подсчета. Результатом задачи по распознавания гамильтоновых контуров может быть либо “Да”, если в графе содержатся контуры, либо “Нет”, а результатом задачи подсчета гамильтоновых контуров в графе является число таких контуров. NP и NP-полный являются классами задач распознавания. Классы, соответствующие задачам подсчета, обозначаются #P и #P-полный. Очевидно, что любая задача подсчета, по крайней мере, не проще чем соответствующая ей задача распознавания. Например, если известно число гамильтоновых контуров в графе, то не составит труда ответить на вопрос - «Число гамильтоновых контуров больше нуля?».
Получается, что любая разновидность задачи подсчета из NP-полного класса часто является #P-полной. С другой стороны, существуют примеры задач распознавания, у которых время решения является полиномиальным, а их счетные аналоги относятся к NP-полному классу. Например, задача поиска точного соответствия в двудольном графе имеет полиномиальное время решения, а задача поиска точного числа полных соответствий в двудольном графе является #P-полной. Чтобы не усложнять этот обзор, мы не будем подробней вдаваться в проблему сложности, а будем указывать, относится ли она к полиномиальному классу или классу NP сложности.
Многие практические приложения требуют использования моделей с разной надежностью компонентов. В таких моделях все вероятности являются рациональными числами. Мы формулируем проблему анализа рациональной надежности следующим образом. В качестве входной информации используется представление и для каждого компонента i пара целых чисел ai, bi. На выходе получается пара целых чисел a и b таких, что a/b = Rel(SBS,{ai/bi}).
Мы начинаем с установления того, что, если конкретный анализ функциональной надежности является NP-сложными, тогда соответствующий анализ рациональной надежности является NP-сложными.
Утверждение 2.2. Для любой задачи анализа рациональной надежности r-Rel и соответствующей ей задачи анализа функциональной надежности, f-Rel за полиномиальное время может быть сведена к r-Rel.
Доказательство: В f-Rel входит представление функции SBS. На выходе необходимо получить набор коэффициентов {Fi} полинома надежности. Чтобы преобразовать f-Rel в r-Rel выберем m+1 рациональное значение вероятности 0 < p0 < p1 < ... < pm < 1. Для j= 0,1,…,m обозначим решения соответствующей задачи анализа рациональной надежности как rj = Rel(SBS,pj), где все компоненты надежности установлены равными pj. Теперь мы можем записать систему уравнений:
Решив m+1 задачу анализа рациональной надежности, найдем pj и rj. Получим систему из m+1 линейного уравнения с m+1 неизвестными Fi.
Коэффициенты матрицы имеют свойство матрицы Вандермонде и, следовательно, является невырожденной, таким образом, можно вычислить значения Fi.
Исследуем более детально вид полинома надежности для функций SCBS. Если задана SCBS, мы определяем значения:
m = число компонентов в системе
с = мощность набора минимального разреза
nc = число наборов разрезов с минимальной мощностью
l = мощность минимального набора путей.
nl = число наборов путей с минимальной мощностью
Заметим сразу, что коэффициенты полинома надежности обладают следующими свойствами:
Fi=nl для i=m-l,
Fi=0 для i>m-l
Эти свойства означают, что, вычисляя полином надежности, мы легко определяем важные свойства SCBS функции. Например, исследовав полином надежности, мы сможем определить размер набора разрезов с минимальной мощностью. Таким образом, если задача распознавания набора разрезов с минимальной мощностью имеет сложность NP, то задача вычисления полинома надежности тоже имеет сложность NP. Из цепочки наших рассуждений следует:
Теорема 2.3. Для любой SCBS, если выполняется одно из следующих пяти условий, то задачи анализа функциональной и рациональной надежности являются NP сложными:
1. Задача распознавания минимального набора путей имеет сложность NP.
2. Задача подсчета минимального набора путей имеет сложность NP
3. Задача распознавания минимального набора разрезов имеет сложность NP
4. Задача подсчета минимального набора разрезов имеет сложность NP
5. Задача нахождения общих коэффициентов в полиноме надежности имеет сложность NP.
Доказательство: Результат анализа функциональной надежности следует из того, что выходные значения каждой из пяти задач могут быть получены из полинома надежности. Результат для проблемы рациональной надежности следует из утверждения 2.2. Применим построенную нами систему к задаче исследования сетевой надежности.
