Примеры сетевых топологий
Границы сетевой надежности
Существенно, то, что проблемы надежности, представляющие интерес, являются #P-полными, и, следовательно тот факт, что описанные точные алгоритмы совершенно неэффективны не вызывают удивления. Несмотря на это при оценке сетевой надежности абсолютно необходимо, чтобы работа завершалась за “разумное” время. Конфликтные требования быстрого вычисления при высокой точности приводят к разнообразной коллекции методов установления мер надежности.
Возникают две основные темы: оценка надежности с привлечением моделирования по методу Монте-Карло и оценка границ надежности. В первом случае целью является получение точной оценки меры надежности путем рассмотрения малой доли состояний, выбранных случайно. Это приводит к точечной оценке меры надежности и получению доверительных интервалов этой оценки. Ограничение отличается от этого как по методике, так и по результатам. Современные методики расчета ограничений пытаются найти комбинаторные или алгебраические структуры в проблеме надежности, позволяющие извлечь структурную информацию при рассмотрении малой доли состояний. В отличие от методов Монте-Карло, рассматриваются состояния, выбранные неслучайно. Целью ограничения является формирование абсолютной верхней и нижней границы меры надежности.
Проведение связи между методами Монте-Карло и методиками ограничений, возможно, вводит в заблуждение, так как многие методы Монте-Карло используют ограничения как средство определения размера пространства выборки. Мы сначала рассмотрим случай, когда все ребра работают независимо с одной и той же известной вероятностью. Затем мы рассмотрим вариант, когда ребра работают независимо с произвольными (но все же известными) вероятностями.
