Постников В.М. - Методические указания к выполнению домашних заданий, страница 7

Определяем расстояния между всеми узлами сети, между которыми можно проложитькабель (формируем таблицу расстояний между узлами сети);3. Формируем очередь, элементами которой являются дуги, определяющие расстояниямежду узлами сети. Очередь формируется так, чтобы, от начала очереди к ее концу,расстояния между элементами в очереди (длины дуг) не увеличивались.4.

Последовательно просматриваем все элементы очереди (длины дуг, начиная с дугинаименьшей длины) и формируем маршрут прохождения кабеля. Если выбранная дугапозволяет подсоединить к оконечным узлам формируемого маршрута сети новые узлы,не образуя циклов (или петель), то соответствующие узлы сети соединяем этой дугой,иначе дугу отбрасываем и не включаем в маршрут.5.

Завершаем просмотр очереди расстояний между узлами сети, если все узлы сетивключены в сформированный маршрут прокладки кабеля. Далее соединяем крайние узлыполученного маршрута прокладки кабеля и получаем кольцевой маршрут.Рассмотрим решение задачи выбора маршрута прокладки кабеля для сети кольцевойархитектуры с применением метода «иди в ближний узел» на примере.Пример. Следует проложить кабель для сети кольцевой архитектуры, состоящей изпяти узлов.

Расстояния между узлами сети даны в табл П 4.1Расстояние между узлами сетиТаблица П 4.1Узлы123451*4621324*3213363*5134225*851313138*35Решение. Согласно приведенному порядку решения задачи методом “иди в ближнийузел” имеем:1. Сеть имеет пять узлов, соответственно с номерами от 1 до 5.2. Расстояния между узлами сети приведены в табл.П4.13. Формируем очередь расстояний между узлами сети, упорядоченную не по убываниюдлин лучей между узлами сети, которая имеет следующий вид:4Q14=2,Q24= 2,Q23=3,Q35=13,Q25=13,Q15=13.Q12=4,Q34=5,Q13=6,Q45=8,Просматриваем очередь и формируем маршрут прокладки кабеля.

В началерассматриваем дугу 14. Соединяем узлы 1 и 4. и получаем маршрут(1-4).Далеерассматриваем следующую дугу из очереди – дугу 24.Соединяем узлы 2 и 4 и получаем маршрут (1 – 4 - 2). После рассматриваем дугу 23,соединяем узлы 2 и 3 и получаем маршрут (1 – 4 – 2 - 3).Далее рассматриваем дугу 12. Поскольку узлы 1 и 2 уже входят в состав маршрута, апетли образовывать нельзя, то отбрасываем дугу 12.Рассматриваем следующую дугу 34. Поскольку узлы 3 и 4 уже входят в составмаршрута, а петли образовывать нельзя, то дугу 34 также отбрасываем.Рассматриваем дугу 13., Соединить узлы 1 и 3 нельзя, поскольку тогда получимкольцевой маршрут, в котором отсутствует узел 5, поэтому дугу 13 также отбрасываем.Рассматриваем дугу 45.

Узел 4 уже задействован и не является крайним в маршруте,поэтому эту дугу отбрасываем.Рассматриваем дугу 35. Соединяем узлы 3 и 5 и получаем маршрут, проходящийчерез следующие узлы:(1 – 4 – 2 – 3 - 5).Поскольку все узлы входят в состав маршрута, то кольцевой маршрут будет иметьследующий вид:узел 1узел 4узел 2узел 3узел 5узел 1O − − − − − −O − − − − − O − − − − − O − − − − − O − − − − − OS= 1 – 4 – 2 – 3 – 5 - 1.Длинамаршрутапрокладкикабеля кольцевой архитектуры равна суммелучей, входящих в состав кольцевого маршрутаL= 2+2+3+13+13=33 единицы36длинПриложение 5Выбор маршрута прокладки кабеля для сети кольцевой архитектурыс использованием метода Прима-ЭйлераМетод Прима-Эйлера использует алгоритм Прима и метод Эйлера, для решениязадачи коммивояжера.Порядок решения задачи методом Прима – Эйлера имеет следующий вид:1.

Определяем множество узлов сети (V),2. Определяем расстояние между всеми узлами сети, между которыми можно проложитькабель. Формируем таблицу расстояний между узлами сети3. С помощью алгоритма Прима строим остовое дерево. При этом сначала формируемочередь расстояний между узлами сети.

Очередьформируем так, чтобы от началаочереди к ее концу не уменьшались расстояния между узлами, т.е. длины дуг. Далеепоследовательно выбираем из очереди длины дуг, начиная с дуги минимальной длины,и строим граф. Вершинами графа являются узлы сети, а дугами – расстояния между этимиузлами сети. От каждого узла может выходить любое число дуг, но не допускаетсяобразования колец и петель.4.Строим мультиграф, каждой длине дуги сопоставляем ей идентичную.5.Строим в полученном мультиграфе. маршрут Эйлера При построении маршрута Эйлераодин узел считаем базовым, из которого осуществляем кольцевой обход мультиграфа,при этом удаляем в кольцевом маршруте все узлы, которые повторно встречаются на путиобхода этого мультиграфа.Рассмотрим пример решения задачи выбора маршрута прокладки кабеля для сетикольцевой архитектуры с применением метода Прима-Эйлера на примере.Пример.

Следует проложить кабель для сети кольцевой архитектуры, состоящей изпяти узлов. Расстояния между узлами сети даны в табл П 4.1.Выбрать маршрут прокладки кабеля сети методом Прима-Эйлера.Решение.1. Сеть имеет пять узлов, соответственно с номерами от 1 до 5.2. Расстояния между узлами сети приведены в табл.П4.13. Формируем очередь расстояний между узлами сети, упорядоченную не по убываниюдлин дуг между узлами сети, которая имеет следующий вид:Q14=2,Q24= 2,Q23=3,Q35=13,Q25=13,Q15=13.Q12=4,Q34=5,Q13=6,Q45=8,Используя алгоритм Прима, строим остовое дерево, приведенное ниже37узел 1узел 4узел 2узел 3O − − − − − −O − − − − − O − − − − − O!!Оузел 54.

Строим мультиграф, отражающий остовое дерево, который имеет следующий вид:узел 1узел 4узел 2узел 3O= = = = = =О= = = = =О= = = = = O!!!!О узел 55. В полученном мультиграфе, используя метод Эйлера, строим замкнутый маршрут,последовательно проходя через все узлы, который имеет следующий вид:5–4–1–4–2–3–2–4–5Далее из этого маршрута исключаем повторные прохождения узлов иполучаем рациональный маршрут прокладки кабеля сети кольцевой архитектуры,который проходит через следующие узлы:S=5–4–1–2–3–5При этом длина маршрутаL = 8+2+4+3+13 = 30 единиц38Приложение 6Выбор маршрута прокладки кабеля для сети кольцевой архитектурыс использованием метода ЛиттлаПорядок выбора маршрута методом Литтла имеет следующий вид:1.

Для каждой строки исходной матрицы расстояний между узлами сети находимминимальный элемент, который вычитаем из всех элементов этой строки2. Для каждого столбца, полученной измененной матрицы расстояний между узлами сети,находим минимальный элемент, который вычитаем из всех элементов соответствующегостолбца.3. Для каждого элемента a = 0 , полученной новой матрицы расстояний, находимijсумму ранее определенных минимальных элементов строки и столбца, которуюобозначаем kij4.

Находим значение krs = max k , которое соответствует элементуiji, jaij = 0 ,находящемуся на пересечении строки (r) и столбца (s). Удаляем строку (r) и столбец (s).При этом элементу матрицы asr присваиваем значение asr = ∞Затем дугу (r,s)вводим в состав маршрута прокладки кабеля.5. Скорректированную и уменьшенную по размерности матрицу расстояний междуузлами сети записываем заново .и повторяем все описанные ранее действия в пп 1-4.пока последовательно не будут определены все дуги.6. Формируем маршрут прокладки кабеля из набора полученных дуг.7.

Определяем длину маршрута прокладки кабеля.Рассмотрим решение задачи выбора маршрута прокладки кабеля для сети кольцевойархитектуры с применением метода Литтла на примере.Пример. Следует проложить кабель для сети кольцевой архитектуры, состоящейиз пяти узлов. Расстояния между узлами сети даны в табл П 4.1.Выбрать маршрут прокладки кабеля сети методом Литтла.Решение. Этап 1 Находим минимальный элемент в каждой строке таблицы и вычитаемего из всех элементов этой строки.

Минимальные элементы строк соответственно равны2,2,3,2,8., а их сумма равна 17. Получаем таблицуУзлы123451*230522*005341*354002*051111106*39Этап 2 Находим минимальный элемент в каждом столбце полученной таблицы мвычитаем его из всех элементов этого столбца. . Минимальные элементы столбцовсоответственно равны 0,0,1,0,6 , а их сумма равна 7.

Получаем таблицу:Узлы 123451*230522*005330*244002*055540*Найденные минимальные элементы в строках и столбцах – это так называемыеконстанты приведения. Их сумма по строкам и столбцам равна 24. Эта оценка снизу наданном шаге определения длины маршрута прокладки кабеля.Этап 3 Определяем дугу, исключение которой максимально увеличило быполученную оценку снизу. С этой целью заменяем поочередно каждый нулевой элементполученной матрицы на бесконечность ( ∞ ) и вычисляем сумму наименьших элементовв строке и столбе, содержащих этот элемент.aij + min aijij = minjiи krs = max kiji, jНаходим kk =2+0=2 k =0+2=21423kk4145=0+2=2k42=0+0=024=0+0=0 k =2+0=232k=0+4=4k45k =4+0=454= max kij = 4i, jВключаем дугу 45, следовательно узлы 4 и 5, в маршрут прокладки кабеля.Вычеркиваем строку 4 и столбец 5 из таблицы расстояний между узлами сети, а элементу(a54) этой таблицы присваиваем значение a54=∞Этап 4 Таблица расстояний между узлами после первой корректировки будет иметьследующий видУзлы12351*23522*05330*44002∞Повторяем этап 1.

Находим минимальный элемент в каждой строке полученной таблицыи вычитаем его из всех элементов этой строки. Минимальные элементы строксоответственно равны 0,0,0,4., а их сумма равна 4. Получаем таблицу:40Узлы 12341*23022*00330*25110∞Повторяем этап 2. Находим минимальный элемент в каждом столбце полученнойтаблицы м вычитаем его из всех элементов этого столбца. .