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


Методы Монте-Карло - часть 2


Кроме того, каждый граф всегда содержит, по крайней мере, один однородно ориентированный (s,t)-разрез.

Большинство методик Монте-Карло, представленных выше, используется также для проблем наикратчайшего пути и, в общем, не требуют того, чтобы базовый граф не имел циклических структур, как это имеет место во многих методиках ограничения для проблем PERT. Как было показано выше, пусть для еОЕ параметр ребра Xe имеет cdf Fe(x). Предположим, что вы имеете функциональные ограничения ФL и ФU для мультивариантной меры Ф, удовлетворяющей условиям

· ФL(x) Ј Ф(х) Ј ФU(x) для каждого вектора состояния х

· Для любого присвоения

величинам первой компоненты х при k=0,…,m, условная cdf имеет вид

и

может быть вычислено за полиномиальное время. Пространство Х важности в мультивариантной версии проблемы равно теперь

X={xО{0,1}E:ФL(x)Ј a, Ф>U(x)>a}

а модификация метода розыгрыша, базирующегося на ограничениях, представленная в разделе 5.1 приобретает вид

1. Разыгрывается событие

из пространства Х путем последовательного розыгрыша для k=1,…,m компонент состояния
из cdf

2. Вычисляется доля

тех выборок, для которых Ф(х) Ј a. Число
равно теперь несмещенной оценке R.

Функциональные ограничения на основе группирования ребер или непересекающихся разрезов, описанные в разделе 6.4, также дают хорошие функции ограничения для этого метода, так как условные cdf для этих функций могут быть легко вычислены. Хотя в работах Фишмана и др. эти ограничения используются только для задач максимального потока, как это описано в разделе 6.4, они могут применяться также к проблемам PERT и кратчайшего пути так, как это предложено выше.




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



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