Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 19
Текст из файла (страница 19)
На рис. 2.29 показано расположение 10 общин и задана сеть поврежденных дорог. Длина каждой дуги соответствует затратам, связанным с ремонтом данного участка дороги, Эта задача решается с помощью программы, реализующей алгоритм построения кратчайшего остова. На рис. 2.30 изображен кратчайший остов, являющийся частью дорог, которые соединяют все 10 городов и которые должны быть отремонтированы. На с, 107 приводятся результаты работы программы, с помощью которой было получено решение задачи. 2.8.5. ПРИМЕНЕНИЯ ЗАДАЧИ О КРАТЧАИШЕМ ОСТОВЕ Задача о кратчайшем остове (ЗКО) находит широкое практическое применение. Многие задачи, на первый взгляд не похожие на ЗКО, после некоторых преобразований сводятся к ней.
С помощью построения кратчайшего остова, например, Д. Росси, Хейзер и Книг 110) предложили схему прокладки телевизионных кабелей, соединяющих все станции в единую сеть. Но наиболее интересное и важное применение ЗКО, по-видимому, находит в кластерном анализе, где ряд задач, решаю- !09 Детерминированные логики е сетях щихся другими методами этого анализа, наиболее эффективно решаются о помощью построения КО [53).
Другое применение ЗКО находит при оценке надежности сетей: вес КО соответствует минимальной вероятности того, что дерево будет повреждено в одной или нескольких дугах. Гомори и Ху [25] использовали алгоритм построения КО при решении задач о многополюсных потоках. Хелд и Карп [26, 27! нашли аналогичное применение ЗКО для решения задачи коммивояжера.
2.9. ЗАДАЧА КОММИВОЯЖЕРА Задача коммивояжера может быть сформулирована следующим образом. Коммивояжер должен выехать из заданного города, побывать в каждом из остальных н — 1 городов ровно один раз и вернуться в исходный город. Задача заключается в определении последовательности объезда городов, при которой коммивояжеру требуется проехать наименьшее суммарное расстояние. При этом предполагается, что расстояние для каждой пары городов известно.
Вместо длины пути можно рассматривать любые другие критерии эффективности, такие, как стоимость, время и т. д. Нетрудно заметить, что всего существует (л — 1)1 возможных маршрутов, среди которых один или несколько — оптимальные. Однако если некоторые города для коммивояжера недоступны, то минимальное значение целевой функции должно быть бесконечным. В большинстве случаев можно считать, что расстояние между городами 1 и 1 является симметричным, т. е. расстояние от города ! до города ! равно расстоянию от города / до города Е Однако для алгоритма, который приводится ниже, данное предположение можно опустить. Приводимый ниже алгоритм называется алгоритмом ветвей и границ.
Впервые он был разработан Литтлом и др. [411. Алгоритм работает следующим образом. Вначале определяется некоторое допустимое решение, после чего множество всех оставшихся маршрутов разбивается на все более мелкие подмножества. На каждом шаге разбиения легко вычисляется нижняя граница длины текущего наилучшего маршрута. С помощью найденных границ производится дальнейшее разбиение подмножеств допустимых маршрутов и в конечном итоге определяется оптимальный маршрут. Если находится маршрут, длина которого не превосходит наименьшей нижней границы всех других маршрутов'>, то данное промежуточное решение становится «наилучшим» допустимым решением.
Основными о Здесь имеются в виду множества маршрутов, для которых к данному шагу алгоритма вычислены оденки.— Прим. ред. но Глава 2 процедурами предлагаемого алгоритма являются вычисление нижних границ длин маршрутов, выделение субоцтимальных решений и ветвление с целью получения новых (более коротких) маршрутов. Подмножества множества всех маршрутов можно рассматривать как узлы дерева, а процесс разбиения — как ветвление дерева. Поэтому данный метод называется методом поиска по дереву решений, илн методом ветвей и границ.
Работу алгоритма мы опишем для одной модельной задачи. Параметры задачи коммивояжера, соответствующие расстояниям между городами, будут записаны в виде матрицы. Элементэтой матрицы, расположенный в 1-й строке и 1чм столбце, соответствует расстоянию от города 1 до города 1', которое мы будем рассматривать как длину звена (1,1). Обозначим через Р матрицу расстояний, каждый элемент которой соответствует расстоянию от города 1 до города 1. Если в задаче и городов (остановок), то Р является матрицей размером и,'л',и с неотрицательными элементами в(п.
Вначале в качестве Р выбирается исходная матрица расстояний, а в процессе работы алгоритма будут выполняться различные преобразования матрицы Р. Маршрут Т можно представить как множество и упорядоченных пар городов: Т=((1ь 1в), (1я 13) ° ° ((л — ь (л), (1,, 1~)). Каждый допустимый маршрут представляет собой цикл, проходя по которому коммивояжер посещает каждый город ровно один раз и возвращается в исходный город. Каждая упорядоченная пара (1,1) является дугой, или звеном, маршрута.
Длина 2(Т) маршрута Т равна сумме соответствующих элементов матрицы расстояний: Я(Т) =,')', бм. и. пвт Очевидно, что для любого допустимого маршрута каждая строка и каждый столбец матрицы Р содержат ровно по одному элементу, соответствующему этому маршруту. Отметим, что величина 2(Т) определена для любого допустимого маршрута и что длина оптимального маршрута не может превосходить текущее значение 2(Т). Следовательно, текущее значение 2(Т) является верхней границей длины оптимального маршрута. Эту верхнюю границу будем обозначать через Уи(Т). 2.9Л. ВЫЧИСЛЕНИИ НИЖНИХ ГРАНИБ, При определении нижних границ мы воспользуемся понятием редукции.
Если из каждого элемента некоторой строки матрицы расстояний вычесть постоянную величину С, то длина любого маршрута, определяемая новой матрицей, меньше дли- Детермииироаиииме истоки в сетях ны того е маршрута, определяемой старой матрицей, на величину С~1Данное утверждение справедливо потому, что каждому марш~ту соответствует ровно один элемент данной страни. Однако относительные длины всех маршрутов останутся неизменными. Следовательно, при переходе от исходной матрицы расстояний к новой останутся неизменными и все оптимальные маршруты. Очевидно, что аналогичное утверждение справедливо и для элементов столбцов матрицы расстояний.
Процедуры вычитания из каждого элемента строки наименьшего элемента этой же строки и из каждого элемента столбца наименьшего элемента этого же столбца называются редукциеи строк и редукцией столбцов соответственно. Матрица с неотрицательными элементами, в каждой строке и каждом столбце которой содержится по крайней мере один нулевой элемент, называется редуцированной матрицей. Она может быть получена в результате последовательной редукции ее строк и столбцов.
Если Е(Т) †дли маршрута Т, определяемая матрицей расстояний до выполнения редукции, 21(Т)— длина того же маршрута, определяемая редуцированной матрицей, а Н вЂ” сумма всех констант, используемых при вычислении редуцированной матрицы, то л(Т) =Н+21(Т). Поскольку редуцированная матрица содержит только неотрицательные элементы, то Н является нижней границей длины маршрута Т для нередуцнрованной матрицы расстояний. Рассмотрим задачу, в которой число городов равно 6 141], а матрица расстояний задается табл. 2.14.
Будем предполагать, что йи=со для всех 1=1. Таблица 2.14. Исходная матрица расстояний 1 2 3 л 5 б Выберем вначале произвольный допустимый маршрут, например, маршрут, состоящий из звеньев (1, 4), (4, 5), (5, 3), (3, 6), (6, 2) н (2, 1). Длина данного маршрута равна Яс(Т) = =16+18+27+0+5+7=73. Величина 2о(Т) принимается в качестве верхней границы длины оптимального маршрута, т. е. для оптимального маршрута значение У(Т) не может превосходить значения Яо(Т). В начале работы алгоритма нахожде- Глава 2 112 ние допустимого решения, позволяющего оценить о имальное решение, не является обязательным.
Однако част определение верхней границы позволяет сократить прово мые вычисления. Далее мы переходим к выполнению редукции, вначале строк, а затем столбцов матрицы расстояний. Дця этого в каждой строке определяется минимальный элембнт и найденное значение вычитается из элементов соответствузощей строки. Результаты выполненпя данной процедуры приведены в табл. 2.15, где столбец С; содержит вычитаемые константы. Таблица 21б. Редукция строк 1 2 3 4 5 б С; 1 2 з 4 5 б Затем производится редукция столбцов. Из табл.
2.15 видно, что каждый столбец, кроме первого, содержит нулевой элемент. Поэтому может быть выполнена только редукция первого столбца. В табл. 2.16 приводятся результаты, полученные после вычитания нз каждого элемента первого столбца числа 5. Строка Яг содержит вычитаемые константы для каждого столбца. Значение Н элемента, расположенного на пересечении строки Я1 н столбца Сь равно сумме всех вычитаемых констант. Как видно из табл.
2.16, Н Е (С1+Я1)=48. Данное значение и/ является нижней границей усе(Т) длин всех маршрутов в рассматриваемой задаче. Таблица 2.16. Редукция столбцов 1 2 3 4 5 6 Ст 1 2 з 4 5 6 Ж Теперь задача заключается в нахождении оптимального (минимального) маршрута. Отметим, что в- идеальном случае из Детерминированные потоки в сетях поиск решеция заключался бы в выборе ровно одного нулевого элемента в каждой строке и каждом столбце. Другими словами, если бы~такой маршрут нулевой длины мог бы быть найден, то длина, оптимального маршрута равнялась бы 48. Вместо того чтобь1,одновременно определять все звенья оптимального маршрута с помощью текущей матрицы расстояний, мы воспользуемся алгоритмом, на каждом шаге которого по матрице расстояний строится одно звено оптимального маршрута.
В результате работы алгоритма будет построен один нз маршрутов минимальной длины. Для построения решения вначале, по-видимому, целесообразно выбрать звено нулевой длины, а затем последовательно добавлять звенья нулевой илн минимальной длины. Данная процедура основана на двух основных утверждениях. Во-первых, если выбирается звено (1,1), то решение не должно содержать других звеньев, соответствующих элементам (-й строки или /-го столбца.
Во-вторых, если звено (1,1) можно исключить из окончательного решения, то его можно не рассматривать при выполнении последующих вычислений Следовательно, для каждого звена достаточно рассмотреть следующие два случая. В первом из них звено включается в текущее (частичное) и все последующие (частичные) решения, пока определяется маршрут. Во втором случае звено исключается из дальнейшего рассмотрения. 2«Ь2. ВЕТВЛЕНИЕ Процесс разбиения множества всех маршрутов на непересекающиеся подмножества может быть представлен в виде ветвления дерева, как показано на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
