Трассировка с помощью алгоритма Прима

Трассировка с помощью алгоритма Прима. На основании полученных ранее данных и требований задания проведем трассировку общего провода цепи питания печатной платы блока оперативной памяти методом Прима. Для этого приведём необходимый участок печатной платы в сетке с шагом 5. Вывод 1 разъёма должен быть соединён с выводами 7 DD1-DD13. Пронумеруем точки соединений от 1 до 14. DD10 DD11 DD13 DD12 5 6 11 12 DD9 DD8 DD6 DD7 4 7 10 13 DD5 DD2 DD3 DD4 3 8 9 14 DD1 2 1 Рис. 3.1 Для эскиза платы рис. 3.1 составим матрицу расстояний 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 0 10 21 31 43 36 22 12 22 34 45 61 53 31 2 10 0 13 24 35 44 33 22 31 43 55 64 52 40 3 21 13 0 13 24 33 22 11 20 31 42 51 40 29 4 31 20 13 0 13 22 11 22 31 20 31 40 29 40 5 13 11 24 13 0 11 22 31 40 31 20 29 40 51 6 41 22 33 22 11 0 13 21 20 33 24 22 13 32 7 50 31 22 11 22 13 0 13 29 42 33 14 24 41 8 22 13 11 22 31 21 13 0 11 24 13 31 22 25 9 24 20 20 31 40 20 29 11 0 13 22 39 31 34 10 34 31 31 20 31 33 42 24 13 0 13 29 20 45 11 45 24 42 31 20 24 33 13 22 13 0 11 11 37 12 61 42 51 40 29 22 14 31 39 29 11 0 13 52 13 53 33 40 29 40 13 24 22 31 20 11 13 0 13 14 10 12 29 40 51 32 41 25 34 45 37 52 13 0 Трассировка по алгоритму Примма заключается в следующей последовательности 1 Берём любую точку в качестве стартовой. 2 Задаёмся ограничением на локальную степень вершины кол-во возможных связей . 3 По матрице расстояний находим точку наиболее близкую к любой из уже задействованых точек. 4 Если у обеих вершин ограничение локальной степени недостигнуто, проводим связь между двумя найдеными точками и зачёркиваем в матрице расстояний столбец соотв. этой вершине, иначе возвращаемся к п. 3. 5 Повторяем пункты 3-4 пока все точки не будут соеденены все столбцы вычеркнуты. Проведём трассировку методом Примма корпусной цепи питания.

В качестве стартовой берём точку 1 и вычёркиваем столбец 1. Локальную степень вершины принимаем равной 4. Самая короткая связь по матрице расстояний у неё с тчк. 2. Проводим связь.

Рассматриваем две строки - 1-ю и 2-ю. Самая короткая связь между 1 и 8, между которыми и проводится следующая связь.

Вычёркивается столбец 2. Теперь рассматриваем три строки - 1-ю, 2-ю, и 8-ю. Наименьшее расстояние имеется между 8 и 3, 8 и 9. Проводим эти связи вычёркивая соотв. столбцы.

И т.д. Повторяем до тех пор, пока все точки не будут соеденены т.е. все столбцы матрицы смежности будут вычеркнуты. Полученый результат виден на рис. 3.1. 3.2