Примеры сетевых топологий


Введение к сложности анализа надежности


Вычислительные задачи, которыми чаще всего занимаются специалисты по численным методам, можно разделить на две группы: задачи распознавания, такие как определение, содержит ли граф гамильтонов цикл, и задачи оптимизации, такие как нахождение минимальной стоимости маршрута коммивояжера. Задачи анализа надежности в корне отличаются от двух последних. При вычислении надежности приходится учитывать не только топологию сети, но и потоки данных в ней. Следовательно, анализ их сложности включает соображения, которые связаны, но отличаются от механизма, используемого при рассмотрении проблем распознавания и оптимизации: классы 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-полный. Очевидно, что любая задача подсчета, по крайней мере, не проще чем соответствующая ей задача распознавания. Например, если известно число гамильтоновых контуров в графе, то не составит труда ответить на вопрос - «Число гамильтоновых контуров больше нуля?».


Начало  Назад  Вперед