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

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

. Оценка вариации в каждом случае оказывается грубо равной 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, которые удовлетворяют следующим критериям:

· w(F)=Pr(F) = R

· w(U) эффективно вычисляемо (т.е. за полиномиальное время), выборка событий может быть эффективно осуществлена из U с вероятностью, пропорциональной их весу.

· Можно эффективно распознать, когда элемент из U принадлежит также и F.

· w(U)/w(F) ограничено сверху некоторой величиной М для всех случаев класса задач

Тогда ясно, что если осуществлена выборка из U и определена оценка

путем умножения доли этой выборки, которая содержится в F, на w(U), тогда

является несмещенной оценкой R. Установлено, что для любых положительных скаляров e e и d, если размер выборки равен, по крайней мере, Mґln(2/d)4.5/e2, тогда результирующая оценка

является e-d аппроксимацией для R. Другими словами, эта схема выборки является FPRAS.

Теперь рассмотрим метод покрытия с точки зрения его использования для проблемы надежности (s,t)-связности, хотя та же методика может быть применена для широкого круга ситуаций. Пусть (G,s,t,p) является примером проблемы надежности (s,t)-связности и пусть С является минимальным набором (s,t)-разрезов для G. Определяем универсальное взвешенное пространство U, которое состоит из пар (х,С), где х - вектор состояния, СО С, и хе=0 для всех e ОC. Вес, приписываемый каждой паре (х,С) просто равен Р(х). Теперь каждое состояние отказа х системы отражается в элементах U столько раз, сколько требуется мини разрезов для отказа х. Для того чтобы F входило в U, необходимо приписать каждому х уникальное СОС. В проблеме (s,t)-связности это сделано с помощью нахождения набора элементов, которые могут быть достижимы от s через рабочие ребра (с учетом х) и установки СєС(х), соответствующих ребрам их Х в V\X. Элементы F теперь появляются в U, >как (х,С), такие что С=С(х), а элементы U могут быть определены на долгое время соответствующими элементу F путем проверки условия С=С(х). Метод покрытия для задачи (s,t)-связности рассмотрен ниже.

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

1. Определяем множество С набора (s,t)-разрезов G. Для каждого СО С вычисляем w(C)=ПeО Сqe = полному весу всех элементов U со второй компонентой, равной С, и затем вычисляем w(U) =3СО Сw(C).

2. Осуществляем выборку элементов (x,C) из U в пропорции их весов при первом розыгрыше С из С с вероятностью w(C)/w(U) и затем производим розыгрыш х путем установки хе=0, eОС, и приписав другим компонентам х значения согласно их вероятностям.

3. Вычисляем долю

, когда событие (х,С) имеет С=С(х). Тогда

(U) является несмещенной оценкой R.

Рассмотренная выше схема не является FPRAS по двум причинам. Во-первых, необходимо нумеровать все разрезы в наборе С и мощность набора растет экспоненциально с ростом объема задачи. Во-вторых, условие ограничения для w(U)/w(F) не удовлетворяется для общих случаев задачи. Карп и Луби однако, модифицировали процедуру, описанную выше, для случая задач надежности (s,t)-связности, где граф G является плоским и однонаправленным и ограничения сопряжены с множественностью и суммарной вероятностью, а также выполняется условие ограничения сверху ПeО С(1+qe) некоторым фиксированным М.

Мы здесь не вдаемся в детали, главная идея заключается в расширении С, чтобы включить разрезы, которые являются “почти минимальными”, таким образом, чтобы ассоциированное пространство U, определенное выше, удовлетворяло требуемым свойствам с учетом F. Плоскость G используется, чтобы разрешить эффективную выборку элементов расширенного пространства U с правильными вероятностями, так чтобы модифицированная схема для задач надежности (s,t)-связности стала FPRAS.

Содержание раздела