В ведение В настоящее время используются различные варианты волнового алгоритма, в частности, лучевой и маршрутные. Простейшим видом волнового алгоритма является волновой алг оритм нахождения кратчайшего пут и без пересечения множества занятых и запрещенных элементов (участко в печатной платы). Его целесообразно использовать при трассировке сое динений в одной плоскости, когда недопустимо выходить из пределов это й плоскости. Определяются начальная и конечная точки и моделируется распространение волны от конечной точки к начальной в направлении во лны. Недостатком этого алгоритма является то, что он мало пригоден для трассировки многослойных печатных плат, проводники прокладываются п о краям платы, значительное число длинных параллельных проводников я вляются причиной большой взаимоиндуктивности. Более совершенным волновым алгоритмом является волновой алго ритм прокладки пути с минимальным числом пересечения. В этом случае ч исло пересечений ранее проложенных трасс должно быть минимальным. Дл я преодоления недостатка этого алгоритма, при котором трассы стремят ся к одной из границ платы и прижимаются друг к другу, был предложен ал горитм для проведения пути, минимально приближающихся к другим трасс ам. Основой алгоритма является условие, при котором элементы данного соединения должны иметь минимум соседних элементов, принадлежащих ра нее проложенным трассам. Если одним из условий является требование регулярности соед инений (один слой горизонтальные, другой – вертикальные и т.п.), то удоб нее использовать волновой алгоритм прокладки пути с минимальным чис лом изменений направления, который позволяет минимизировать количес тво межслойных соединений. В отличие от волновых и лучевых алгоритмов, в которых на начальной ста дии перебираются все возможные варианты трассы, в маршрутных алгорит мах прокладка трассы ведется сразу и по кратчайшему маршруту. 1. Маршрутный алгоритм трассировки Каждый слой платы представлен в памяти ЭВМ булевой матрицей , элементы которой имеют значение 0, если соответствующий элемент своб оден для прокладки пути, и имеют значение 1, если соответствующий элеме нт занят. Все элементы матрицы, которые принадлежат исходным препятст виям, задаются единичным значением. Алгоритм реализует следующие последовательно выполняемые этапы: 1) построение пути до вст речи с препятствием; 2) обход препятствий; 3) минимизация построенн ого пути. Этап 1. Пусть требуется проложить путь между элементами d a , булевой матрицы, описывающей модель платы. При отсутствии пр епятствий между элементами можно проложить конечное множество путей , имеющих минимальную длину в выбранной геометрии. Процесс построения Р-пути (Н-пути) сводится к тому, чтобы определить такую последовательно сть элементов L =< d a , d a +1 ,…, d k ,…, d b > , что любой эле мент d k принадлежит Р-ок рестности (Н-окрестности) элемента d k -1 . Если будем рассматривать Н-окрестность, то вектор пер ехода Z k от элемента d k к элемент у d к+1 возможен только в направлениях, параллельных координ атным осям. Для случая Р-окрестности вектор перехода может иметь диаг ональные направления. На каждом шаге построения пути направление вектора перехода Z k от элемента d k к элементу d к+1 определяе тся функциями sgn ( x b - x k ), sgn ( y b - y k ), где x b , y b - координаты элемента d b пути, x k , y k - координаты э лемента d k . Правило выбора направления построения пути до встречи с препятствие м в наилучшем направлении приведено в таблице 1. Таблица 1. Фун кция Z k 0 1 2 3 4 5 6 7 sgn(x b -x k ) 1 1 0 -1 -1 -1 0 1 sgn(y b -y k ) 0 1 1 1 1 -1 -1 -1 Наим енование направлений приведено на рисунке 1. 3 2 1 4 A 0 5 6 7 Рису нок 1. Наименование направлений вектора перемещения Z k . После каждого шага построения пути необходимо по вектору перехода Z k оп ределить состояние очередного элемента d k (свободный или занятый) булево м атрицы. Рассмотрим построение Н-пути. Для описания дискретного пространства, в котором строим путь, использ уем булеву матрицу С размером m n . Кроме того, для сокращения вычислений введ ем усеченную матрицу А размером m l . Число строк в матрице А определяется ширин ой прокладываемого проводника в дискретах. При прокладке проводников шириной в один дискрет матрица А будет матрицой-строкой, только один элемент которой принимает единичное значение. Номер этого элемента о пределяется координатой x k анализируемого э лемента d k . Состояние элементов описывается через булеву функцию , где c i , j – элемент мат рицы С; a i - элемент матрицы-сторки А. Здесь через индекс j обозначается номер строки матрицы С, котор ый определяется координатой y k элемента d k . Если V =1 , то элемент d k занят, и построение пути прекращается . Дальнейшее построение осуществляется путем обхода препятствий, нач иная с элемента d k -1 , который будем называть элементом в стречи с препятствием. При построении Р-пути распознавание состояния элемента выполняется в два этапа. На первом этапе определяем, принадлежит ли элемент d k какому-либ о объекту, записанному в матрице С. Если элемент d k не принадлеж ит никакому объекту, то переходим к выполнению второго этапа, суть кот орого сводится к следующему: определяем состояние элементов, которые принадлежат одновременно Н-окрестностям элементов d k , d k -1 . Таких элементов может быть только два, причем они расположе ны диагонально. Если оба элемента заняты, то построение пути из элемен та d k -1 в d k запрещено. При построении пути в диагональных направлениях состояния элементов описывается булевой функцией , i = 1, 3, 5, 7. (1) Булевы функции V i , V i -1 , V i +1 определяются при просмотре Р-окрестности элемента d k . Если функция (1) равна нулю, то выбранный элемент свободный; в противном случае – зан ятый. Если очередной элемент d k булевой матрицы С, через который долже н пройти путь занят, то из элемента d k -1 , который назове м элементом встречи с препятствием (на рисунке 2 это элемент 1), начинает ся обход препятствия. Этап 2. Переход от элемента встречи с препятствием к следующему свободному элементу пути выполняются согл асно правилу первого шага. Правило первого шага. Этап обхода пр епятствия начинается с элемента d k встречи с препятствием в направлении Z k , двоичный код которого определяется путем сложения кода пред шествующего направления ( Z ’ ) k -1 с кодом 001 по модулю 8 при отрицательном н аправлении обхода препятствий, а при положительном обходе – с кодом 111. Если выбранное направление запрещено, то принимаем первое возможное направление. При построении пути выполняется отрицательный (правый) и положительн ый (левый) обход всей группы препятствий, лежащих между конечными элем ентами пути. В этом случае у первого элемента встречи с препятствием п уть разветвляется на два. По одному пути осуществляется обход препятс твий справа, а по другому – слева. При построении Н-пути для обхода препятствий используется алгоритм Н- слежения, а при построении Р-пути – Р-слежение. При отрицательном направлении Р-слежения двоичный код приоритетного направления опреднляется соотношением , а при положительном . Если направление с высшим приоритетом запрещено, то выбираетс я первое возможное направление с низшим приоритетом. Определяемое со отношением , где n – двоичный код чи сел из последовательности 1, 2, …,8. Суммирование по модулю 8 выполняется при отрицательном направлении с лежения, вычитание – при положительном. Важным моментом является определение элемента, в котором заканчивает ся обход препятствий и начинается построение пути в оптимальном напр авлении (по прямой к элементу d b ). Если в нужный мом ент не прекратить обход препятствий, то неизбежно зацикливание пути в округ препятствий. Элемент пути, в котором прекращается обход препятс твий, назовем элементом спуска. На рисунке 2 элементом спуска является элемент 19. Здесь приведен путь в лабиринте, построенный согласно этой методике от элемента d a к элементу d b . От элемента d a до элемента 1, который является элементом встречи, выполн яется построение пути согласно этапу 1. Обход препятствий начинается от элемента встречи 1 в отрицательном направлении (этап 2) и заканчивае тся элементом спуска 19. От элемента спуска 19 до конечного элемента пути выполняется этап 1. Для определения элемента спуска пути предлагается следующий алгорит м: a) определяем двоичный к од угла поворота вектора перехода относительно вектора Z ’ из соотношения ; причем суммирование выполняется при отри цательном направлении обхода препятствий, вычитание – при положител ьном. b) В каждом элементе излома проверяем значение двоичного кода a k и направление построения пути в наилучшем направлени и. Если a k 0 и направление обхода препятствий совпадает с наилучшим направ лением построения пути, то элемент d k будет элементом спуска. В противном случае d k не является элементом спуска. Этап 3. Минимизация длинны пути сводится к постро ению выпуклого контура, описанного вокруг первоначального пути. Если нет возможности получить выпуклый контур из-за наличия препятствий, т о строится сглаженный контур, т.е. контур, имеющий меньшую длину, чем пе рвоначальный. Находим все элементы спуска первоначального пути и разбиваем его на отдельные участки, разграниченные элементами спуска. Последовательн о минимизируем все участки пути. 1) Находим все элементы и злома соответствующего участка пути, и если имеется не более одного и злома, то он не подлежит минимизации если элементов излома два и более , то минимизация заключается в том, что строится новый путь L н ( d a , d j ) пути L ( d a , d j ), где d j - элемент излома пути, самый близкий к конечному элементу. 2) Построенный вновь подп уть L н ( d a , d j ) сравнивается по длине с путем L ( d a , d j ) , и если новый путь меньше, то L ( d a , d j ) заменяется на L н ( d a , d j ) . 3) Минимизация повторяет ся для следующего элемента излома, самого близкого к d j , и до тех пор, пока на L н ( d a , d j ) или L ( d a , d j ) останется один элемент излома. Осуществляется минимизация обоих первоначально построенных путей, полученных при положительном (левом) и отрицательном (правом) об ходе группы препятствий, из которых выбирается минимальный (рисунок 3). 2. Волновой алгоритм трассировки. Дискретное поле платы разбивают на три множества, описываемых с помощью булевых матриц: С – множество элементов поля, требующих соединения между собой (на ри сунке 4 множество , где i = 0, 1, 2, 3); Р – множество элементов поля, запрещенных для трассировки (на рисунке 4,а(б) это множество закрашено черным); S – множество своб одных элементов поля платы. Требуется, используя элементы множества S , соединить элементы множества С в одну цепь, не пересекающую Р. Процесс нахождения минимального пути состоит из двух этапов: - Распространение волны от источника до встречи с одним из приемников; - Определение пути от источ ника к приемнику. В качестве источника в ыбирается один из элементов множества С, все остальные элементы являю тся приемниками. Обозначим через R k множество элементов вол ны на шаге k и назовем его k - фронтом волны, тогда R k +1 принадлежит Н-окрестности R k . На каждом шаге расширения делается проверка пересечения фонта волны с приемником. Как только какой-либо элемент приемника буд ет включен в волну, процесс распространения волны завершается, и от бл ижайшего к источнику элемента приемника начинается построение пути. Для построения волны используются матрицы распространения волн в го ризонтальном ( R k ’ ) , и вертикальном ( R k ) направлении и матрицы точек поворота с вертикального направления на горизонтальное ( M k ) и с горизонтального направления на вертикальное ( M k ’ ), где ; ; . На рисунке 5, а - г приведе ны соответственно матрицы R k , R k ’ , M k , M k ’ , построенные для k =12 . Источником является фрагмент С 0 . Для нагля дности в клетках, занятых волной, указывается номер шага, на котором до стигнута эта точка. На этапе построения пути определяется, каким фронтом достигнут прием ник: горизонтальным или вертикальным. От элемента пересечения волны с приемником в направлении, соответствующему последнему фронту волны, определяем элементы, не принадлежащие множеству Р. При встрече с перв ым же элементом множества точек поворота рассмотренного направления движение прекращается. Все пройденные элементы включаются в искомый путь. Элемент встречи принимается за исходный для движения по другому фронту волны. Направление чередуется таким образом до тех пор, пока не будет достиг нут элемент источника. На рисунке 5, д показан пример построения пути от приемника С 1 к источнику С 0 . Стрелкам и показано направление движения. В дальнейшем процесс распространени я волны повторяется с учетом построенного пути. Такой выбор источника обеспечивает ветвление цепи в любой ее точке. Процесс заканчивается, когда все элементы С будут связаны в единую це пь (рисунок 5, е), либо когда оставшиеся элементы этого множества уже не могут быть присоединены к источнику.