Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 18
Текст из файла (страница 18)
Общее число элементарных операций, выполнение которых необходимо для завершения работы алгоритма, в наихудшем случае равно л л л — 1 ')'3(и — т)=3 ~~)'(и — т) =3'~)',(и — т)ли л ! гВ ! м 1 -3 ((и — 1)+(и — 2)+...+1) = Зи (и — 1)/2. 2.7.2. ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ АЛГОРИТМА ФЛОИДА Рассмотрим сеть 0=(Х, А), где Ы=(1, 2, ..., и). На каждой итерации алгоритма суммарное число элементов, значение которых должно быть оценено с помощью трехместной операции (2.53), можно вычислить, исходя из следующих соображений: 1. Общее число элементов матрицы равно и'.
2. Суммарное число элементов в базовой строке и базовом столбце равно 2и — 1. 3. Число нулевых элементов на главной диагонали равно и и для каждого из них не надо получать новую оценку. 4. Один элемент базовой строки и один элемент базового столбца расположены на главной диагонали. 5. Анализ каждого элемента требует выполнения одной операции сложения и одной операции сравнения, соответствующих трехместной операции. 6. Таким образом, максимальное число операций, выполняемых на одной итерации алгоритма, приблизительно равно 2п (и — 3) . 102 Глава 2 Поскольку число итераций равно числу узлов, т.
е. и, то общее число элементарных операций, выполнение которых необходимо для завершения работы алгоритма, в наихудшем случае равно 2пт(п — 3). 2.7.3. ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ МЕТОЛА ДВОИНОГО ПОИСКА Рассмотрим сеть 6= (Х, А), где Х=(1, 2, .„, п). Процедуру определения числа элементарных операций в алгоритме рассмотрим на примере обратного поиска. Как отмечалось в равд. 2.6.1, при обратном поиске узлы рассматриваются в последовательности п, и — 1, ..., 1.
Число обобщенных операций сложения З и минимизации Э, необходимых для выполнения процедуры обратного поиска, приводится в табл. 2.13. Таблица 222. Число обобщенных операций, неоходиыых для выполнения процедуры обратного поиске Таким образом, в соответствии с результатами, содержащимися в табл. 2.13, число обобщенных операций, выполняемых при обратном поиске, равно л(п — 1). Аналогичным образом можно показать, что число обобщенных операций, выполняемых при прямом поиске, также равно п(п — 1). Следовательно, общее число обобщенных операций в алгоритме двойного поиска равно 2п(л — 1).
Если требуется найти К кратчайших путей, то общее число оценок, которое необходимо получить при выполнении одной процедуры поиска, равно лК Поскольку при каждом поиске улучшается по крайней мере одна оценка, то число обращений к процедуре двойного поиска в наихудшем случае равно лК/2. Таким образом, общее число обобщенных операций, выполнение которых необходимо для завершения работы алгоритма двойного поиска, равно (лК/2)2л(п — 1) =Клх(л — 1) жКпв.
1ОЗ Детерминироеонние нотона в сетя» 2.8. ЗАДАЧА О КРАТЧАЙШЕМ ОСТОВНОМ ДЕРЕВЕ Перед тем как перейти к изучению этой новой потоковой задачи, остановимся на определениях, данных в гл. 1, которые имеют непосредственное отношение к нахождению кратчайшего остова. В настоящем разделе рассматриваются неориентированные сети. Назовем деревом связное множество неориеитированных ребер (дуг), не содержащее циклов. Таким образом, если задано множество и узлов, соединенных неориентнрованными ребрами, то для построения дерева необходимо выделить подмножество, состоящее из лт — 1 дуги. Иными словами, каждый узел соединен с другим узлом одним-единственным путем.
Рассмотрим сеть, содержащую л узлов, совокупность которых образует множество $. Осговным деревом называется связное множество, состоящее из (л — 1) дуг (ребер) и л узлов. Из любого собственного подмножества множества $ может быть образовано дерево, которое, однако, не является может не быть остовным деревом исходной сети.
Как и раньше, будем предполагать, что каждой дуге, соединяющей узлы 1 и 1 из множества о, приписано число сн, называемое расстоянием, или весом, дуги. Теперь мы можем ввести понятие кратчайшего (или максимального) остова. Кратчайшим остовом называется такой остов сети, у которого сумма весов си всех его дуг минимальная. Задача о кратчайшем остове имеет широкое практическое применение. Предположим, например, что вы являетесь поставщиком природного газа и хотите поставлять его с места разработки К заказчикам. Тогда кратчайший остов сети подачи газа определит такую распределительную систему, которая свяжет всех заказчиков и при этом затраты (или расстояние) будут минимальными.
Аналогичная задача возникает также при проектировании транспортной сети, когда требуется найти решения, минимизирующие затраты. Построение кратчайшего остова часто встречается в задачах субоптимизации, или декомпозиции, сложных сетевых алгоритмов. Помимо того что данная задача имеет большое практическое значение, метод ее решения является уникальным в исследовании операций.
2.8.1. АЛГОРИТМ ПОСТРОЕНИЯ КРАТЧАИШЕГО ОСТОВНОГО ДЕРЕВА В рассмотренных выше потоковых алгоритмах были использованы рекуррентные схемы вычислений, позволяющие строить последовательность решений, сходящуюся к оптимальному решению. Оказывается, задача о кратчайшем остове является одной из немногих задач исследования операций, которые могут Глава 2 2.8.2. ПРИМЕР ПОИСКА РЕШЕНИЯ С ПОМОЩЬЮ «ПОЕДАЮЩЕГО» АЛГОРИТМА (РИС.
2.28) Шаг 1. 8 = (1, 2, 3, 4, 5, 6, 7), 8 = в. Шаг 2. Выбрать узел 6. 8=(6,5) 8 = (1,2,3,4,7). Стоимость = т вд. о~-'-э быть решены с помощью «поглощающих» алгоритмов, являющихся весьма экономичными. Используя схему «поглощения», мы приведем следующий алгоритм. Как отмечалось выше, задача о кратчайшем остове заключается в выборе таких дуг заданной сети, что их суммарная стоимость минимальна и для любой пары узлов найдется путь (или маршрут), соединяющий их.
Этого можно достигнуть, выбирая дуги таким образом, что образованное ими дерево (определение которого было дано выше) покроет, или соединит, все узлы заданной сети. Иначе говоря, нас интересует, как построить остов минимальной стоимости. Задача о кратчайшем остове решается достаточно просто. Алгоритм начинает работу с выбора произвольного узла сети и кратчайшей дуги из множества дуг, соединяющих этот узел с другими узлами. Соединим два узла выбранной дугой. Выберем ближайший к этим узлам третий узел.
Добавляем этот узел н соответствующую дугу к сети. Продолжаем данный процесс до тех пор, пока все узлы не будут соединены между собой. Алгоритм, основанный на «поглощении» кратчайших дуг, может быть описан следующим образом. Алгоритм построения кратчайшего остова Шаг 1. Используя узлы исходной сети, определить следующие два множества: 8 — множество соединенных узлов; 8 — множество несоединенных узлов. Вначале все узлы будут принадлежать множеству 8.
Шаг 2. Выбрать произвольный узел из 8 и соединить его с ближайшим соседним узлом. (После выполнения данного шага множество 8 будет содержать два узла.) Шаг 3. Среди всех дуг, соединяющих узлы из множества 8 с узлами из множества 8, выбрать кратчайшую дугу. Концевой узел этой дуги, лежащий в 8, обозначить через б. Удалить узел б из множества 8 и поместить его в множество 8.
Шаг 4. Выполнять шаг 3 до тех пор, пока все узлы не будут принадлежать множеству 8. Детерминированные нотона в сетнх Рис. 2.98. Пример сети в задаче с кратчайшем остове. Шаг 3. а. Выбрать узел 3. $=(6, 5, 3), $ (1, 2, 4, 7). б. Выбрать узел 4. $= (6, 5, 3, 4), $=(1, 2, 7). Стоимость = 4ед. Шагав Стоимость б ед. Стоимость = Зад. Шаг Зб 'Стоимость ~ 7 ед. Стоимость 7 ед.
Шаг з в Стоимость = 9 еД. тоимость = 9 ед. Швг Зг з. Выбрать узел 2. $=(6, 5, 3, 4, 2), $=(1, 7). г. Выбрать узел 1. $ = (6, 5, 3, 4, 1, 2), $ = (7). 106 Глава л д. Выбрать узел 7. $= (6, 5, 3, 4, 1, 2, 7), В=в. Стоимость 14е агзд Алгоритм заканчивает работу, поскольку Ь=н. Стоимость кратчайшего остова равна 14. 2.8.3. ОПИСАНИЕ ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ АЛГОРИТМ ПОСТРОЕНИЯ КРАТЧАЙШЕГО ОСТОВА Назначение: построение кратчайшего остова неориентированной сети.
Локализация: подпрограмма М1)ЧЗРА в пакете сетевой оптимизации. Ограничения: программа позволяет обрабатывать сети, содержащие до 50 узлов и 50 дуг. Размеры сети можно увеличить, изменив границы массивов в операторах размерности, записанных в подпрограмме М1)ЧБРА и в основной программе.
Входные данные: Набор 1. Одна карта с именем алгоритма МБТК в формате (А4). Набор 2. Одна карта с числом узлов и числом дуг в сети в формате (2110). Набор 3. Общее число карт в данном наборе равно числу дуг в сети. С каждой карты считываются следующие величины: 1) номер начального узла дуги; 2) номер конечного узла дуги; 3) длина дуги. Формат (4Х, 16, 110, Р10.2).
Набор 4. Данный набор состоит из одной карты, содержащей слово 'РЕ(ЧО' в формате (А4), которая указывает конец задачи. Набор 5. Данный набор состоит из одной карты, содержащей слово 'ЕХ1Т' в формате (А4), которая указывает конец входных данных. Используемые переменные: 1 — начальный узел дуги, 3— конечный узел дуги, А! — длина дуги, Р— рабочий массив, содержащий длины дуг. Используемый метод: выбрать узел 1 и соединить его с ближайшим к нему узлом.
Затем найти узел, ближайший к уже 107 Детерминированные потоки в сетях выбранным узлам, и провести соответствующую дугу. Выполнять данную процедуру до тех пор, пока все узлы не будут соединены. Литература: НВВег 8. Вм 11еЬег!пап Я. О., ОрегаВопз асе- зеагсЬ, 2пд еб., Но!беп-13ау, 1пс., Са111огп!а, 1974. 2.8.4. РАСПРЕДЕЛЕНИЕ СРЕДСТВ НА РЕМОНТ АВТОСТРАДЫ Отдел автомобильных дорог одного из округов располагает определенным фондом, предназначенным для покрытия асфальтом нескольких дорог и проведения на них ремонтных работ.
Эти дороги соединяют 10 небольших сельских общин. Состояние поврежденных дорог таково, что в период выпадения осад- ЗАДАЧАО 'КРАТЧАЙШЕМ ОСТОВЕ КРАТЧАЙШИЙ ОС~ТОВ СОСТОИТ ИЗ СЛЕДУ!ОЩИХ ДУГ 4 6 д. 2 — — ДЗ --- ----Я8 / Ъ / / / / Ъ / / Ъ / / / Ъ 9, 4 !о >-4 в ! 4 ------- 7 — — — — 9 / ! !2ч /б Ъ ! ,!о ! Рис. 2.29. Задача о кратчайшем остове. НАЧАЛЬНЫЙ УЗЕЛ 1 2 3 3 4 5 б б 'б КОНЕЧНЫЙ ДЛИНА УЗЕЛ ДУГИ 2 7.00 3 4.00 7 2.00 8 6.00 5 6.00 6 4.00 7 500 10 4.00 9 3.00 Глава 2 ков они становятся непроходимыми.
Кроме того, из-за возникновения на дорогах выбоин, их приходится периодически ремонтировать. Для минимкзация расходов отдел автомобильных дорог должен разработать план усовершенствованной системы взаимосвязи между всеми десятью общинами, реализация которого потребует минимума строительных материалов и рабочего вре- Рис. 2.30. Решение задачи о кратчайшем остове. мени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
