Проведение пути с минимальным числом пересечений

При такой постановке задачи занятыми считают ячейки, в которых: а) находятся выводы конструктивных элементов,

б) имеются изгибы или пересечения ранее построенных проводников,

в) ячейки, в которых направление проводников совпадает с путевой координатой строящегося пути.

Такое определение занятости допускает пересечение проводников во взаимно перпендикулярных направлениях и запрещает их параллельное прохождение в одной ячейке.

Вес незанятой ячейки k-го фронта считаем равным весу соседней ячейки (k-1)-го фронта, если в этой ячейке нет ранее построенного проводника и на единицу больше в противном случае.

При этом в k-й фронт включаем лишь те ячейки, которые имеют минимальный вес. Это условие не позволяет расширяющемуся фронту волны пересечь построенные проводники до тех пор, пока окрестность ячейки-источника не заполнит замкнутую область, ограниченную проводниками и занятыми ячейками. Если при этом ячейка-приемник достигнута не будет, то фронт сразу пересекает все проводники, образующие границу области.

При втором и последующих пересечениях процесс повторяется.

После достижения ячейки-приемника проводник проводится согласно путевым координатам, присвоенным ячейкам в процессе распространения волны. На рисунке 7.3 показан вариант проведения пути между точками X и Y для рассматриваемого случая. Вес, присваиваемый ячейке Y, равен числу пересечений строящегося проводника с ранее проведенными.

В этом алгоритме избыточной информацией, которая не учитывается при проведении пути, является вес ячейки. От его присвоения можно отказаться, если последовательно, учитывая приоритет направления, присваивать путевые координаты всем ячейкам каждой очередной области, ограниченной проводниками, переходя от одной области к другой по мере их заполнения.

Рисунок 7.3

Параллельная оптимизация пути по нескольким параметрам в озможна.

Практически в любой задаче трассировки печатных проводников приходится учитывать не один, а несколько критериев качества. Если удается задать количественную оценку важности отдельных критериев, то задача может быть решена с помощью алгоритма Ли.

В качестве примера рассмотрим один из возможных вариантов присвоения веса незанятой ячейке k-го фронта:

1. Р_k = P_k-1 + 1 если в данной и соседних ячейках нет ранее построенных проводников и путевая координата не меняет своего направления;

2. Р_k = P_k-1 + 2, если в соседних ячейках нет ранее построенных проводников, но путевая координата меняет свое направление;

3. Р_k = P_k-1 + 3, если в данной ячейке путевая координата не меняет своего направления и нет ранее построенного проводника, но в соседней ячейке такой проводник есть;

4. Р_k = P_k-1 + 5, если в данной ячейке происходит пересечение с ранее по- строенным проводником.

!!! Для платы (рисунок 7.3) построить связь между Х и Y c учетом данных ограничений.

Недостатки волнового алгоритма Ли:

1. малое быстродействие;

2. большой объем оперативной памяти ЭВМ, необходимый для хранения информации о текущем состоянии всех ячеек коммутационного поля;

3. возможность построения лишь соединений типа «вывод - вывод».

Модификации волнового алгоритма

1. Метод встречной волны.

2. Метод соединения комплексами.

3. Лучевой алгоритм трассировки.

Метод встречной волны

В данном методе источниками волн являются обе ячейки, подлежащие электрическому объединению. При этом на каждом k-ом шаге поочередно строят соответствующие фронты первой и второй волн, распространяющихся из этих ячеек. Процесс продолжается до тех пор, пока какая-либо ячейка из фронта первой волны не попадет во фронт второй волны или наоборот. Проведение пути осуществляют изданной ячейки в направлении обоих источников по правилам, описанным в волновом алгоритме Ли.

Достоинства:

1. время, затрачиваемое на этапе распространения волны, уменьшаются примерно вдвое.

Недостатки:

1. необходимость выделения дополнительного разряда памяти на каждую рабочую ячейку поля для хранения информации о принадлежности ее к первой или второй волне.

2. возможность построения лишь соединений типа «вывод - вывод».

Метод соединения комплексами:

Пусть необходимо объединить некоторое множество точек М = {т₁, т₂, ..., m_n}.

1. Выбираем в качестве источника произвольную точку

m_i ∈ M

и распространяем из нее волну влияний до встречи с какой-либо точкой

m_j ∈ M

2. Проводим путь, соединяющий точки m_i и т_j.

3. Вновь перейдем к процессу «распространения волны», выбрав в качестве источника только что построенный проводник, и заканчиваем его при встрече с какой-либо точкой

4. Проведя путь, получаем соединение уже трех точек множества М.

5. Теперь источником волны является дерево, состоящее из построенных проводников, и т. д.

Достоинство:

1) возможность присоединения каждой очередной точки (начиная с третьей), к любой точке ранее построенных соединений,

2) сокращение общей длины печатных проводников

3) увеличение числа разводимых цепей

4) возможность построения соединений типа «вывод - проводник» и «проводник - проводник».

Быстродействие алгоритма можно повысить, применив метод встречной волны, если это позволяет объем памяти ЭВМ. В данном случае источниками «распространения волн» являются все ранее построенные проводники и ячейки, подлежащие объединению.

Для дополнительного сокращения затрат машинного времени производят неполную очистку ячеек рабочего поля после подсоединения каждой очередной точки к строящейся цепи. Для этого достаточно запомнить в специальном счетчике радиус R окрестностей, построенных до встречи на предыдущем шаге, и перед следующим шагом очистить окрестности радиусом R только тех двух источников, которые только что были соединены. Для вновь проведенного соединения строят окрестность радиусом R. Если не произошло встречи с какой-либо уже построенной окрестностью, дальнейший процесс «распространения волны» продолжается для всех источников, если встреча состоялась, то вновь переходят к проведению пути и т. д.

⇐ Предыдущая 1 234 Следующая ⇒