Метод наиболее вероятных состояний
Метод наиболее вероятных состояний является ограничивающей процедурой, которая может быть применена к достаточно общему классу многопараметрических проблем. Единственным требованием является эффективное вычисление Ф. Мы описываем его применение к метрике работоспособности Pr[ФЈa]. Приложение к E[Ф] осуществляется аналогично. Предположим, что состояния сети упорядочены
, где s = qn, такое что
Метод наиболее вероятных состояний базируется на нумерации состояний в этом порядке. Важность использования этого порядка заключается в том, что процесс может быть завершен раньше с хорошим ограничением. Определим lpФ(k) и upФ(k) как нижнее и верхнее ограничение, для
. Верхнее и нижнее ограничения обычно используются здесь, как легко вычислимые, и, фактически, в большинстве случаев являются тривиальными границами, которые не зависят от k. Для систем с двумя состояниями, если pe равно вероятности “хорошего” состояния для ребра
е, а qe - вероятности “плохого” состояния для ребра
е, типичным предположением служит то, что pe ? qe и как следствие
, так что мы можем установить
и
для всех k. Ограничения для наиболее вероятных состояний определяются как
Здесь
может определяться динамически на основе некоторого критерия остановки. Наиболее типичным критерием является требование того, чтобы разность между верхним и нижним ограничениями лежала в допустимых пределах. Нижнее и верхнее ограничение для ожидаемого значения метрики могут быть определены аналогичным образом.
Сансо и Саумис предположили, что вместо нумерации по наиболее вероятным состояниям, много лучше осуществлять нумерацию по “наиболее важным” состояниям. Аргументация заключается в том, что в некоторых ситуациях определенные мало вероятные состояния, которые могут быть не пронумерованы, оказывают большое влияние на метрику работоспособности системы. Такие состояния могут соответствовать ситуациям, в которых система демонстрирует крайне плохую работоспособность. В частности,
может быть относительно мала, но
может быть очень велико или очень мало. Это особенно важно при вычислении ограничений Е[Ф].
Содержание раздела
