2.2.Построение коммуникационной сети
минимальной длины
Коммуникационная сеть минимальной длины, или дерево кратчайших расстояний, - это совокупность дуг сети, имеющая минимальную суммарную длину и обеспечивающая достижение всех узлов сети.
Пример
Региональный вычислительный центр должен установить специальные линии связи между пятью локальными потребителями и новым сервером. Чтобы сократить затраты, руководство центра решило, что общая протяженность линий связи в сети должна быть минимальной. Хотя сервер может быть связан с каждым потребителем в отдельности, более экономичным было бы установить прямую связь с частью потребителей, а остальных связать с сервером через потребителей, которые уже получили эту связь (рис.2.10).
Рис.2.10
Шаг 1. Начинаем произвольно с любого узла и соединяем его с ближайшим узлом. Эти два узла теперь рассматриваются как связанные узлы, а остальные – как несвязанные узлы.
Шаг 2. Определяем несвязанный узел, который наиболее близок к одному из связанных узлов. Если два или более узлов можно рассматривать как ближайшие, то выбираем любой из них. Добавляем этот узел к связанным узлам. Повторяем этот шаг до тех пор, пока все узлы не станут связанными.
Используя жирные линии для пометки дуги, обеспечивающей соединение узлов, приходим к следующему результату, характеризующему шаг 1 (рис.2.11).
Рис.2.11
Повторение шага, заключающегося в добавлении ближайшего несвязанного узла к связанному сегменту сети (рис.2.12), дает нам решение задачи о дереве кратчайших расстояний, показанное на рис. 2.13.
Рис.2.12
Сумма расстояний в сети регионального центра составляет 110 км.
Рис.2.13
Заметим, что хотя дуги сети вычислительного центра измерялись в километрах, другие сетевые модели могут характеризоваться другими показателями – затратами, временем и т.д. В таких случаях алгоритм дерева кратчайших расстояний будет приводить к оптимальному решению (минимальные затраты, минимальное время и т.д.) применительно к рассматриваемому критерию.
Задача 2.2
Вариант 1
Найдите дерево кратчайших расстояний для следующей сети службы пожарной безопасности.
Какова минимальная длина связанного дерева?
Вариант 2
В Москве возможно строительство нового парка. Дизайнеры определили идеальные места расположения павильонов, торговых палаток, пикников, лодочных станций, открытых сцен и т.д. Эти места представлены узлами на сети, приведенной ниже. Дуги сети отражают возможные альтернативы дорожек в парке. Дизайнеры хотят минимизировать общую протяженность дорожек, которые требуется провести в парке, и при этом обеспечить доступ ко всем узлам. Какое решение вы им предложите?
Какова минимальная общая протяженность дорожек?
Вариант 3
На большом предприятии по производству мыла инспекторы осуществляют контроль качества на различных производственных участках, а затем возвращаются в лабораторию с образцами продукции для анализа. Процесс инспектирования слишком затянут, так как инспекторы тратят значительное время на доставку образцов с производственных участков в лабораторию. Компания рассматривает возможность установки пневматических труб, которые можно было бы использовать для доставки образцов. Сеть отражает расположение лаборатории и производственных участков, на которых берутся образцы. Дуги представляют собой альтернативы конвейерной системы. Расстояния на дугах сети показаны на сотнях метров. Каковы минимальная общая длина системы, которая позволит посылать образцы в лабораторию?
Какова минимальная общая протяженность конвейера?
Вариант 4
Московский университет устанавливает компьютерную систему электронной почты, которая позволит передавать сообщения между деканатами восьми факультетов. Сеть возможных электронных связей между деканатами показана ниже. Протяженность коммуникаций в километрах отмечена на дугах. Предложите проект системы связи, которая позволит всем восьми деканатам обеспечить доступ к системе электронной почты. Ваше решение должно обеспечить минимально возможную общую длину коммуникаций.
