Выбор маршрута прокладки кабеля шинной архитектуры

Метод основан на использовании алгоритма Краскала.

Порядок определения маршрута (работа алгоритма):

1) определяем множество узлов, через которое должен пройти шинный сегмент (или луч);

2) определяем расстояние между теми узлами, где можно проложить кабель. То есть, формируем матрицу расстояний;

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

4) просматриваем очередь от самого начала и последовательно выбираем из этой очереди длины лучей, формируя маршрут прокладки кабеля минимальной длины. Если луч нас устраивает, то мы включаем его в маршрут, а если нет – то нет.

Пример. Есть узлы, решаем:

1) множество узлов:

2) матрица расстояний:

№
	*
		*
			*
				*
					*

она симметричная.

3) формируем очередь:

, , , , , , , , ,

4) маршрут:

Итого: , а длина

А вот, например, поменяем местами узлы и

, , , , , , , , ,

Тогда маршрут будет:

То есть, мы можем менять местами узлы, имеющие одинаковую длину.

Короче, , а длина

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