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


Метод покрытия - часть 2


· 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).




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