2014-09-02
1299
Это наиболее эффективный метод решения задачи трассировки с точки зрения реализации на ЭВМ. В основе метода лежат два следующих принципа:
· всякая изолированная вершина соединяется с ближайшей вершиной;
· всякий изолированный фрагмент соединяется с ближайшей вершиной кратчайшим ребром.
Расстояние от вершины до фрагмента – расстояние между этой вершиной до ближайшей к ней вершины фрагмента.
Алгоритм построения минимального дерева:
1. Для произвольного вывода цепи найти ближайший вывод
и провести соединение.
2. На каждом последующем шаге из множества свободных
выводов (не подсоединенных, изолированных вершин) выбрать тот,
который находится ближе остальных к группе уже связанных выводов,
и подсоединить его к этой группе по кратчайшему пути. Рис.7.2.1
Это способ наращивания фрагментов или последовательный способ.
Полученное дерево будет иметь минимальную суммарную длину соединений. Алгоритм наиболее эффективен при числе вершин (выводов), входящих в цепь не более 15.
Минимальное дерево, построенное по алгоритму Прима, обладает тем свойством, что степень любой вершины (число инцидентных ребер) не превышает шести.
Если при разработке монтажной схемы требуется, чтобы максимальное число проводников, подходящих к одному выводу, было больше шести, то используют алгоритм Прима с модифицированными принципами:
1. всякая изолированная вершина соединяется с ближайшей вершиной имеющей степень меньше δ;
2. всякий изолированный фрагмент соединяется с ближайшей вершиной, имеющей степень меньше δ, кратчайшим ребром.
Возможен параллельный способ наращивания фрагментов минимального дерева, т.е. одновременно строится два фрагмента и проверяется, достигла ли степень хотя бы одной вершины предельного числа δ. Если не достигла, то фрагменты соединяются. Процесс продолжается до построения дерева, связывающего все заданные вершины.
Пример параллельного алгоритма трассировки.
Дано:
· число вершин n =6, которые принадлежат одной цепи и которые надо соединить;
· максимально допустимая степень вершин δ =2;
· массивы координат всех вершин X и Y.
Необходимо построить минимальное связывающее дерево соединений.
| Х | ||||||
| У |
Введем пять вспомогательных массивов Д, А, В, Л и М.
В массив Д заносим расстояния между каждой парой вершин, номера которых записываются в массивы А и В. Расстояние между парой вершин:
—————————
Д = √(хi-хj)2 + (уi-уj)2
Массив Л показывает степень вершин. В массив М заносят метки по номеру вершин (все вершины одного фрагмента имеют один номер, что бы не было цикличности).
|
|
|
|
|
|
|
|
|
|
|
Рис.7.2.2
Рассчитываем расстояния между каждой парой вершин и заполняем массивы Д, А, В.
| Д | √10 | √13 | √17 | √17 | √41 | √2 | √10 | √10 | √2 | ||||||
| А | |||||||||||||||
| В |
Располагаем элементы массива Д. в порядке возрастания.
| Д | √2 | √2 | √10 | √10 | √10 | √13 | √17 | √17 | √41 | ||||||
| А | |||||||||||||||
| В |
В процессе построения дерева заполняем массивы Л и М, которые первоначально имеют вид:
| Л | ||||||
| М |
1шаг. Соединяем вершины 3 и 4, номера которых находятся в первой позиции массивов А и В; присваиваем им одинаковые метки (№3), степени этих вершин равны единице;
| Л | ||||||
| М |
На каждом последующем шаге выбираем очередную пару вершин, проверяем возможность их соединения и при положительном исходе проверки соединяем.
2шаг. Соединяем вершины 5 и 6:
| Л | ||||||
| М |
3шаг. Соединяем вершины 4 и 5:
| Л | ||||||
| М |
4шаг. Соединяем вершины 1 и 2:
| Л | ||||||
| М |
Получили два фрагмента.
5шаг. Соединяем вершины 1 и 6 (не с 5, т.к. будет δ>2):
| Л | ||||||
| М |
