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


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


Когда базовые редуцирования выполнены, для завершения вычислений можно применить полный подсчет состояний. Если только редуцирования не приводят к существенному уменьшению размера графа, такая схема непрактична. Несмотря на это, можно сформировать все минимальные пути сети и, следовательно, метод, использующий минимальные маршруты, будет работать. Предположим тогда, что минимальные пути P1,…,Ph графа G посчитаны. Пусть Ei является случаем, когда все ребра минимаршрута Pi работоспособны. Тогда надежность равна вероятности того, что произошло одно (или более) событий {Ei}. К сожалению, {Ei} не являются независимыми и, следовательно, мы не можем просто суммировать вероятности их реализации. Точнее Pr[E1 или E2] равна Pr[E1] + Pr[E2] - Pr[E1 и E2]. Теперь Rel(G) = Pr[E1 или E2 или … или Es], и, следовательно,

(1)

где EI является событием, когда все пути Pi c iОI находятся в рабочем состоянии. Это является стандартным расширением включения-исключения.

Имея список минимальных путей, вычисляется вероятность для каждого реализованного субнабора минимальных путей. Чтобы вычислить надежность, необходимо только определить выше представленную сумму. Выполняя это, следите, чтобы нечетные минипути давали вклад с плюсом, а четные - с минусом. Это сводит нашу проблему к определению набора всех минимаршрутов. Наивная реализация этого подхода фактически хуже, чем полный подсчет состояний. Число наборов путей h может быть показательной функцией n и, следовательно, только формирование минипутей требует экспоненциального времени. Однако более серьезным недостатком является то, что генерирование всех субнаборов наивным способом занимает 2h времени, которое предоставляет нам дважды экспоненциальный алгоритм вычисления надежности.

Приняв меры, можно избежать двойного экспоненциального поведения. Каждый субнабор минипутей соответствует субграфу, ребра которого являются объединением наборов ребер минипутей. Учитывая это, i-структура субграфа является набором i минипутей, чье объединение является субграфом.


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



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