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


Методы, базирующиеся на маршрутах и разрезах - часть 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 деревьев связи и

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




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



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