Волновой алгоритм C. Ли

ЛАБОРАТОРНАЯ РАБОТА № 7

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ

ТРАССИРОВКИ ПЕЧАТНЫХ И ПЛЕНОЧНЫХ СОЕДИНЕНИЙ

Цель работы – исследовать эффективность алгоритмов трассировки печатных и пленочных соединений; освоить особенности алгоритмизации и программирования задач трассировки печатных соединений на современных ЭВМ волновыми и лучевым алгоритмами; приобрести навык построения математических моделей объектов конструирования, реализации и иссле-дования их при решении задачи трассировки в САПР.

СВЕДЕНИЯ ИЗ ТЕОРИИ

Многие методы трассировки печатных соединений основаны на идеях волнового алгоритма, предложенного С. Ли [1 – 4]. Он представляет собой развитие алгоритмов построения кратчайших путей в сети и позволяет на-ходить маршруты соединений, оптимальные по ряду параметров. Данный алгоритм является классическим примером использования методов динами-ческого программирования.

Волновой алгоритм C. Ли

Монтажное поле разбивается на элементарные ячейки. Размеры ячеек и их количество определяются площадью поля, допустимой плотностью располо-жения выводов элементов и проводников. В простейшем случае ячейка пред-ставляет собой квадрат со стороной h, равной расстоянию между средними линиями двух соседних печатных проводников (рис.7.1).

Рис. 7.1.

Если размеры поля по горизонтали и вертикали соответственно A_x и B_y, то получим дискретное рабочее поле (ДРП) с N_x ´ N_y ячейками:

, , (7.1)

где – символ ближайшего большего целого.

В данном ДРП (рис.7.2) определяется множество занятых ячеек, соответ-ствующее зонам, запрещенным для проведения соединений: выводы элементов, технологические области, ранее проведенные соединения и т. д. По мере прове-дения соединений множества занятых и свободных ячеек изменяются.

Основу всех модификаций волнового алгоритма С. Ли составляет процеду-ра построения оптимального в заданном смысле пути между двумя известными ячейками ДРП. Процедура состоит из двух этапов: поиска пути и проведения пути.

Рис.7.2.

На первом этапе из одной из заданных ячеек ДРП – источника моделиру-ется распространение числовой волны до тех пор, пока ее фронт не достиг второй отмеченной ячейки ДРП – цели, либо наступает момент, когда в оче-редной фронт нельзя включить ни одну новую не занятую ячейку ДРП.

В первом случае искомый путь существует, во втором – нет.

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

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