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


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


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

Одна стратегия окончательной постоптимизации была сформирована для применения, когда вероятности работоспособности всех ребер равны между собой. Кольбурн и Хармс заметили, что если произвести оценку полинома

при фиксированном значении р, будет получена линейная комбинация F0,…,Fd. Следовательно, если известна верхняя или нижняя граница значения надежности и она полиномиальна при специфицированном значении р, то мы получаем линейное ограничение. Таким образом, любой метод, применяемый к сети с ребрами, вероятности работоспособности которых равны между собой, выдает линейное ограничение этого вида. Все линейные неравенства, полученные так, удовлетворяются одновременно, и, следовательно, можно комбинировать ограничения разных видов, используя методы линейного программирования. Если все базовые используемые ограничения эффективно вычислимы, можно использовать алгоритмы с полиномиальным временем для линейного программирования, чтобы сохранить полное время вычислений в полиномиальных пределах.




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