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


Метод покрытия


Точность схем Монте-Карло, представленных выше обычно оценивается по вариации оценки

. Оценка вариации в каждом случае оказывается грубо равной a/K, где К - число проб, а a - некоторая константа, которая зависит от R и типа производимых испытаний. Таким образом, грубое аналитическое сравнение этих оценок может быть сделано на основе относительных значений a. Действительная величина вариации зависит от многих других факторов, и при линейном уменьшение К время испытаний может стать критическим. Таким образом, сравнения в действительности следует делать на эмпирической основе.

Метод покрытия разработан Карпом и Луби [R.M.Karp, M.Luby “Monte Carlo algorithms for the planar multiterminal network reliability problems”, J. Complexity 1 (1985), 45-64] и базируется на более жестком критерии, требующем большей эффективности от схемы Монте-Карло. В частности, пусть e и d являются положительными скалярами. Предположим, что мы хотим вычислить некоторую относительную меру значения R, и пусть

является результатом оценки R некоторой схемы Монте-Карло. Тогда оценка
является e-d аппроксимацией для R, если

Схема Монте-Карло называется полной полиномиальной рэндомизованной аппроксимацией FPRAS, если, кроме того, время получения оценки

имеет порядок e-1, log(d-1). Грубо говоря, FPRAS является алгоритмом, который эффективно осуществляет оценку R, чья относительная ошибка с высокой вероятностью может быть гарантировано малой.

Схема Монте-Карло Карпа-Луби является в действительности гибридом методов приоритетных и послойных выборок, и использует миниразрезы системы для улучшения наивной схемы выборок. Чтобы сохранить совместимость со статьей Карпа-Луби, мы рассматриваем вычисление R=Pr[Ф=0], т.е., вероятность отказа системы, если даже можно разработать аналогичную схему с точки зрения работы системы. Идея встроить набор F событий отказов в универсальное взвешенное пространство (U,w) - где w является неотрицательной весовой функцией для элементов U, которые удовлетворяют следующим критериям:




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



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