Сделай Сам Свою Работу на 5

ПОСТРОЕНИЕ КОММУНИКАЦИОННОЙ СЕТИ





ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ НА ГРАФАХ

 

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

 

ЗАДАЧА ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ

 

Метод присвоения меток

Задача состоит в том, чтобы найти кратчайший путь на графе от какой-то выделенной вершины до любой другой вершины.

 

Пример: Узел 7 – склад, остальные узлы – строительные площадки компании. Показатели на дугах – расстояния в километрах.

Надо найти кратчайшие расстояния от склада до каждой строительной площадки.

Какова длина кратчайшего пути от склада до строительной площадки 1?



Проходит ли кратчайший путь от склада до строительной площадки 1 через строительную площадку 2?

Какова длина кратчайшего пути от склада до строительной площадки 2?

Проходит ли кратчайший путь от склада до строительной площадки 2 через строительную площадку 4?

 

Каждому узлу приписывают метку из двух чисел:

- первое число – минимальное расстояние от узла 7 до данного узла,

- второе – номер предыдущего узла на пути от узла 7 к данному узлу.

Помеченным называют узел, для которого определен путь от узла 7. Иначе узел – непомеченный.

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

Узлу 7 присваиваем метку (0, S), где 0 – расстояние от узла 7, S – обозначение стартового узла.

Узел 7 связан с узлами 2, 4 и 6. Им присваиваем соответствующие метки – [17, 7], [5, 7], [6, 7].

После выполнения этой операции выполняют два шага:



- находят участок минимальной длины и соответствующую временную метку делают постоянной;

- узел, которому соответствует данная постоянная метка становится новым стартом.

 

Метка с наименьшим расстоянием [5, 7] соответствует узлу 4. Этот узел объявляем помеченным и заменяем скобки у метки.

Узел 4 связан непосредственно с узлами 2 и 5 без постоянных меток. Временная метка узла 5 равна [5+4, 4]=[9, 4], а у узла 2 – [5+6, 4]= [11, 4]. Т.к. узел 2 уже имеет временную метку [17, 7], то из двух меток выбираем ту, в которой расстояние меньше, т.е. [11, 4].

Из всех временных меток [11, 4], [9, 4], [6, 7] выбираем метку с наименьшим первым числом – [6, 7]. Она становится постоянной и очередной шаг начинаем с узла 6.

Этот узел связан только с узлом 5 без постоянной метки. Временная метка узла 5 равна [6+2, 6]=[8, 6]. Эта метка имеет меньшее первое число, чем предыдущая, поэтому узлу 5 приписываем новую временную метку [8, 6].

Из всех временных меток [11, 4], [8, 6] метку с наименьшим первым числом [8, 6] объявляем постоянной и следующий шаг начинаем с соответствующего ей узла 5.

Узел 5 связан только с одним узлом без постоянной метки – узлом 3. Временная метка узла 3 равна [8+4, 5]=[12, 5].

Из всех временных меток [11, 4], [12, 5] метку с наименьшим первым числом [11, 4] объявляем постоянной и следующий шаг начинаем с соответствующего ей узла 2.

Узел 2 связан с узлами и 1 и 3 без постоянных меток. Временная метка узла 1 равна [11+15, 2]=[26, 2], а узла 3 – [11+3, 2]=[14, 2]. Т.к. узел 3 уже помечен меткой с меньшим первым числом, то метку не меняем.

Из временных меток [26, 2], [12, 5] метка с наименьшим первым числом [12, 5] становится постоянной и следующий шаг начинаем с соответствующего ей узла 3.



Метку узла 1 меняем на (12+10, 3)=(22, 3).

Всем узлам приписаны постоянные метки. Действие алгоритма прекращается.

Первое число метки у каждой вершины – это длина кратчайшего пути от узла 7 до данной вершины. Чтобы восстановить кратчайший путь от узла 7 до какой-то вершины, нужно из этой вершины перейти в соседнюю (ее номер – второе число метки) и т.д. до вершины 7.

Ответы на вопросы задачи:

Метка узла 1 – (22, 3), следовательно, длина кратчайшего пути от узла 7 до узла 1 равна 22. Чтобы определить путь, смотрим второе число метки: из узла 1 идем в узел 3. Метка узла 3 – (12, 5), следовательно, идем в узел 5. Метка узла 5 – (8, 6), следовательно, идем в узел 6. Метка узла 6 – (6, 7), следовательно, идем в узел 7. Т.о., кратчайший путь 1-3-5-6-7. Он не проходит через узел 2.

Два других вопроса – на самостоятельное рассмотрение.

 

 

ПОСТРОЕНИЕ КОММУНИКАЦИОННОЙ СЕТИ

МИНИМАЛЬНОЙ ДЛИНЫ

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

Алгоритм:

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

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

 

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

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

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

 

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

Далее ищем ближайший несвязанный узел к узлам 1, 2, 3. Это узел 7 (ближайший к узлу 3).

Ближайший несвязанный узел к узлам 1, 2, 3, 7 – узел 5 (ближайший к узлу 7).

Далее аналогично. В результате получим минимальное дерево.

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

 

 








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



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.