Постников В.М. - Методические указания по выполнению ДЗ №2 - Кабельные системы АСОИиУ (1044768), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Согласно приведенному порядку решения задачи методом “иди в ближний узел” имеем:

1. Сеть имеет пять узлов, соответственно с номерами от 1 до 5.

2. Расстояния между узлами сети приведены в табл.2

3. Формируем очередь расстояний между узлами сети, упорядоченную не по убыванию

длин лучей между узлами сети, которая имеет следующий вид:

Q₁₄=2, Q₂₄= 2, Q₂₃=3, Q₁₂=4, Q₃₄=5, Q₁₃=6, Q₄₅=8,

Q₃₅=13, Q₂₅=13, Q₁₅=13.

4 Просматриваем очередь и формируем маршрут прокладки кабеля. В начале

рассматриваем дугу 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).

Поскольку все узлы входят в состав маршрута, то кольцевой маршрут будет иметь следующий вид: S= 1 – 4 – 2 – 3 – 5 - 1.

Длина маршрута прокладки кабеля кольцевой архитектуры равна сумме длин лучей, входящих в состав кольцевого маршрута

L= 2+2+3+13+13=33 единицы

Решение задачи методом Прима – Эйлера

Метод Прима-Эйлера основан на использовании алгоритма Прима и метода Эйлера, применяемых при решении задачи коммивояжера.

Порядок решения задачи методом Прима – Эйлера имеет следующий вид:

1. Определяем множество узлов сети (V),

2. Определяем расстояние между всеми узлами сети, между которыми можно проложить кабель. Формируем матрицу расстояний между узлами сети

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

4. Строим мультиграф, т.е . каждой длине дуги сопоставляем ей идентичную.

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

Согласно приведенному порядку решения задачи методом Прима – Эйлера имеем:

1. Сеть имеет пять узлов, соответственно с номерами от 1 до 5.

2. Расстояния между узлами сети приведены в табл.2

3. Формируем очередь расстояний между узлами сети, упорядоченную не по убыванию

длин дуг между узлами сети, которая имеет следующий вид:

Q₁₄=2, Q₂₄= 2, Q₂₃=3, Q₁₂=4, Q₃₄=5, Q₁₃=6, Q₄₅=8,

Q₃₅=13, Q₂₅=13, Q₁₅=13.

Далее используя алгоритм Прима, строим остовое дерево, приведенное на рис. 3.

Рис. 3 Остовое дерево

4. Строим мультиграф, который приведен на рис. 4

Рис.4. Мультиграф

5. В полученном мультиграфе, используя метод Эйлера, строим замкнутый маршрут:, который имеет следующий вид:

5 – 4 – 1 – 4 – 2 – 3 – 2 – 4 – 5

Далее из этого маршрута исключаем повторные прохождения узлов и

получаем рациональный маршрут прокладки кабеля сети кольцевой архитектуры,

который приведен на рис 5

Рациональный кольцевой маршрут, т.е. маршрут прокладки кабеля минимальной длины, проходит через следующие узлы: 5 – 4 – 1 – 2 – 3 – 5

При этом длина маршрута L = 8+2+4+3+13 = 30 единиц

Рис 5 Маршрут прокладки кабеля

Решение задачи методом Литтла

Метод (или иногда называют алгоритм Литтла) включает следующую последовательность действий:

1. Для каждой строки исходной матрицы расстояний между узлами сети находим минимальный элемент, который вычитаем из всех элементов этой строки

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

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

4. Находим значение , которое соответствует элементу , находящемуся на пересечении строки (r) и столбца (s). Удаляем строку (r) и столбец (s). При этом элементу матрицы присваиваем значение

Затем дугу (r,s) вводим в состав маршрута прокладки кабеля.

5. Скорректированную и уменьшенную по размерности матрицу расстояний между узлами сети записываем заново .и повторяем все описанные ранее действия в пп 1-4. пока последовательно не будут определены все дуги.

6. Формируем маршрут прокладки кабеля из набора полученных дуг.

7. Определяем длину маршрута прокладки кабеля.

Для примера, рассмотренного ранее, получены следующие дуги (r,s) –

45, 32, 14, 21, 53.

Последовательно соединяем дуги узлов и получаем следующий маршрут прокладки кабеля: S= 4 – 5 – 3 - 2 – 1 - 4

Длина маршрута прокладки кабеля равна L= 8+13+3+4+2= 30 единиц

Пример Исходная матрица расстояний между узлами сети имеет следующий вид

Определение наилучшего маршрута прокладки кабеля кольцевой архитектуры с использованием метода Литтла включает следующие этапы:

Этап 1 Находим минимальный элемент в каждой строке матрицы м вычитаем его из всех элементов этой строки. Минимальные элементы строк соответственно равны 2,2,3,2,8., а их сумма равна 17. Получаем матрицу:

Этап 2 Находим минимальный элемент в каждом столбце полученной матрицы м вычитаем его из всех элементов этого столбца. . Минимальные элементы столбцов соответственно равны 0,0,1,0,6 , а их сумма равна 7. Получаем матрицу:

Найденные минимальные элементы в строках и столбцах – это так называемые константы приведения. Их сумма по строкам и столбцам равна 24. Эта оценка снизу на данном шаге определения длины маршрута прокладки кабеля.

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

Находим и

Характеристики

Список файлов книги