2014-09-02
1399
Это наиболее эффективный метод решения задачи трассировки с точки зрения реализации на ЭВМ. В основе метода лежат два следующих принципа:
· всякая изолированная вершина соединяется с ближайшей вершиной;
· всякий изолированный фрагмент соединяется с ближайшей вершиной кратчайшим ребром.
Расстояние от вершины до фрагмента – расстояние между этой вершиной до ближайшей к ней вершины фрагмента.
Алгоритм построения минимального дерева:
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):
| Л | ||||||
| М |
