Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Построение коммуникационной сети минимальной длины.




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

Алгоритм построения:

1. Начать с любого узла и соединить его с ближайшим узлом. Считаем, что это связанные узлы, а все другие – несвязанные.

2. Определить несвязанный узел, ближайший к одному из связанных узлов. Если их несколько, выбрать любой. Добавить этот узел к связанным. И так до тех пор, пока есть несвязанные узлы.

Пример. Университет устанавливает компьютерную систему электронной почты между деканатами.

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

Начинаем с узла 1. Ближайший к нему узел – это узел 2 на расстоянии 2. Считаем, что узлы 1,2 – свзанные, и отметим это двойной чертой.

Ближайшие несвязанные узлы к одному из связанных узлов 1 и 2 – это узлы 3 и 6. Выбираем любой из них, например узел 3. Ребро 1-3 отметим двойной чертой и считаем узлы 1,2,3 связанными.

Далее ищем ближайший несвязанный узел к узлам 1,2,3,. И т.д.. В результате получим минимальное дерево.

Его длина равна сумме расстояний на дугах: 2+3+1+1+0,5+1+2=10,5 (км).

Задача.

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






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных