Результаты размещения

3. Трассировка цепей питания и земли с использованием алгоритма построения кратчайших связывающих цепей

Трассировка - прокладка электрических трасс, проводов (при проводном монтаже), дорожек.

Трассировку соединений осуществляют с помощью алгоритмов, основанных на методах динамического программирования. Общим для этих алгоритмов является разбиение монтажного поля на ячейки, размер и форма которых определяют плотность и конфигурацию печатных проводников. Наибольшее распространение на практике получило разбиение рабочего поля на правильные квадраты, что обеспечивает простую адресацию ячеек в прямоугольной системе координат и привычную форму соединений. Размеры ячеек определяются конструктивно - технологическими требованиями, предъявляемыми к печатному монтажу. Так как в каждой ячейке обычно размещается только один вывод или печатный проводник, максимальные размеры ячеек определяются допустимой точностью воспроизведения проводников.

Алгоритм Краскала (цепи земли)

Строится кратчайшая связывающая сеть путем последовательного присоединения к ней ребер, удовлетворяющих следующим условиям:

·        ребро минимально

·        ребро инцидентно только по одной вершине

·        присоединение рассматриваемого ребра не приводит к повышению степени любой вершины больше заданного числа

Последовательность:

·        на множестве вершин строится полный граф, задаются матрица расстояний

·        упорядочиваются ребра в порядке возрастания их длины

Построение КСС осуществляется путем последовательного выбора ребер удовлетворяющих трем условиям, при этом формируется массив индексов ребер. Условием получения покрывающего дерева является вычерчивание всех номеров вершин в массиве номеров.

1)     Матрица расстояний

Рис.4

Матрица длин

Страницы: 1, 2, 3, 4, 5, 6