Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 17
Текст из файла (страница 17)
Одна карта с именем алгоритма КБКТ в формате (А4). Набор 2. Одна карта с числом узлов и числом дуг в сети в формате (2110). Набор 3. Данный набор состоит из следующих трех разделов. Раздел 1: 1) номер начального узла дуги; 2) номер конечного узла дуги; 3) длина дуги. Формат (3110). Для каждой дуги соответствующие величины должны быть пробиты на одной карте. Карты располагаются в порядке возрастания конечных узлов дуг.
Раздел 2: 1) К, (ч(8, 1МАХ. Фопмат (4Х, 315). Глава 3 Раздел 3: Ц НР, РМАХ. Формат (4Х, 215). Замечание: если данную задачу требуется последовательно решать для различных начальных и (илн) конечных узлов сети, то входные данные следует изменять только в разделах 2 и 3. Набор 4. Данный набор состоит из одной карты, содержащей слово 'РЕЯ(Л' в формате (А4), которая указывает конец за- дачи. Набор 5. Данный набор состоит из одной карты, содержащей слово 'ЕХ1Т' в формате (А4), которая указывает конец вход- ных данных. Составные части программы.
Программа состоит из следу- ющих подпрограмм: КБНОКТ (ввод данных и вычисления); 1Л5%Р (печать длин К кратчайших путей из начального узла сети во все остальные узлы); ТцАСЕ (печать узлов К крат- чайших путей нз начального узла сети в заданный конечный узел).
Используемые переменные и массивы: Х вЂ” число узлов в сети, М(Л вЂ” число дуг (1, Л), для которых 1<Л, М1. — число дуг (1, Л), для которых Л<1, 1.).Е1ч — массив, в котором значение Л-го элемента равно числу дуг (1, Л) при Л<1, 1.1МС вЂ” массив номеров 1 узлов, соединенных дугой с уз- лом Л, где 1)Л. Номера 1 располагаются последовательно для .Л=1, 2, ..., г1, 1.УА1.— массив длин дуг, соответствующих узлам в массиве 1.1НС, 1Л.Ег1 — массив, в котором значение Л-го элемента равно чис- лу дуг (1, Л) при 1<Л.
ШМС вЂ” массив номеров 1 узлов, соединенных дугой с уз- лом Л, где 1<Л. Номера 1 располагаются последовательно для Л=1,2, ...,Н, 0ЧА1.— массив длин дуг, соответствующих узлам в масси- ве ШЫС, 1ЫР— верхняя граница длин всех путей сети, ЬТАВТ вЂ” массив, в котором значение Л-го элемента равно номеру позиции, начиная с которой в массиве 1ХС располага- ются номера 1 узлов, соединенных дугой с узлом Л, 11чС вЂ” массив номеров 1 узлов, соединенных дугой с узлом Л. Номера 1 располагаются последовательно для Л= 1, 2, ..., о1, ЪА1.— массив длин дуг, соответствующих узлам в массиве 1НС.
Дополнительные переменные, которые должны быть описа- ны пользователем: Дете нинироеанные потоки е сетях 96 К вЂ” число искомых кратчайших путей, 1МАХ вЂ” максимально допустимое число итераций в алго- ритме двойного поиска, МБ, 1ЧР— начальный н конечный узлы К искомых кратчай- ших путей, РМАХ вЂ” максимальное число путей из узла ЫБ в узел )ЧР, которое должно быть сгенерировано.
Используемый метод: данный алгоритм основан на методе, описанном в равд. 2.6.1. Литература: 1481. Если по условию задачи требуется рассматривать только пу- ти, не содержащие циклов, то подпрограмма ТЯАСЕ может быть модифицирована таким образом, что поиск пути завер- шится, как только встретится цикл. При этом в подпрограмме вместо операторов, расположенных в строках 52 — 54, следует записать следующие операторы: 120 60 Х = 1, К 1Р(Х(1н1, Ю) — 1,Т) 60, 180, 70 180 ОО 181 1А = 1, КК 1Р(1н1 — Р(1А)) 181, 70, 181 181 СО)ЧТПЧ11Е ОО ТО Ф 60 СО(ЧТ1Х()Е 2.6.4.
РЕЗУЛЬТАТЫ ВЫЧИСЛЕНИИ Эффективность метода двойного поиска наглядно показана в работе 148). Кроме того, в этой работе показано, что данный метод как теоретически, так и практически является более эффективным, чем другие методы решения задачи о К кратчайших путях. В настоящем разделе мы будем рассматривать прямоугольные сети, какими являются, например, сети проселочных дорог во многих сельскохозяйственных районах Соединенных Штатов. Интересной особенностью данных сетей является наличие в них нескольких путей заданной длины. Если требуется найти.
кратчайший путь, удовлетворяющий одному нли нескольким внешним условиям, таким, например, как непревышение допустимой нагрузки на мосты, через которые проходит этот путь„ то приходится искать все пути заданной длины. В настоящем разделе мы остановимся на некоторых, результатах вычислений„ связанных как с определением длин путей, так и с выполнением процедуры трассировки. Будем рассматривать сеть, состоящую из 56 узлов и 182 дуг (рис. 2.26). Через 1Ч5 .и )ЧР будем обозначать соответственно 96 г г номера источников н стоков. Ниже приводятся данные о: 1) числе построенных путей; 2) порядковом номере (по длине) максимального из построенных путей; 3) общем времени рещения задачи; 4) времени выполнения процедуры трассировки. з з 2 з з з 1 99 2 2 Э 2 4 г 5 3 б 3 7 б 8 4 4 3 2 15 з !6 3 4 3 4 3 4 3 4 3 4 3 1 3 2 г 2 2 9 99 1О 3 11 3 12 3 13 3 14 з 2 4 2 4 3 4 3 2 2 4 3 2 з г 2 г з 1 23 3 24 Гт 99 !8 3 '9 з гО 3 г! з гг 3 2 4 2 2 2 4 4 2 5 5 4 4 3 з 4 3 5 25 99 26 3 27 3 28 3 29 3 30 3 3! г 32 4 3 3 4 4 3 2 2 4 4 4 2 4 1 2 г 2 г 2 33 99 34 г 35 г 36 2 37 2 38 з 39 з 40 3 4 4 3 2 2 1 1 2 4 4 2 5 5 3 3 5 4 3 1 41 99 42 2 43 5 44 4 45 2 46 4 47 5 48 2 2 1 1 2 б 3 3 2 5 б 1 3 4 .
4 3 3 3 4 3 2 49 99 50 3 51 г 52 2 53 б 54 г 55 б 56 гх Рис. 2.26. Пример поиска К кратчайших путей. Рассматриваются два случая. В случае 1) НБ=1, ЯР=56, К= =1О; в случае 2) ИВ=56, ЫР принимает 7 различных значений (каждый пользователь, для которого находятся пути между ХЯ н МР, задает свои значения ИР), К=5, а максимальное число построенных путей между (ч(8 и ХР равно 30. Результаты вычислений приводятся в табл. 2.!1а и табл. 2.11б. В табл. 2.11а приводятся следующие результаты.
В первом столбце записаны значения 1О, 20, 40, 80, 160, 250 и 285, которые принимал параметр РМАХ, соответствующий максимальному числу построенных путей. В каждом из этих случаев были получены оценки длин К=10 путей. Порядковый номер (по 97 Детерминированные нотона в сетях Таблица 2.11а. Результзты вычислений для случая 1 (1ВМ 360) Таблица 2.11б.
Результаты вычислений для случая 2 ОТВЕЙ,175 х,, к клок окко о $ ккк соо кк Фйкх к о о я к к'Вакф ко ооохох йк оо Лок о сякккя ао к к уй х о ох, х око к Ф й Ж л тп 3,77 0,271 0,108 П 3,89 0,281 0,118 1П 4,62 0,367 0,204 длине) РМАХ-го пути записан во втором столбце. В третьем н четвертом столбцах указывается общее время решения задачи и время работы подпрограммы ТКАСЕ соответственно.
Разность между этими двумя величинами равна времени работы программы, реализующей алгоритм двойного поиска. В табл. 2.11б приводятся результаты трех просчетов задачи на машинах 1ВМ 360 и СУВЕК 175. В первом столбце ука- 7 — 1664 1 г 3 4 5 б 7 1 3 4 5 б 7 1 2 3 4 5 6 7 4 8 19 29 33 39 52 5 23 11 34 40 9 50 1 9 17 25 33 41 49 20 17 30 10 9 8 6 1О 1г 21 9 5 30 7 27 30 30 28 9 30 7 5 4 5 5 5 4 4 5 5 5 5 5 5 4 5 5 5 5 5 5 5 Глава 2 наны номера вариантов. Во втором столбце — номера пользователей системы.
Третий столбец содержит номера ЫР конечных узлов сети, задаваемые каждым пользователем. В четвертом столбце указано число построенных путей из узла ЫБ=56 в узел ЫР. В рассматриваемом случае это число не должно превосходить величины РМАХ=30. В пятом столбце записывается порядковый номер (по длине) максимального из построенных путей, не содержащих циклов. Этот номер не должен превосходить К=5. В шестом и седьмом столбцах указано общее время, решения задачи иа 1ВМ 360 и С'1"ВЕК 175 соответственно, а в восьмом столбце — время выполнения подпрограммы ТКАСЕ для СУВЕЕ 175. 2.6.5. РЕЗУЛЬТАТЫ ВЫЧИСЛЕНИЙ ДЛЯ ЗАДАЧИ НАХОЖДЕНИЯ ЧЕТЫРЕХ КРАТЧАЙШИХ ПУТЕЙ Требуется найти четыре кратчайших пути из узла 1 .в каждый из узлов 10, 11 и 12 в сети, изображенной на рис.
2.27. При работе программы начальные оценки полагаются равными оо. Входные данные должны располагаться в последова- Таблица 2.12. Входные данные н модельном примере кант тг зт Набор 1: Набор 2: Набор З: Номер карты Номер карты Номаркарты Набор 4: Рамп Набор 5: ЕХ17 тельности, указанной в табл. 2.12. Отметим, что номера конечных узлов, набитые на перфокартах 1 — 31,,расположены в строго возрастающем порядке. Приводимые ниже выходные 1 4 7 ю 1З 1б 19 22 25 гв 31 З4 2 1 4 3 2 5 1 3 4 б 3 2 7 4 5 4 5 1О 3 б 2 4 7 5 7 8 8 8 9 12 9 12 2 !о ю г 5 в 11 14 17 го 23 26 29 Зг З5 3 1 4 4 2 2 2 3 5 4 г 2 5 3 6 5 '5 5 б 5 8 7 8 9 8 12 7 10 2 4 1 ЗО гг ю з 6 9 12 15 1В 21 24 г7 зо зз 1 2 4 5 2 3 5 3 2 5 4 10 3 5 2 8 5 4 9 б 3 5 8 4 б 9 3 8 11 2 и !о Детерминированные натеки в сетях Сток Сток Источник Сток Ряс. 2.27. Сеть а задаче о четырех кратчайших путях.
данные программы содержат длины четырех кратчайших путей. ДЛИНАК = 4 КРАТЧАЙШИХ В УЗЕЛ 11 ПУТЕЙ ИЗУЗЛА1 ЧИСЛО ИТЕРАЦИЙ, В РЕЗУЛЬТАТЕ ВЫПОЛНЕНИЯ КОТОРЫХ ПРОЦЕСС СХОДИТСЯ, РАВНОЕ К КРАТЧАЙШИХ ПУТЕЙ ИЗ УЗЛА 1 В УЗЕЛ 1! ПУТЬ ДЛИНА ПОСЛЕДОВАТЕЛЬНОСТЬ УЗЛОВ 11 8 5 11 8 5 11 8 5 1 11 8 5 1 11 8 5 1 П 8 5 11 8 5 1 11 8 5 11 8 7 7е 1 2 3 4 5 б 8 9 10 11 12 12 13 16 16 17 17 и 17 17 0 8 4 8 4 8 б 10 б 7 б 10 11 15 10 11 9 13 13 17 12 13.
11 15 12 13 9 1О 9 12 11 !2 ю и П 12 1б 17 14 15 14 15 18 19 16 17 16 17 3 1 2 1 3 5 3 3 б 3 2 4 2 3 2 1 3 5 2 б 3 1 4 2 1 Глава 2 К КРАТЧАЙШИХ ПУТЕЙ ИЗ УЗЛА 1 В УЗЕЛ 10 1ОО ПОСЛЕДОВАТЕЛЬНОСТЬУЗЛОВ 1О 7 4 2 1 10 7 4 2 4 1О 7 4 2 3 10 7 4 2 5 10 7 4 2 5 ПУТЬ ДЛИНА 1 13 2 17 2 ! 3 18 1 4 18 з 5 19 2 1 КРАТЧАЙШИХ ПУТЕЙ ИЗ УЗЛА 1 В УЗЕЛ 12 ПОСЛЕДОВАТЕЛЬНОСТЬ УЗЛОВ !2 9 б 3 1 12 9 6 3 5 !2 9 6' 3 б 12 9 6 3 2 12 9 б 3 5 12 9 б 5 3' 12 9 6 5 2 12 9 б 9 6 К ДЛИНА 11 15 15 16 16 16 1.7 17 ПУТЬ 1 2 з 5 7 8 з 3 1 1 2 1 1 1 3 1 2.7. АНАЛИЗ АЛГОРИТМОВ ПОИСКА КРАТЧАЙШИХ ПУТЕЙ И ОЦЕНКА ИХ СЛОЖНОСТИ Проведение анализа вычислительных алгоритмов имеет как практическое, так и теоретическое значение.
Для практических целей необходимо иметь информацию об оценках, илв верхних границах, объема машинной памяти, требуемой для работы программы, реализующей алгоритм, и времени ее прохождения. Основное теоретическое значение анализа алгоритмов заключается, по-видимому, в полученви количественных критериев, позволяющих проводить, сравнения нескольких алгоритмов решения одной и той же задачи. В настоящем разделе будут получены верхние границы объема вычислений, необходимых для реализации алгоритмов Дейкстры н Флойда и метода двойного поиска. В алгоритмах Дейкстры и Флойда выполняется только два типа элементарных операций в сложение и сравнение. Обычно предполагается, что время выполнения каждой из этих двух операций приблизительно одинаковое.
Будем также предполагать, что в наихудшем случае при работе алгоритма выполняется максимально возможное число элементарных операцвй. Это число, которое принимается за верхнюю границу объема вычислений и называется вычислительной сложностью алгоритма, является функцией размера сети и количества искомых решений (путей). Вычислительная сложность метода двойного поиска будет выражена как функция числа обобщенных операций, определенных в равд. 2.6.1. Детермимировилнме лотоки в сетях ш! 2.7.!. ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ МЕТОДА ДЕИКСТРЫ Рассмотрим сеть 0=(й(, А), содержащую и узлов, образующих множество Х. В наихудшем случае конечный узел сети будет и-и по счету узлом, которому приписывается постоянная пометка. Предположим, что в некоторый заданный момент работы алгоритма т узлам приписаны постоянные пометки, а и — т узлам — временные пометки.
Для определения (т+1) -го узла, которому должна быть приписана постоянная пометка, необходимо вычислить новые величины и т временных пометок, выполняя при этом для каждой из них операцию сложения и операцию сравнения. После вычисления новых значений временных пометок необходимо также найти минимальное среди них, чтобы определить пометку, которая должна стать постоянной. Данная процедура минимизации состоит из и т — 1 операций сравнения. Таким образом, если имеется т узлов с постоянными пометками, то число элементарных операций, которое необходимо выполнить для того, чтобы еще одному узлу приписать постоянную пометку, равно 3(и — т) — 1жЗ(и — т).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
