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


Преобразования и сокращения


Одним из “сокращений” популярных в задачах с большим числом состояний, которые не имеют аналогов в бинарных проблемах, является преобразование задачи с большим числом состояний в проблему, в которой каждое ребро с состоянием “отказ” удаляется из сети, а “работающая” связь имеет длину, пропускную способность и время завершения. Хотя это вообще не дает улучшения в сложности ассоциированного алгоритма вычисления надежности, эта техника позволяет концептуально облегчить использование факторизации и других методов нумерации. В частности, если случайная переменная связи Xe берется из ряда x1 Ј x2<…< xq с Pr[Xe=xi]= pi, i=1,…,q, тогда связь е может быть замещена посредством

Кратчайшего пути: q параллельных путей, i-ая связь имеет длину xi и вероятность работоспособности pi(1-

Максимального потока: q последовательных связей, i-ая связь имеет пропускную способность xi и вероятность работоспособности pi(1-

Сети с работоспособностью PERT: q параллельных путей, i-ая связь имеет время завершения операции xi и вероятность работоспособности pi(1-

Удаление неподходящих связей, рассмотренное в 3.1, применимо также и к трем проблемам, упомянутым выше, так как состояние связи, которое не лежит на минимальном (s,t)-пути не влияет ни на длину пути, ни на поток, ни на время выполнение операции. Обязательные ребра графа могут быть аналогично связаны с проблемой максимального потока. В частности, если обязательное ребро е подключено к мгновенному графу G, когда вычисляется Pr[ФFLOW? a], тогда мультипликативный фактор, применяемый к проблеме для подключенного графа G·e, равен Pr[Се? a]. В случае проблем наикратчайшего пути или PERT обязательные связи не могут быть немедленно присоединены, так как параметры этих ребер графа повлияют на длину кратчайшего и самого длинного пути исходного графа. Они, в действительности, вводят три односвязные субсети и, следовательно, могут обрабатываться, как это описано в разделе 6.3.

Последовательные и параллельные сокращения имеют мощные аналоги в проблемах маршрутов и потоков.


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



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