|
||
Модели и методы для выбора структуры ВСРасчет структуры вычислительной сети древовидной конфигурации(Алгоритм Прима) Расчет структуры вычислительной сети иерархической древовидной конфигурации
2002, Номер1 (2) |
||
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Расчет структуры вычислительной сети
древовидной конфигурации (Алгоритм Прима) Абросимов Л.И. Даны узлы вычислительной сети, расположенные как показано на рис. 1 Требуется построить древовидную кратчайшую связанную сеть (КСС), так чтобы ее суммарная взвешенная длина Q была минимальной.
4 5 7 2 6 3 Рис. 1 Матрица M расстояний между узлами имеет вид, представленный на рис. 2
Рис. 2 Процедуру решения рассмотрим по шагам. 1-й шаг. В матрице М ищем два элемента с минимальным
расстоянием между узлами. Для этого
просматриваем матрицу М расстояний поэлементно и ищем минимум. Находим элементы m21 = m12=25. Узлы составляют фрагмент КСС в виде множества Ф={1,2} Целевая функция Q=25. Вычёркиваем 1-й и 2-й столбцы в матрице М и заполняем матрицу Х. Матрица М расстояний(после 1-го шага) Матрица Х связности (после 1-го шага)
Рис. 3 Рис. 4
1. Так выглядит получившийся после 1-го шага фрагмент Ф. Ищем ближайший к нему узел сети, т. е. считаем фрагмент Ф отдельным узлом и проверяем пространство вокруг в поисках ближайшего узла. 2 Рис.
5 2-й шаг. Просматриваем в матрице М, которую получили после предыдущего шага, (см. рис. 3) строки 1 и 2 в поисках минимального элемента. Это m14=31. Аналогично получаем Ф={1,2,4} и Q=25+31=56. Вычеркиваем 4-й столбец матрицы М и корректируем матрицу Х связности. Матрица М расстояний (после 2-го шага) Матрица Х связности (после 2-го шага)
Рис.
6 Рис.
7 Полученный после второго шага фрагмент имеет вид, представленный на рис.7
1 4 2 Рис.
8 3-й шаг. Просматриваем в матрице М предыдущего шага строки 1, 2 и 4 (см рис. 6) в поисках минимального элемента. Это m23=32. В фрагмент добавляется узел 3. Ф={1,2,3,4} и Q=56+32=88. Вычёркиваем 3-й столбец матрицы М и корректируем матрицу Х связности. Матрица М расстояний (после 3-го шага) Матрица Х связности (после 3-го шага)
Рис. 9 Рис.10
Фрагмент сети 4 2 Рис.
11 3 4-й шаг. Просматриваем в матрице М предыдущего шага строки 1, 2 ,3и 4 (см рис. 9) в поисках минимального элемента. Это m45=33. В фрагмент добавляется узел 5. Ф={1,2,3,4,5} и Q=88+33=121. Вычёркиваем 5-й столбец в матрице М и корректируем матрицу Х связности. Матрица М расстояний (после 4-го шага) Матрица Х
связности (после 4-го шага)
Рис. 12 Рис.
13
Фрагмент сети 4 5 2 Рис. 14 3 5-й шаг. Просматриваем в матрице М предыдущего шага
строки 1, 2 ,3, 4 и 5 (см рис. 12) в поисках минимального элемента. Это m56=32. В фрагмент
Ф добавляется узел 6. Ф={1,2,3,4,5,6} и Q=121+32=153. Вычеркиваем 6-й столбец и корректируем матрицу связности. Матрица расстояний (после 5-го шага) Матрица Х
связности (после 5-го шага)
Рис. 15 Рис.
16
4 5 2
6 3 Рис
17 6-й шаг Просматриваем в матрице М предыдущего шага строки 1, 2 ,3, 4, 5 и 6 (см рис. 15) в поисках минимального элемента. Это m57=39. В фрагмент Ф добавляется узел 7. Ф={1,2,3,4,5,6,7} и Q=153+39=192. Вычёркиваем 7-й столбец и корректируем матрицу связности.
Матрица Х связности
Рис.
18 Кратчайшая связывающая сеть, полученная в результате расчета, имеет вид,
представленный на рис. 19.
4 5 7 2
6 3 Рис
19 Все узлы соединены , работа алгоритма заканчивается. ЛИТЕРАТУРА |
