Дерево - кратчайший путь
Cтраница 3
Как и алгоритм расстановки меток, метод коррекции меток ( label correcting) начинает работать, присваивая полю Dist корневого узла нулевое значение и помещая корневой узел в список возможных. Значения Di st для других узлов устанавливается в бесконечность. Затем из списка возможных узлов выбирается первый узел и добавляется к дереву кратчайшего пути. [31]
 |
Перекресток со штрафами за повороты.| Перекресток, соединенный с фиктивным корневым узлом. [32] |
Однако программу все же придется слегка изменить, чтобы учесть разбиение узлов на несколько частей. Предположим, нужно найти кратчайший путь между узлами. Учитывая, что узел i разрешается по-кинуть по любому ребру, можно создать фиктивный узел, чтобы использовать его как корневой узел дерева кратчайшего пути. Соедините этот узел связями нулевой стоимости с каждым из подузлов узла i. В этом случае, если построить дерево кратчайшего пути с корнем в фиктивном узле, будут найдены все кратчайшие пути, включающие любойиз этихпо-дузлов. На рис. 12.14 показан перекресток с рис. 12.13, соединенный с фиктивным корневым узлом. [33]
Программа PathS использует алгоритм установки меток для вычисления кратчайшего пути. Она похожа на программы Nc LEdit и Span. Если вы не вставляете и не удаляете узлы или связи, то можно выбрать узел при помощи мыши, и программа найдет и отобразит дерево кратчайших путей с корнем в этом узле. [34]
Предположим, что имеется карта города, которая показывает расположение всех пожарных депо. Вам необходимо определить для каждой точки города ближайшее к ней депо. На первый взгляд эта задача кажется сложной. Можно попытаться вычислить дерево кратчайших путей с корнями в каждом узле сети, чтобы найти, какое из пожарных депо расположено ближе всего к тому или иному узлу. [35]
В пакете программ исследования надежности для расчета режимов применяется модифицированный алгоритм Басакера-Гоуэна со справочной, позволяющий одновременно с режимом найти оптимальную систему потенциалов и оценок мощностей. Основные изменения по сравнению со стандартной процедурой сводятся к следующему. Автоматизировано составление преобразованной расчетной сети, причем описание ее упорядочивается в соответствии со структурой графа сети. На каждом шаге алгоритма при построении дерева кратчайших путей из 0 в остальные узлы сети используются элементы такого дерева, построенного на предыдущей итерации. Коррекция потока и оценок при изменении состояния системы осуществляется с использованием справочной, которая содержит перечень кратчайших деревьев, построенных при вычислении потока в нормальной ситуации. О быстродействии алгоритма свидетельствуют следующие данные: для расчета 76 оптимальных режимов в системе неф-теснабжения, исходная расчетная сеть которой содержала 67 узлов и 92 дуги, потребовалось около 2 5 мин машинного времени ЭВМ ЕС-1040, т.е. в среднем примерно 2 с на расчет потока, потенциалов и оценок для каждого состояния системы. [36]
Теперь предположим, что требуется найти для исходной сети дерево кратчайшего пути с корнем в узле D. На рис. 12 16 изображена новая сеть, сформированная из сети на рис. 12.15, с фиктивным корневым узлом, соответствующим узлу D. Дерево кратчайшего пути через эту сеть обведено жирными линиями. [37]
Для каждой точки сети кратчайший путь от ложного корневого узла к данной точке пройдет через ближайшее к ней пожарное депо. Чтобы найти ближайшее к данной точке пожарное депо, просто следуйте по кратчайшему пути от точки к корню, пока на пути не встретится одно из депо. Построив всего одно дерево кратчайших путей, вы можете найти ближайшее пожарное депо к каждой точке сети. [38]
Однако программу все же придется слегка изменить, чтобы учесть разбиение узлов на несколько частей. Предположим, нужно найти кратчайший путь между узлами. Учитывая, что узел i разрешается по-кинуть по любому ребру, можно создать фиктивный узел, чтобы использовать его как корневой узел дерева кратчайшего пути. Соедините этот узел связями нулевой стоимости с каждым из подузлов узла i. В этом случае, если построить дерево кратчайшего пути с корнем в фиктивном узле, будут найдены все кратчайшие пути, включающие любойиз этихпо-дузлов. На рис. 12.14 показан перекресток с рис. 12.13, соединенный с фиктивным корневым узлом. [39]
Страницы: 1 2 3