Примеры сетевых топологий
Методы, базирующиеся на маршрутах и разрезах
Когда базовые редуцирования выполнены, для завершения вычислений можно применить полный подсчет состояний. Если только редуцирования не приводят к существенному уменьшению размера графа, такая схема непрактична. Несмотря на это, можно сформировать все минимальные пути сети и, следовательно, метод, использующий минимальные маршруты, будет работать. Предположим тогда, что минимальные пути P1,…,Ph графа G посчитаны. Пусть Ei является случаем, когда все ребра минимаршрута Pi работоспособны. Тогда надежность равна вероятности того, что произошло одно (или более) событий {Ei}. К сожалению, {Ei} не являются независимыми и, следовательно, мы не можем просто суммировать вероятности их реализации. Точнее Pr[E1 или E2] равна Pr[E1] + Pr[E2] - Pr[E1 и E2]. Теперь Rel(G) = Pr[E1 или E2 или … или Es], и, следовательно,
где EI является событием, когда все пути Pi c iОI находятся в рабочем состоянии. Это является стандартным расширением включения-исключения.
Имея список минимальных путей, вычисляется вероятность для каждого реализованного субнабора минимальных путей. Чтобы вычислить надежность, необходимо только определить выше представленную сумму. Выполняя это, следите, чтобы нечетные минипути давали вклад с плюсом, а четные - с минусом. Это сводит нашу проблему к определению набора всех минимаршрутов. Наивная реализация этого подхода фактически хуже, чем полный подсчет состояний. Число наборов путей h может быть показательной функцией n и, следовательно, только формирование минипутей требует экспоненциального времени. Однако более серьезным недостатком является то, что генерирование всех субнаборов наивным способом занимает 2h времени, которое предоставляет нам дважды экспоненциальный алгоритм вычисления надежности.
Приняв меры, можно избежать двойного экспоненциального поведения. Каждый субнабор минипутей соответствует субграфу, ребра которого являются объединением наборов ребер минипутей. Учитывая это, i-структура субграфа является набором i минипутей, чье объединение является субграфом.
Структура является нечетной, когда i нечетно, и четным, когда i четно. Граф, имеющий структуру, является К-субграфом. Каждая нечетная структура субграфа вносит положительный вклад в надежность, а каждая четная структура дает негативный вклад. Знаковая доминантность G с терминальным набором вершин К, sdom(G,K), равна числу нечетных структур G минус число четных структур G. Доминантность dom(G,K) равна абсолютному значению знаковой доминантности. Мы обычно пишем sdom(G), а подразумеваем dom(G) с терминальным набором К. С учетом этих определений Сатианарайана и Прабхокар существенно упростили выражение для надежности:
где Н пробегает все состояния G. Это упрощение является существенным, так как влечет за собой только формирование всех состояний, а не генерацию всех субнаборов минимаршрутов. Однако нужны еще некоторые усилия, если мы должны улучшить подсчет всех состояний. В частности, нам теперь нужна знаковая доминантность каждого состояния.
Первой целью является определение того, какие состояния имеют знаковую доминантность равную нулю, и могут, следовательно, игнорироваться в выражении для надежности. Учитывая это, состояние (субграф) является релевантным, если он не содержит нерелевантных дуг. Субграф, содержащий нерелевантные дуги, не имеет каких-либо структур и, следовательно, имеет нулевую знаковую доминантность. Таким образом, мы ограничиваем наше рассмотрение только релевантными субграфами. Среди релевантных субграфов многие имеют нулевую знаковую доминантность: точнее циклические субграфы (субграфы с ориентированными циклами). Более того, нециклические релевантные диграфы с m дугами и n узлами имеют знаковую доминантность sdom(G)=(-1)m-n+1.
Изучение доминантности в отношении проблем надежности является разумным приложением комбинаторных аргументов. Метод, который в простейшем случае требует двойного экспоненциального времени, сводится к требованию формирования нециклических релевантных графов и тривиальным расчетам для каждого из них. На практике это позволяет существенно улучшить полный подсчет состояний.
Однако число нециклических субграфов является экспоненциальной функцией n. Следовательно, несмотря на существенное сокращение вычислительных усилий, объем вычислений остается значительным.
Использование знаковой доминантности в задачах без ориентированности осуществляется совсем другим образом. В задачах без ориентированности циклические релевантные графы имеют ненулевую доминантность. Таким образом, алгоритмы включения-исключения, использующие минимаршруты, требуют алгоритмов вычисления знаковой доминантности. Однако настоящий алгоритм вычисления знаковой доминантности отдельного графа является тем же, что и алгоритм для рекурсивного расчета надежности с привлечением факторизации. Фактически, оптимальные стратегии факторизации, использующие последовательные и параллельные редукции, реализуют столько же шагов факторизации, что и в доминантности.
Предположим, что у нас есть перечень минипроходов P1,…,Ph и пусть Ei является случаем, когда все ребра/дуги минипрохода Pi являются работоспособными. Как было замечено, события {Ei} не являются независимыми. Мы рассматриваем стратегию формирования набора независимых событий. Пусть
Существует большое разнообразие методов булевой алгебры. Во-первых, заметим, что выражение для события Di является комплексным булевым выражением, включающим дополнения событий Ei, а не только состояния ребер и дополнения состояний ребер.
Вычисление Di требует упрощения булевого выражения к такому виду, который включает только состояния ребер и их дополнения. Большинство методов связано первоначально с эффективностью этого упрощения и с получением результирующих выражений, которые настолько малы насколько возможно. Во-вторых, чтобы облегчить упрощение, большинство методов использует некоторую простую стратегию для упорядочения кратчайших проходов прежде чем определять события {Di}. Конкретные, определенные события сильно зависят от выбранного порядка минипроходов. Типовой эвристикой здесь является упорядочение кратчайших проходов путем помещения в начало проходов с меньшим числом ребер/дуг. Несмотря на эти эвристические улучшения, вообще не существует известной полиномиальной границы для длины упрощенного булевого выражения Rel(G) через число минипроходов.
В случае всетерминальной надежности и достижимости, такая полиномиальная граница может быть получена с помощью алгоритма Болла и Немхаузера. При этом получается булева формула, описывающая независимые события и базирующаяся на минипроходах, в которой число членов равно числу этих проходов.
Кольбурн и Пулейбланк [S.J.Colbourn and W.R. Pulleyblank, “Matroid Steiner problems< , the Tutte polynomial and network reliability” J. Combinatorial theory B41 (1989), 20-31] сформулировали алгоритм упорядочения минипроходов для проблем k-терминальной надежности, где число членов не превышает числа деревьев связи. Однако это число может превышать число минипроходов при экспоненциальном факторе.
Каждый алгоритм, упомянутый здесь, в худшем случае требует экспоненциального времени реализации вне зависимости оттого, вычисляет ли он число состояний, минипроходов или миниразрезов. Полный граф с n узлами, например, имеет 2n-1 миниразрезов, nn-2 деревьев связи и
Методы, основанные на доминантности, гарантируют, что будут просматриваться только релевантные состояния и, таким образом, достигается улучшение в отношении почти всех других методов включения-исключения. Методы, базирующиеся на факторизации (для неориентированного случая), также генерируют только релевантные состояния. Подход Сатайанарайана-Чанга реализует наилучшее возможное время вычисления, используя последовательные и параллельные сокращения. Фактически, во всетерминальном случае, так как число деревьев связи превышает доминантность, алгоритм улучшает все методы, основанные на минипроходах. Наконец, методы, основанные на независимых произведениях, хотя и сопряжены с трудностями анализа, дают два важных алгоритма: алгоритм Болла-Немхаузера для вычисления всетерминальной надежности за полиномиальное время при заданном числе минипроходов, и алгоритм Прована-Болла, который вычисляет двухтерминальную надежность за полиномиальное время при заданном числе миниразрезов.
Этот полезный механизм измерения сложности в терминах числа минипроходов, миниразрезов или релевантных состояний позволяет видеть, что отобранные методы в действительности лучше остальных алгоритмов оценки сетевой надежности.
