Минимизация сети

Задача минимизации сети состоит в нахождении ребер, соеди­няющих все узлы сети (т. е. каждая пара узлов соединена цепью) и имеющих минимальную суммарную длину. Очевидно, что решение задачи не должно содержась циклов. Рис. 6.1 иллюстрирует рассмат­риваемую ситуацию. На ребрах, соединяющих узлы 1, 2 и 3, указаны их длины.

Рис. 6.1.

Ясно, что в минимальной сети узел 3 соединен с узлами 1 и 2, что дает суммарную минимальную длину последо­вательности ребер 44-6=10. Если соединить узлы 1 и 2, возникнет цикл, и получающаяся сеть, конечно, не может быть мини­мальной.

Отсутствие циклов в минимальной сети естественным образом привело к ее названию — минимальное дерево-остов. В любой сети минимальное дерево-остов можно определить следующим итератив­ным процессом. Начать с любого узла и соединить его с ближайшим /злом сети. Соединенные два узла образуют теперь связное множест­ву, а остальные узлы — несвязное множество. Далее в несвязном множестве выбрать узел, который расположен ближе других (на кратчайшем расстоянии) к любому из узлов связного множества, корректировать соответствующим образом связное и несвязное множества и повторять процесс до тех пор, пока в связное множе­но не попадут все узлы сети. В случае одинаково удаленных узлов выбирать любой из них, что указывает на неоднозначность минимального дерева-остова.

Пример. Телевизионная фирма планирует создание кабельной сети (рис. 6.2) для обслуживания пяти районов-новостроек, числа на ребрах указывают длину кабеля, соединяющего соответст­вующие узлы. Узел 1 представляет телевизионный центр, а остальные узлы (2—6) соответствуют пяти новостройкам. Отсутствие

ребра между двумя узлами означает, что соединение соответствующих новостроек либо связано со слишком большими затратами, либо практически невозможно. Нужно найти такие ребра, которые потребуют минимальной длины для связи (прямой или через другие пункты) всех районов с телевизионным центром. Рис. 6.3 иллюстрирует итерационный процесс решения этой задачи. При любом выборе начального узла получается одно и то же решение. В данном примере логично начинать вычисления с узла 1, т. е. в начальный момент он соответствует множеству связных узлов». Множество «несвязных узлов» представлено узлами 2, 3, 4, 5 и 6. Символически это можно записать как

Задача о кратчайшем пути

Задача о кратчайшем пути состоит в нахождении связанных между собой дорог на транспортной сети, которые в совокупности имеют минимальную длину от исходного пункта до пункта назначе­ния. В данном разделе рассматриваются различные случаи, которые можно промоделировать и решить как задачу о кратчайшем пути. Приложения сопровождаются описанием алгоритмов решения.

Алгоритмы нахождения кратчайшего пути для сетей без циклов

Сначала рассмотрим алгоритм на численном примере.

Прежде чем описать процедуру решения, введем следующие обо­значения:

dij — расстояние на сети между смежными узлами i и j, Uj ~ кратчайшее расстояние между узлами 1 и j, U1=0. Процедура завершается, когда получено значение U7. Общая фор­мула для вычисления Uiимеет вид

Дата добавления: 2014-01-15