Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 15
Текст из файла (страница 15)
Для иллюстрации численного метода решения данной задачи рассмотрим прямоугольную сеть, изображенную на рис. 2.20. Она ао Таблица 2.7. Пути в задаче со штрафами аа выполнение поворотов представляет собой участок транспортной сети с перекрестками. Въезд на участок осуществляется через узел 1, а выезд— через узел 8. Числа, приписанные дугам, представляют собой плату за проезд по соответствующим улицам. Кроме того, предполагается, что за выполнение каждого поворота взимается штраф, равный 3. Требуется определить наиболее экономный путь из узла 1 в узел 8. Мы воспользуемся следующей теоремой.
Теорема 118]. В сети со штрафами за выполнение поворотов кратчайший путь из узла з в узел Т, проходящий через промежуточный узел А, может не содержать в себе кратчайший путь из з в л или кратчайший путь из й в з. Проиллюстрируем данную теорему на првмере транспортной сети, изображенной на рис. 2.20. Перебирая всевозможные пути и выбирая среди них тот, для которого общие затраты минимальны, нетрудно получить наиболее экономный путь. Соответствующие результаты приведены в табл. 2.7. Из этих результатов видно, что наиболее экономным путем из узла 1 в узел 8 является путь Рш общая стоимость которого равна 15. Отметим, что при движении от узла 1 к узлу 4 вдоль пути Р, общие затраты составляют 11.
В то же время, рассматривая пути Р1 и Рт, можно заключить, что между узлами 1 и 4 существует путь меньшей стоимости, равный 1О. Он является частью пути Рт и состоит нз дуг (1, 2), (2, 6), (6, 5) и (5, 4). Поэтому данный путь является кратчайшим путем из узла 1 в узел 4, и в то же время он не принадлежит кратчайшему пути, соединяющему узлы 1 и 8. Следовательно, для решения за- 81 Детерминированные потони е сетях дачи о кратчайшем пути на сети со штрафами за выполнение поворотов нельзя непосредственно воспользоваться обычными алгоритмами поиска кратчайших путей.
Однако исходная задаРис. 2.21. Алгоритм поиска кратчайшего пути аля сети со штрафами аа выполиеиие поворота. а — шаг Н 6 — шаг 21 е — шаг 3. ча может быть сведена к другой задаче, для которой указанные алгоритмы применимы 1181. Соответствующая процедура может быть описана следующим образом. Пусть задана сеть 6= (Х, А) с р узлами, образующими множество 11, и а дугами, образующими множество А. Шаг 1. Ввести фиктивный узел и и соединить его с источником з ориентированной дугой 1з, з). Ввести фиктивный узел Ти соединить его со стоком г ориентированной дугой 1г, У). Полу- Глава 2 ченная при этом сеть для рассматриваемого примера изображена на рнс. 2.21, а. Шаг 2.
Каждой дуге сети приписать фиктивну)о метку Еа. Пусть Ео, Еь-.,Е,Еач.1 — фиктивные метки а+2 д г расширенной сети. Полученная при этом сеть для рассма иваемого примера изображена на рис. 2.21, б. Шаг 3. Построить фиктивную сеть, состоящую из а+2 узлов Ео, Еь-,Еааь причем узлы Е; и Ег соединены ориентированной дугой (Еь Е;) в том случае, когда в помеченной сети, построенной на шаге 2, дуга с меткой Е; непосредственно предшествует дуге с меткой Еь Значения параметра ветви, соединяющей узлы Е; и Еь определяются равными с(Е~)+р(Еь Ег), где с(Е;) — исходная стоимость дуги Еь а р1Еь Е;) — штраф за выполнение поворота, соответствующего дуге (Е;, Е;). Стоимости дуг 18, з) и 18 Т) полагаются равными нулю. Предполагается также, что иа узлов з и 1 повороты никогда не выполняются.
Фиктивная сеть для рассматриваемого примера изображена на рис. 2.21, в. Стоимости дуг выписаны в табл. 2.8. Таблица 2.8. Стоимости дуг фиктивной сети, построенной на шаге 3 Используя один из алгоритмов поиска кратчайшего пути'>, можно определить наиболее экономный путь из узла Ео в узел Е1о. Читателю предлагается проверить, что такой путь соответствует последовательности дуг ГЕо Е1) Р-ь Еа), ~Ез, Ет), 1Ет, Еа) и 1Еэ Е|о).
Как следует из табл. 2.9а, стоимость этого пути равна 15. Записав данное решение в терминах исходной сетевой задачи, мы получим результаты„ приведенные в табл. 2.9 б. Та- о Если не принимать во внимание ориентацию дуг, то алгоритмы, описан- ные в равд. 2.3 н 2.4, могут быть использованы дли поиска кратчайших путей. — Прим. перев. Детерминированные нагони е сетях Таблица 2.9а. Оптимальный путь в фиктивной сети Таблица 296.
Оптимальное решение ким образом, путь минимальной стоимости в исходной сети соответствует последовательности узлов 1, 2, 3, 4, 8, а его общая стон~месть равна !5. 2.З. ЗАДАЧА О К КРАТЧАИШИХ ПУТЯХ При решении некоторых практических задач, связанных с коммуникационными или транспортными сетями, требуется найти не один, а несколько кратчайших путей, расположенных в порядке возрастания вх длин. Например, знание нескольких кратчайших путей в сети улиц позволит планировщикам транспортных сетей более точно моделировать потоки движения автомобилей по улицам городов.
При составлении маршрута передачи информации по коммуникационной сети, когда некоторые пугн временно заняты, могут быть использованы сведения о наилучших из возможных альтернативных вариантов. Таким образом, в тех случаях, когда нет возможности воспользоваться наилучшим решением, можно найти ему замену из числа дополнительных решений.
Кроме того, знание решений, ближайших к наилучшему, позволит определить устойчивость решений по отношению к внешним факторам, влияние которых не учитывается в сетевой модели. В общей постановке задачи о К кратчайших путях не требуется, чтобы пути не содержали циклов, и учитываются только длины путей. Ослабление ограничений в данной задаче позволило разработать несколько процедур поиска решения, в ко- Глава г торых учитывается специфика конкретной сетевой задачи. Традиционный подход к решению данной задачи1был разработан рядом авторов и изложен в обзорных стат х, таких, например, как,работа Дрейфуса 1121.
Внекоторы новыхметодах используется аналогия между решением обще задачи о К кратчайших путях и решением системы обыкновенных линейных уравнений. Один из таких методов, известныв под названием «метод двойного поиска» [47), позволяет одновременно вычислять длины К кратчайших путей из начального узла ко всем остальным узлам сети. Перейдем к рассмотрению этого метода. здс1. МЕТОД ДВОИНОГО ПОИСКА Рассмотрим ориентированную сеть, узлы которой занумерованы от 1 до и. Предположим, что для каждого узла имеется вектор оценок длин К кратчайших путей, соединяющих этот узел с заданным начальным узлом. Метод двойного поиска основан на последовательном уменьшении оценок, в результате чего за конечное число итераций строится оптимальный вектор оценок.
Предполагается, что начальные оценки не меньше длин соответствующих путей. На каждой итерации выполняются две процедуры. При выполнении процедуры прямого поиска узлы рассматриваются в порядке возрастания их номеров Ц=1, 2, ..., и). После построения множества узлов 1(1, соединенных дугой с узлом 1, последовательно рассматриваются длины К кратчайших путей из начального узла в узел / и устанавливается возможность прохождения более коротких путей через эти узлы й Если такие пути существуют, то вх длины будут использоваться в качестве новых оценок на последующих итерациях. Аналогичная процедура выполняется при обратном поиске, однако в этом случае узлы рассматриваются в порядке убывания их номеров О=п, п — 1, ..., 1) и исследуются узлы 1)1, соединенные дугой с узлом 1. В алгоритме двойного поиска используются две специальные алгебраические операции 147). Они называются обобщенными операциями, поскольку выполняются не над числами, а над векторами.
Данные векторы должны иметь одинаковую размерность и могут содержать как конечные, так и бесконечные компоненты. Однако требуется, чтобы конечные компоненты предшествовали бесконечным и были расположены в строго возрастающем порядке. Таким образом, векторы не должны содержать равных конечных компонент. Следующие векторы являются допустимыми: А=1 — 4, О, 7, аа1, В=13, 4, аа, аа1.
С другой стороны, векторы С= 1 — 4, 3, 3, 91, 0= ~ — 9, О, аа, 9] не являются допустимыми. Детерминированные потоки в сетях 85 Перейдем к рассмотрению этих двух операций. Первая из них называется обобщенной операцией минимизации, вторая— обобщенной операцией сложения. Эти операции являются двухместными, т. е. онн могут выполняться только над двумя векторами.
При выполнении обобщенной операции минимизации вначале определяется множество всех компонент двух заданных векторов размерности и, а затем строится третий вектор такой же размерности, составленный из й различных наименьших по величине элементов этого множества, расположенных в строго возрастающем порядке. Если в новом векторе число конечных компонент меньше его размерности, то остальные компоненты принимаются равными оо. В качестве примера рассмотрим векторы А=! — 4, О, 1, оо! и В=11, 7, 8, 9!.
Множеством, образованным из компонент векторов А и В, является множество ( — 4, О, 1, оо, 1, 7, 8, 91. Различные по величине элементы этого множества могут быть упорядочены следующим образом: — 4, О, 1, 7, 8, 9, оо. Поскольку размерность векторов А и В равна 4, результатом выполнения обобщенной операции минимизации над ними является вектор С= 1 — 4, О, 1, 7~!, составленный из четырех наименьших по величине элементов построенного множества. При выполнении обобщенной операции сложения вначале определяется множество всевозможных попарных сумм компонент двух заданных векторов одинаковой размерности, а затем строится третий вектор такой же размерности, первой компонентой которого является минимальный элемент построенного множества.
Остальные компоненты вектора выбираются точно так же, как было показано при описании обобщенной операции минимизации. Для иллюстрации выполнения обобщенной операции сложения рассмотрим векторы А и В. Множество всевозможных попарных сумм компонент этих двух векторов задается следующей таблицей: Элементы множества А — 4 О ! со Элементы множества В з э Поэтому множество всевозможных попарных сумм может быть определено как ! — 3, 1, 2, оо, 3, 7, 8, оо, 4, 8, 9, оо, 5, 9, !О, оо7, Элементы этого множества могут быть расположены в строго возрастающем порядке следующим образом: — 3, 1, 2 Глава л 3, 4, 5, 7, 8, 9, !О, сс. Поэтому обобщенная сумма векторов А и В равна вектору С= [ — 3, 1, 2, 3]. Для описанив! алгоритма двойного поиска нам потребуется формальное определение этих двух операций.
Введем следующие обозначения:  — множество вещественных чисел; В множество, содержащее все элементы из В и элемент сс; К— число искомых длин путей; 8(К) — множество векторов размерности К, компоненты которых принадлежат В и расположены в строго возрастающем порядке; ппп| — операция нахождения !что минимального элемента заданного множества. Поскольку по определению компоненты векторов из 8(К) расположены в строго возрастающем порядке, то следует принять соглашение, что сс<сс в том случае, когда вектор содержит несколько бесконечных компонент. Обобщенная операция минимизации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
