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

visit this site right here visit site

Постоптимизация ограничений


До сих пор мы обсуждали базовые стратегии получения ограничений. Даже конспективное описание каждого показывает, что существует огромное разнообразие доступных методов получения ограничений. Естественно попытаться объединить их для уточнения границ или получения более общих ограничений. Предпочтительным путем является нахождение общей теории, в которой число границ унифицировано. Потерпев неудачу в этом, можно пожелать получить какую-либо информацию о надежности, и это возможно с помощью разных рассмотренных методов. Например, если известна вероятность достижения u из s, и независимо известна также вероятность достижения t из u, что можно сказать о вероятности достижения t из s? Используя известную теорему Алсведе и Дайкина, Брехт и Кольбурн разработали методы для улучшения нижних границ. Они заметили, что если сеть G соединена с терминальным набором К1, с вероятностью р1, соединена с терминальным набором К2 и с вероятностью р2 и К1ЗК2№0, то G соединена с терминальным набором К1cК2 с вероятностью, по крайней мере, р1р2. Это дает мультипликативный треугольник неравенств для границ двухтерминальной надежности, который Брехт и Кольбурн нашли эффективным для улучшения границ двухтерминальной надежности, которые были вычислены другими методами (в частности методом группирования ребер). Ключом здесь является постоптимизация, методика улучшения ограничений для произвольных границ.

В чем-то похожий метод для верхних границ, называемый ренормализацией, был изучен недавно. Для двухтерминальной надежности вероятность хе того, что один терминал s не может связаться с другим терминалом t через специфицированное ребро е, ограничена сверху вероятностью того, что само ребро е не обеспечивает связь плюс вероятность того, что е работает с вероятностью, кратной вероятности хf для каждого ребра f, соединенного с е. Двухтерминальные верхние границы могут быть использованы для определения исходных оценок вероятности хе для каждого ребра е. Тогда каждое неравенство может привести к некоторому сокращению значения хе.


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



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