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


Эффективные алгоритмы для ограниченных классов


Вычисление Ф для последовательно-параллельных графов может быть выполнено тем же способом, каким это делается для задачи (s,t)-связности с последовательным и параллельным сокращениями, выполненными как это описано выше. Сложность равна O(Rn), где R является сложностью наихудшего варианта выполнения операции свертки или определения min/max в любой момент реализации алгоритма. Таким образом, сложность этих алгоритмов критически зависит от времени выполнения последовательных и параллельных операций. Для трех типов распределений, представленных в начале данного раздела, R является линейным в nq (в конечном случае) или nqr (в двух бесконечных случаях). Обычно считается, что существуют полиномиальные алгоритмы и для графов с ограниченной шириной дерева (смотри раздел 3.2) хотя это специально и не рассматривалось.

6.5. Методы, базирующиеся на состояниях

Нумерационные методы для вычисления надежности систем с большим числом состояний обязательно ограничены кругом проблем с конечным числом состояний для каждой из связей. В частности, пусть каждое ребро ej имеет ассоциированный параметр Xj из ряда значений 1, 2,…,q, с вероятностями pij=Pr[Xj = xj], xj =1,…,q, и пусть функция оценки системы Ф принимает значения из ряда 1,…,К. Тогда две классические, стохастические величины, а именно, cdf для Ф, вычисленная при заданном уровне a О{1,…,К} и среднее значение Ф могут быть записаны как

Ф(x1,…,xn) Ј?

число членов в приведенных двух выражениях может иметь порядок q|E|, и, следовательно, эти проблемы становятся трудноразрешимыми в существенно меньшем масштабе, чем даже в случае расчета надежности для систем с двумя состояниями.

Метод факторизации, предложенный в разделе 3.3, имеет здесь аналогичную (если не более громоздкую) форму. А именно, если для “осевого ребра” e и параметра ребра х определить сеть Ge,x, имеющая дугу е с фиксированным значением х. Тогда теорема факторизации для двух указанных метрик приобретает вид

(2)

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


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



Книжный магазин