Примеры сетевых топологий
Эффективные алгоритмы для ограниченных классов
Нашей первой и наиболее важной целью является получение алгоритмов с полиномиальным временем для вычисления мер надежности, когда это возможно. В виду получаемой сложности мы не можем надеяться в настоящее время получить эффективные методы для сети вообще. Однако мы можем эффективно анализировать ограниченные классы сетей.
В параграфе 3.1 мы получили большую коллекцию редукций, сохраняющих значение надежности, которые, по крайней мере, в своей простейшей форме могут обеспечить полиномиальное время расчета. Например, отбрасывание нерелевантных ребер и стягивание необходимых ребер вмести дает алгоритм для надежности k-терминальных деревьев. Еще лучше результат может быть получен при использовании последовательных и параллельных редукций. Далее может быть вычислена двухтерминальная надежность параллельно последовательных сетей. Когда вместо этого добавляются двухступенчатая и параллельное редукции, в алгоритме все-терминальной надежности для параллельно-последовательных графов непосредственно используются теоремы характеристик параллельно-последовательных графов.
Для k-терминальной надежности параллельно-последовательных графов существует два алгоритма с линейным временем работы. Сатайанарайана и Вуд [A.Satyanarayana and R.K.Wood “A linear time algorithm for computing k-terminal reliability in serial-parallel networks”, SIAM, J. Computing 14 (1985), 818-832] использовали последовательную, параллельную и двухступенчатую редукцию совместно с редукциями двухсвязных сетей, называемых также преобразованиями многогранник-цепочка, чтобы свести последовательно-параллельную терминальную сеть к одновершинному графу.
Когда две субсети сопряжены с s узлами, надежность их объединения может быть полностью определена из значений для каждой субсети. Это может быть фактически выполнено посредством алгоритма динамического программирования, чье время работы линейно по отношению к числу вершин, но экспоненциально относительно числа точек соединения. Метод Уолда и Кольбурна использует тот факт, что последовательно-параллельные графы могут быть рекурсивно разъединены с помощью парных разрезов в вершинах - то есть, последовательно параллельные графы имеют ширину дерева равную двум.
Вычисление Ф для последовательно-параллельных графов может быть выполнено тем же способом, каким это делается для задачи (s,t)-связности с последовательным и параллельным сокращениями, выполненными как это описано выше. Сложность равна O(Rn), где R является сложностью наихудшего варианта выполнения операции свертки или определения min/max в любой момент реализации алгоритма. Таким образом, сложность этих алгоритмов критически зависит от времени выполнения последовательных и параллельных операций. Для трех типов распределений, представленных в начале данного раздела, R является линейным в nq (в конечном случае) или nqr (в двух бесконечных случаях). Обычно считается, что существуют полиномиальные алгоритмы и для графов с ограниченной шириной дерева (смотри раздел 3.2) хотя это специально и не рассматривалось.
6.5. Методы, базирующиеся на состояниях
Нумерационные методы для вычисления надежности систем с большим числом состояний обязательно ограничены кругом проблем с конечным числом состояний для каждой из связей. В частности, пусть каждое ребро ej имеет ассоциированный параметр Xj из ряда значений 1, 2,…,q, с вероятностями pij=Pr[Xj = xj], xj =1,…,q, и пусть функция оценки системы Ф принимает значения из ряда 1,…,К. Тогда две классические, стохастические величины, а именно, cdf для Ф, вычисленная при заданном уровне a О{1,…,К} и среднее значение Ф могут быть записаны как
Ф(x1,…,xn) Ј?
число членов в приведенных двух выражениях может иметь порядок q|E|, и, следовательно, эти проблемы становятся трудноразрешимыми в существенно меньшем масштабе, чем даже в случае расчета надежности для систем с двумя состояниями.
Метод факторизации, предложенный в разделе 3.3, имеет здесь аналогичную (если не более громоздкую) форму. А именно, если для “осевого ребра” e и параметра ребра х определить сеть Ge,x, имеющая дугу е с фиксированным значением х. Тогда теорема факторизации для двух указанных метрик приобретает вид
Методика базируется на простом наблюдении, что в любом нециклическом графе без параллельных ребер всегда может быть осуществлена редукция, по крайней мере, одного узла, скажем путем подключения ребра е, один из концов которого v имеет только е в качестве входного (выходного) ребра.
Расширение алгоритма с линейным временем на деревья любой ширины является непосредственным, за исключением трудности распознавания сетей с заданной шириной дерева.
Получение эффективных алгоритмов путем ограничения ширины дерева рассматривается в литературе для большинства эффективных алгоритмов. Важно заметить, что у планарных графов ширина дерева зависит от числа вершин, несмотря на то, что ширина дерева ограничена O (
Помимо графов с фиксированной шириной, мало что известно по поводу мер надежности неориентированных графов. Гильберт разработал элегантный рекурсивный метод вычисления всетерминальной надежности полных сетей, когда все ребра работоспособны с равной вероятностью. Метод требует линейного времени. Он обобщается естественным образом для k-терминальной надежности, и для полных двучастных систем, а также связанных сетей. Метод существенно зависит от соблюдения условия, что несколько неизоморфных субграфов связаны множественно с некоторым числом вершин. Методу динамического программирования нужно тогда только определить полиномиальное число субсетей.
При обращении к мерам надежности ориентированных графов выделяется один важный алгоритм. Болл и Прован разработали алгоритм с линейным временем для вычисления достижимости в ориентированных нециклических сетях. Алгоритм базируется на соблюдении условия, что такая сеть функционирует (с точки зрения достижимости) тогда и только тогда, когда каждый некорневой узел имеет, по крайней мере, одну из входных дуг в рабочем состоянии.
В последнее время проводятся интенсивные исследования эффективно решаемых классов проблем узловой надежности. Узловая двухтерминальная надежность (без отказов ребер) допускает эффективные алгоритмы для графов перестановок и графов интервалов. Из этого можно получить эффективные алгоритмы для двухтерминальной надежности при отказе ребра, когда сеть имеет линейный граф, который является графом интервалов или перестановок, используя переход от проблем отказов ребер, к проблемам отказов узлов.
Классы, для которых известны точные эффективные алгоритмы, достаточно редки и не относятся к числу наиболее практичных. Несмотря на это, присутствие точных алгоритмов даже для редких классов может использоваться для ускорения точных алгоритмов для более широких классов, которые упрощают сеть некоторым образом; они имеют также использование для вычисления ограничений надежности.
Пусть е1,…, еk являются другими концами по отношению к вершине v. Тогда система Ge,x, заданная выше, является просто GЧe с переменными, ассоциированными с е1,…, еk, модифицированными следующим образом
Кратчайший путь: Lei является смещенным на х, т.е.
Максимальный поток: Сei ограничивается сверху величиной х, т.е.
Работоспособность сети PERT: Tei также смещается на величину х, i=1,…,k.
Распределения этих модифицированных случайных переменных легко вычисляются для распределений конечных состояний, например, путем обработки их как сверток или максимумов, имеющих одну случайную переменную с одним значением. Таким образом, уравнение (2) сводит конкретную проблему сети G к k субпроблем, где k равно числу значений, характеризующих дугу е, для одной и той же сети GЧe, но с разными распределениями для ребер е1,…, еk. Сложность вычисления значения или среднего cdf в этом случае критически зависит от числа таких редукций узлов, которые должны быть произведены, в комбинации с выполнением возможных последовательных и параллельных сокращений, для того чтобы уменьшить сеть до одного ребра. Бейн и др. выдали алгоритм О(n3) для определения минимального числа редукций узлов, которые должны быть выполнены, для того чтобы сократить граф выше описанным образом. Это число, следовательно, в некотором смысле также представляет “сложность” сети с точки зрения проблем пути и потока.
Методики нумерации, предложенные выше, мало используются в решении проблем, сопряженных с бесконечным числом или непрерывным рядом случайных переменных ребер. Когда случайные переменные ребер имеют экспоненциальное распределение, Кулькарни и др. предложили интересные процедуры для решения проблем наикратчайшего пути, максимального потока для плоских сетей и проблем PERT. Мы показываем, что для проблем наикратчайшего пути, максимального потока и PERT имеются аналогичные, хотя более сложные методики решения. Мы рассматриваем команду “бегунов”, которые стартуют в узле отправления s и далее двигаются по ребрам, исходящим из s.
Спустя некоторое время при известном (гамма) распределении, один из бегунов достигает конца своего ребра. В этой точке бегун останавливается, и новые бегуны устремляются вдоль ребер, исходящих из данной вершины. (Бегуны не посылаются бежать по ребрам, откуда прибыл бегун предыдущего этапа). Благодаря экспоненциальному распределению (отсутствие памяти) для времен пробега, следует, что в точке, откуда стартуют бегуны, они начинают новый этап одновременно. Короче говоря, процесс путешествия бегунов по сети является цепью Маркова с непрерывным временем. Состояние этой цепи Маркова соответствует возможному набору вершин, которые бегуны посетили и набору ребер, по которым они движутся в данный момент, а состояния поглощения соответствуют тем, что помечены t в качестве вершины адресата. Среднее время для вероятности поглощения этой цепи Маркова в точности равно длине наикратчайшего пути. Вероятность состояния поглощения может быть вычислена легко путем соответствующего упорядочения состояний цепи Маркова. Хотя время вычисления является линейным по отношению к числу состояний цепи Маркова, это число растет экспоненциально с ростом размера сети. Для сетей порядка 15-20 дуг, этот метод вполне эффективен при нахождении соответствующих решений.
