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


Эффективные алгоритмы для ограниченных классов - часть 2


Пусть е1,…, еk являются другими концами по отношению к вершине v. Тогда система Ge,x, заданная выше, является просто GЧe с переменными, ассоциированными с е1,…, еk, модифицированными следующим образом

Кратчайший путь: Lei является смещенным на х, т.е.

Максимальный поток: Сei ограничивается сверху величиной х, т.е.

, i=1,…, k.

Работоспособность сети PERT: Tei также смещается на величину х, i=1,…,k.

Распределения этих модифицированных случайных переменных легко вычисляются для распределений конечных состояний, например, путем обработки их как сверток или максимумов, имеющих одну случайную переменную с одним значением. Таким образом, уравнение (2) сводит конкретную проблему сети G к k субпроблем, где k равно числу значений, характеризующих дугу е, для одной и той же сети GЧe, но с разными распределениями для ребер е1,…, еk. Сложность вычисления значения или среднего cdf в этом случае критически зависит от числа таких редукций узлов, которые должны быть произведены, в комбинации с выполнением возможных последовательных и параллельных сокращений, для того чтобы уменьшить сеть до одного ребра. Бейн и др. выдали алгоритм О(n3) для определения минимального числа редукций узлов, которые должны быть выполнены, для того чтобы сократить граф выше описанным образом. Это число, следовательно, в некотором смысле также представляет “сложность” сети с точки зрения проблем пути и потока.

Методики нумерации, предложенные выше, мало используются в решении проблем, сопряженных с бесконечным числом или непрерывным рядом случайных переменных ребер. Когда случайные переменные ребер имеют экспоненциальное распределение, Кулькарни и др. предложили интересные процедуры для решения проблем наикратчайшего пути, максимального потока для плоских сетей и проблем PERT. Мы показываем, что для проблем наикратчайшего пути, максимального потока и PERT имеются аналогичные, хотя более сложные методики решения. Мы рассматриваем команду “бегунов”, которые стартуют в узле отправления s и далее двигаются по ребрам, исходящим из s.


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



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