2014-09-02
1046
Дерево Штейнера - граф без замкнутых циклов, вершины которого связаны линиями, проходящими параллельно осям Х и У в декартовой системе координат.
Суммарная длина связей у такого графа должна быть минимальной. Отличие его от алгоритма Прима:
· соединение вершин идет по сторонам прямоугольника, а не под углом;
· в процессе работы добавляются новые вершины из-за Т-образных соединений.
Существует большое число алгоритмов для построения минимального дерева Штейнера.
Один вариант построения дерева Штейнера.
Дано множество точек на плоскости (множество выводов одной цепи) С={с1, с,2, …,сn}
Требуется найти дерево Т=(X, V) с множеством вершин Х и множеством ребер V, для которого С Ì Х и суммарная длина ребер минимальна.
Рис.7.2.2
Строим матрицу расстояний. Метрика ортогональная, т.к. при машинной трассировке печатных соединений используется ортогональная сетка магистралей. Сетка имеет шаг равный 1ед. длины.
| l1 l2 l3 l4 l5 l6 | |
| l1 | 0 4 3 6 7 8 |
| l2 | 4 0 3 4 7 8 |
| l3 | 3 3 0 3 4 5 |
| D = l4 | 6 4 3 0 3 4 |
| l5 | 7 7 4 3 0 1 |
| l6 | 8 8 5 4 1 0 |
Выбираем 1-ю по порядку вершину (любую). По матрице расстояний находим ближайшую вершину, строим охватывающий прямоугольник. По какой стороне прокладывать трассу? Рассмотрим следующую ближайшую к этой паре вершину (2), строим охватывающий прямоугольник. Путь пойдет по общей стороне двух построенных прямоугольников. При параллельном методе рассмотрим следующую пару вершин (4 и 5). Строим охватывающий прямоугольник. Далее строим охватывающий прямоугольник для вершин 3 и 4, прокладываем трассу. Прямоугольник между 5 и 6 вершиной вырождается в линию.
|
|
|
Получаем дерево Штейнера, а именно граф без замкнутых циклов.
Второй вариант построения дерева Штейнера при тех же данных.
Строим матрицу расстояний, подсчитываем суммы по строкам. Выявляем вершину, имеющую минимальное расстояние до остальных и составляем список вершин по возрастанию (строим очередь). Очевидно, что первая вершина находится в центре коммутационного поля. Следующая вершина, ближайшая к центру коммутационного поля (к первой вершине). Через эти вершины строится охватывающий прямоугольник. Выбор последующих вершин идет по спирали. Далее выбираются по порядку из списка следующие вершины, строится охватывающий прямоугольник. Сравнение. Выбор пути по общей стороне этих прямоугольников или по приоритетному направлению. (В PCAD - север-юг, восток-запад). Считается суммарная длина соединений.
Несмотря на различия в построении дерева Штейнера, все варианты дают приблизительно одинаковый результат (суммарную длину соединений). Но не дают идеального варианта соединений вершин.
|
|
|
Деревья печатных соединений могут быть построены с помощью волнового алгоритма. Что позволяет учесть различные ограничения на возможное расположение отдельных цепей. Например, недопустимость их пересечений или равномерность расположения соединений (особенно при числе вершин>15).
