Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 20
Текст из файла (страница 20)
2.31. Узел с пометкой «все маршруты» соответствует множеству всех маршрутов. Узел с пометкой (1,1) соответствует множеству «всех маршрутов», содержаи(их звено (й)). Узел с пометкой (1,1) соответствует подмножеству «всех мдршрутов», не содержащих звено (1,1). На рис. 2.31 дальнейшее ветвление из узла (Т1) не указывается.
Узел с пометкой (й,1) соответствует всем маршрутам, содержащим оба звена (й/) и (А, 1). Как и раньше, узел с пометкой (й,() соответствует всем маршрутам, содержащим (1,1), но не содержащим (й,1). 14ель ветвления можно легко объяснить следующим образом: если осуществляется разбиение множества всех маршрутов на все более мелкие подмножества, то в конце концов будет получено подмножество, содержащее один-единственный маршрут.
Звенья, или пары городов, образующие этот маршрут, могут быть восстановлены, если двигаться по дереву в обратном направлении, т. е. к начальному узлу (с пометкой «все маршруты»). Процесс ветвления выполняется 8 — 1654 114 Глава 2 на основе сравнения нижних границ. Если на неко рой итерации алгоритма нижняя граница длин маршрут~в из одного подмножества превосходит нижнюю границу, соответствующую другому подмножеству, то первое подмножество можно исключить из рассмотрения на следующей итерации. Иными словами, ветвление из соответствующего узла не производится.
Предположим, что из некоторого узла Х дерева решений исходят две дуги, и рассмотрим концевые узлы этих дуг. Тогда Все маршруты Рис. 2.31. Процесс построения подмножеств. тот узел, который соответствует подмножеству маршрутов, содержащих новое звено, будем обозначать через У, а узел, который соответствует подмножеству маршрутов, не содержащих нового звена, будем обозначать через У. 2лвз. ПРОЦЕДУРА ВЪ|ЧИСЛЕНИИ Вернемся к рассмотрению примера.
На рис. 2.32 изображен начальный узел дерева, соответствующий множеству всех маршрутов, и указаны нижняя и верхняя границы длин всех маршрутов. Следующим шагом процедуры является выбор звена, на котором будет базироваться ветвление. Цель ветвления заключается в разбиении множества маршрутов Х на два таких подмножества У и У, что наилучший маршрут из Х наиболее вероятно содержится в У и наименее вероятно — в У. Как отмечалось выше, в первую очередь во множество У должны включаться маршруты, содержащие звенья (й)), для которых А;=О.
Однако в каждой строке и каждом столбце содержится по меньшей мере один нулевой элемент. Вопрос заключается в том, какое из этих звеньев следует включить в У. Для того чтобы ответить на данный вопрос, рассмотрим маршруты, которые могут быть включены в У (маршруты, не содержащие звено (й()). Поскольку город 1 должен быть связан с некоторым дру- Двтерминировиннив потони в сетлх гим городоМ, что каждый маршрут из Г должен содержать звено, длина которого не меньше минимального элемента 1-й строки, не считая Рн.
Соответствующее расстояние обозначим через Аи Поскольку необходимо, чтобы в город 1 можно было бы попасть из некоторого другого города, то каждый маршрут из 'Тсодержит звено, длина которого не меньше минимального 2с(Т) = 48 <1 се~1 ( 7ч уо(7) маршруты и Рис. 2.32. Границы длин маршрутов исходного множества. элемента )что столбца, не считая с(п. Обозначим это расстояние через Вь а сумму величин А; и В; — через Фп. Величины Фн будем называть вторичным штрафом.
Если звено (й)) не включается в возможный маршрут, то звено, соответствующее некоторому другому элементу 1-й строки, и звено, соответствующее некоторому другому элементу )что столбца, должны входить в окончательный маршрут. Величина Фп равна (минимальному) штрафу, которому мы подвергаемся, если не включаем звено (1,1) в оптимальный маршрут.
Если штраф за неиспользование звена (й 1) вычислить для всех звеньев, для которых с(п=О, то можно сравнить соответствующие значения Фп и включить в текущий маршрут звено (й)), за неиспользование которого мы заплатили бы максимальный штраф. Очевидно, что выбор звена (й 1), соответствующего максимальному штрафу, позволяет определить новое подмножество маршрутов, не содержащих звена (81). Нижняя граница для соответствующей ветви должна быть выбрана таким образом, чтобы оиа не превосходила длины ни одного из маршрутов, не содержащих звена (81). Данное требование будет выполнено, если новую нижнюю границу положить равной сумме текущей нижней границы и максимального штрафа за неиспользование звена (й)). Это означает, что для определения максимального значения Фп мы бчдем исследовать все элементы с(г1=0.
Следует отметить, что Фи=О для всех (81), при которых 11пФО. Данное утверждение справедливо в силу того, что если положить г(п=оо и затем произвести редукцию 1-й строки и )что столбца, то сумма вычитаемых констант будет равна Фп. Для нашего примера значения А; и Вг записываются в отдельном столбце и отдельной строке соответственно. Матрица Р вместе с этими значениями выписана в табл. 2.17. Значении Фп для различных звеньев, или пар городов, приведены в табл. 2.18.
Величина Фп выражает дополнительное расстояние, 8' 116 Глава 2 которое коммивояжер проезжает в случае, когда в 1)1аршрут не включено звено (1,1), соответствующее элементу Д1=0 редуцированной матрицы. Таблица 2.17. Первая матрица решений 1 2 3 4 5 б Сг А Ю В1 Как видно из табл. 2.18, максимальное значение Фн равно 10. Выбирая звено (1, 4), мы можем получить выигрыш в расстоянии, равный 10, т.
е. больший, чем при выборе любого Таблица 2.18. Вторичный штраф другого звена. Следовательно, в качестве базового звена ветвления мы выбираем звено (1, 4). На данном этапе У=(1, 4), У=(1, 4). Нижней границей длин маршрутов из У является величина Яае(Т)+55ы.
В нашем примере она равна 48+10=88. Перед тем как определить новую нижнюю границу для множества У маршрутов, содержащих звено (1, 4), необходимо выполнить некоторое преобразование матрицы Р. Отметим, что если мы включаем в маршруты некоторое звено (й,1), то в дальнейшем можно не рассматривать й-ю строку и 1-й столбец. Следовательно, в данном примере первую строку и четвертый столбец можно исключить из рассмотрения. Далее, если звено (Й,1) принадлежит некоторому маршруту, т.
е. (А, 1) является 117 Детернинировинные потоки в сетях звеном некоторого ориентированного цикла из У, то звено (1, й) не может принадлежать маршруту из У, Выполнения данного масловки можно достичь, полагая на всех последующих итерациях Аа=оо. И наконец, могут существовать другие звенья, < помощью которых в дальнейшем также могут быть образованы подмаршруты.
(Подмаршрут — это цикл, включающий в себя неполное множество городов.) Эти звенья называются запрещенными. Их можно исключить из рассмотрения, полагая элементы матрицы Р, соответствующие длинам этих звеньев, равными оо. После проведенного преобразования матрицы Р процедуру редукции можно выполнять с любым столбцом, который содержал один-единственный нулевой элемент, расположенный в й-й позиции, и с любой строкой, которая содержала один-единственнуй нулевой элемент, расположенный в 1-й позиции. Кроме того, не исключена возможность выполнения процедуры редукции со всеми другими строками и столбцами, содержащими элементы, которые соответствуют запрещенным звеньям.
Нижняя граница для У может быть теперь вычислена как сумма всех новых вычитаемых констант и старой нижней границы. Модифицированная матрица Р, а также значения Сь Я~, А; и Вт приводятся в табл. 2.19. Отметим, что первая строка и четвертый столбец были вычеркнуты и что запрещенных звеньев в данном случае не существует. Таблица 2.79. Вторая матрица решений 1 г 3 5 б Се Ае г з а 5 б Новая нижняя граница для У в данном примере равна 48+ +1=49. Дерево решений теперь может быть изображено так, как это показано на рис. 2.33. Значения Фп после второй редукции следующие: Фм=16, Фм=5, Фаз=2 Фее=2, Фаз=О, Фаз=9 и Фее=2. Максимальным среди них является значение Фм=16, и новая нижняя граница для У равна 49+16=65.
Рассмотрим теперь множество У маршрутов, содержащих звено (2, 1). Вычеркнем вначале в матрице Р вторую строку и первый столбец. Длина звена (1, 2) равна теперь оо, однако данное значение не содержится в приво- 118 Глава 2 Таблица 2.20. Третья матрица решений 2 3 5 б С~ А; димой таблице. Отметим, что звено (4, 2) является теперь запрещенным, поскольку оно могло бы образовать подмаршрут. Чтобы предотвратить это, полагаем с(ш= со. В табл. 2.20 при- 48 < ~нов~1 < 73 маршруты е Рнс.
2.38, Границы на первой итерации ведена матрица 0 после выполнения редукции. Новая нижняя граница для У равна 49+2=51, а дерево решений на данном этапе выглядит так, как показано на рис. 2.34. 48 < 1УВСЕ~ < 23 маршруты 58 (1, 4) Рис. 2.34. Границы на второй итерации.
Для изображенных здесь множеств минимальная нижняя граница равна 51 и соответствует узлу (2, 1). Поэтому иа следующей итерации ветвление будет осуществляться из узла (2, 1). Продолжая аналогичные вычисления, мы должны были бы осуществлять ветвление из узлов с наименьшей нижней гра- 119 Детермииироваинме потоки в сетях лицей. Предположим, однако, что процесс ветвления выполняется так, как это показано на рис. 2.35, и будем рассматривать полученный в результате ветвления полный маршрут. Соответствующая матрица решения приведена в табл. 2.21.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
