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


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


Вычисление 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 деревьев связи и

состояний. Если экспоненциальные алгоритмы оказываются наилучшими, можно надеяться, что разумно рассмотреть алгоритмы, которые используют относительно малое число состояний. Из многих алгоритмов, упомянутых здесь, три метода наиболее достойны внимания.




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