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

         

Метод наиболее вероятных состояний


Метод наиболее вероятных состояний является ограничивающей процедурой, которая может быть применена к достаточно общему классу многопараметрических проблем. Единственным требованием является эффективное вычисление Ф. Мы описываем его применение к метрике работоспособности Pr[ФЈa]. Приложение к E[Ф] осуществляется аналогично. Предположим, что состояния сети упорядочены

Метод наиболее вероятных состояний
, где s = qn, такое что
Метод наиболее вероятных состояний
Метод наиболее вероятных состояний базируется на нумерации состояний в этом порядке. Важность использования этого порядка заключается в том, что процесс может быть завершен раньше с хорошим ограничением. Определим lpФ(k) и upФ(k) как нижнее и верхнее ограничение, для
Метод наиболее вероятных состояний
. Верхнее и нижнее ограничения обычно используются здесь, как легко вычислимые, и, фактически, в большинстве случаев являются тривиальными границами, которые не зависят от k. Для систем с двумя состояниями, если pe равно вероятности “хорошего” состояния для ребра е, а qe - вероятности “плохого” состояния для ребра е, типичным предположением служит то, что pe ? qe и как следствие
Метод наиболее вероятных состояний
, так что мы можем установить
Метод наиболее вероятных состояний
и
Метод наиболее вероятных состояний
для всех k. Ограничения для наиболее вероятных состояний определяются как

Метод наиболее вероятных состояний

Здесь

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

Сансо и Саумис предположили, что вместо нумерации по наиболее вероятным состояниям, много лучше осуществлять нумерацию по “наиболее важным” состояниям. Аргументация заключается в том, что в некоторых ситуациях определенные мало вероятные состояния, которые могут быть не пронумерованы, оказывают большое влияние на метрику работоспособности системы. Такие состояния могут соответствовать ситуациям, в которых система демонстрирует крайне плохую работоспособность. В частности,

Метод наиболее вероятных состояний
может быть относительно мала, но
Метод наиболее вероятных состояний
может быть очень велико или очень мало. Это особенно важно при вычислении ограничений Е[Ф].



Содержание раздела