Алгоритми трасування

РЕФЕРАТ.

на тему: «Алгоритми трасування «.

У справжнє час використовуються різні варіанти хвильового алгоритму, в частковості, променевої і маршрутные.

Найпростішим виглядом хвильового алгоритму є хвильової алгоритм перебування найкоротшого шляху без перетину безлічі зайнятих і заборонених елементів (ділянок друкованої плати). Його доцільно використовувати при трассировке сполук в однієї площині, коли неприпустимо виходити з меж цієї площині. Визначаються початкова і кінцева точки і моделюється поширення хвилі від кінцевої точки до початковій в напрямі хвилі. Недоліком цього алгоритму є то, що він мало придатний для трасування багатошарових друкованих плат, провідники прокладаються по краях плати, значне число довгих паралельних провідників є причиною великий взаимоиндуктивности.

Більше досконалим хвилевим алгоритмом є хвильової алгоритм прокладки шляху з мінімальним числом перетину. У цьому разі число перетинань раніше прокладених трас має бути мінімальним. Для подолання нестачі цього алгоритму, при якому траси прагнуть до однієї з кордонів плати і притискаються друг до другу, був запропонований алгоритм для проведення шляху, мінімально майбутніх до іншим трасам. Основою алгоритму є умова, при якому елементи даного сполуки повинні мати мінімум сусідніх елементів, що належать раніше прокладеними трасам.

Якщо одним з умов є вимога регулярності сполук (один шар горизонтальні, інший — вертикальні і т.п.), то зручніше використовувати хвильової алгоритм прокладки шляху з мінімальним числом змін напрями, який дозволяє мінімізувати кількість межслойных соединений.

У відмінність від хвильових і променевих алгоритмів, в яких на початковій стадії перебираються все можливі варіанти траси, в маршрутних алгоритми прокладка траси ведеться відразу і по щонайкоротшого маршруту.

1. Маршрутний алгоритм трассировки.

Кожен шар плати представлений в пам’яті ЕОМ булевой матрицею, елементи якої мають значення 0, якщо відповідний елемент вільний для прокладки шляху, і мають значення 1, якщо відповідний елемент зайнятий. Усі елементи матриці, які належать вихідним перешкодам, задаються одиничним значением.

Алгоритм реалізує такі послідовно що їх этапы:

1) побудова шляху до зустрічі з препятствием;

2) обхід препятствий;

3) мінімізація побудованого пути.

Етап 1. Нехай потрібно прокласти шлях між елементами da, булевой матриці, яка описує модель плати. При відсутності перешкод між елементами можна прокласти кінцеве безліч шляхів, мають мінімальну довжину в обраної геометрії. Процес побудови Р-пути (Н-пути) зводиться до тому, щоб визначити таку послідовність елементів L=, що будь-який елемент dk належить Р-окрестности (Н-окрестности) елемента dk-1.

Якщо будемо розглядати Н-окрестность, то вектор переходу Zk від елемента dk до елементу dк+1 може бути лише в напрямах, паралельних координатным осях. Для випадку Р-окрестности вектор переходу може мати діагональні направления.

На кожному кроці побудови шляху напрям вектора переходу Zk від елемента dk до елементу dк+1 визначається функціями sgn (xb-xk), sgn (yb-yk), де xb, yb — координати елемента db шляху, xk, yk — координати елемента dk.

Правило вибору напрями побудови шляху до зустрічі з перешкодою в найкращому напрямі наведено в таблиці 1.

Таблиця 1.

Функція.

Zk.

sgn (xb-xk).

— 1.

— 1.

— 1.

sgn (yb-yk).

— 1.

— 1.

— 1.

Найменування напрямів наведено на малюнку 1.

A.

Малюнок 1. Найменування напрямів вектора переміщення Zk.

Після кожного кроку побудови шляху необхідно по вектору переходу Zk визначити стан чергового елемента dk (вільний чи зайнятий) булево матриці. Розглянемо побудова Н-пути.

Для описи дискретного простору, в якому будуємо шлях, використовуємо булеву матрицю З розміром m? n. Крім того, для скорочення обчислень введемо усічену матрицю, А розміром m? l. Кількість рядків в матриці А визначається шириною прокладываемого провідника в дискретах. При прокладанні провідників шириною в один дискрет матриця, А буде матрицой-строкой, лише один елемент якої приймає одиничне значення. Номер цього елемента визначається координатою xk аналізованого елемента dk.

Стан елементів описується через булеву функцию.

.

де ci, j — елемент матриці З; ai — елемент матрицы-сторки А.

Тут через індекс j позначається номер рядки матриці З, який визначається координатою yk елемента dk.

Якщо V=1, то елемент dk зайнятий, і побудова шляху припиняється. Подальше побудова здійснюється шляхом обходу перешкод, починаючи з елемента dk-1, який називатимемо елементом зустрічі з препятствием.

При побудові Р-пути розпізнавання стану елемента виконується в два етапу. На першому етапі визначаємо, належить чи елемент dk якомусь об'єкту, записаному в матриці З. Якщо елемент dk не належить ніякому об'єкту, то переходимо до виконання другого етапу, суть якого зводиться до наступному: визначаємо стан елементів, які належать одночасно Н-окрестностям елементів dk, dk-1. Таких елементів може бути лише два, причому вони розташовані діагонально. Якщо обидва елемента зайняті, то побудова шляху з елемента dk-1 в dk запрещено.

При побудові шляху в діагональних напрямах стану елементів описується булевой функцией.

i=1, 3, 5, 7. (1).

Булевы функції Vi, Vi-1, Vi+1 визначаються при перегляді.

Р-окрестности елемента dk. Якщо функція (1) дорівнює нулю, то обраний елемент вільний; в противному разі - занятый.

Якщо черговий елемент dk булевой матриці З, через який повинен пройти шлях зайнятий, то з елемента dk-1, який назвемо елементом зустрічі з перешкодою (на малюнку 2 це елемент 1), починається обхід препятствия.

Етап 2. Перехід від елемента зустрічі з перешкодою до наступному вільному елементу шляху виконуються відповідно до правилу першого шага.

Правило першого кроку. Етап обходу перешкоди починається з елемента dk зустрічі з перешкодою в напрямі Zk, двоїчний код якого визначається шляхом складання коду попереднього напрями (Z')k-1 з кодом 001 по модулю 8 при негативному напрямі обходу перешкод, а при позитивному обході - з кодом 111.

Якщо обраний напрям заборонено, то приймаємо перше можливе направление.

При побудові шляху виконується негативний (правий) і позитивний (лівий) обхід всієї групи перешкод, лежачих між кінцевими елементами шляху. У цьому разі у першого елемента зустрічі з перешкодою шлях розгалужується на два. По одному шляху здійснюється обхід перешкод справа, а по іншому — слева.

При побудові Н-пути для обходу перешкод використовується алгоритм Н-слежения, а при побудові Р-пути — Р-слежение.

При негативному напрямі Р-слежения двоїчний код пріоритетного напрями опреднляется соотношением.

.

а при положительном.

.

Якщо напрям з вищим пріоритетом заборонено, то вибирається перше можливе напрям з нижчим пріоритетом. Обумовлений соотношением.

.

де n — двоїчний код чисел з послідовності 1, 2, …, 8.

Підсумовування по модулю 8 виконується при негативному напрямі спостереження, віднімання — при положительном.

Важливим моментом є визначення елемента, в якому закінчується обхід перешкод і починається побудова шляху в оптимальному напрямі (по прямий до елементу db). Якщо в потрібний момент не припинити обхід перешкод, то неминуче зациклення шляху навколо перешкод. Елемент шляху, в якому припиняється обхід перешкод, назвемо елементом спуску. На малюнку 2 елементом спуску є елемент 19. Тут наведено шлях в лабіринті, побудований відповідно до цієї методиці від елемента da до елементу db. Від елемента da до елемента 1, який є елементом зустрічі, виконується побудова шляху відповідно до етапу 1. Обхід перешкод починається від елемента зустрічі 1 в негативному напрямі (етап 2) і закінчується елементом спуску 19. Від елемента спуску 19 до кінцевого елемента шляху виконується.

етап 1.

Для визначення елемента спуску шляху пропонується наступний алгоритм:

a) визначаємо двоїчний код кута повороту вектора переходу щодо вектора Z' з соотношения.

;

причому підсумовування виконується при негативному напрямі обходу перешкод, віднімання — при положительном.

b) У кожному елементі зламу перевіряємо значення двоичного коду ak і напрям побудови шляху в найкращому напрямі. Якщо ak?0 і напрям обходу перешкод збігається з найкращим напрямом побудови шляху, то елемент dk буде елементом спуску. У противному разі dk не є елементом спуска.

Етап 3. Мінімізація довгі шляху зводиться до побудові опуклого контуру, описаного навколо початкового шляху. Якщо немає можливості отримати опуклий контур через наявності перешкод, то будується згладжений контур, тобто. контур, має меншу довжину, ніж первоначальный.

Знаходимо все елементи спуску початкового шляху і розбиваємо його на окремі ділянки, розмежовані елементами спуску. Послідовно мінімізуємо все ділянки пути.

1) Знаходимо все елементи зламу відповідного ділянки шляху, і якщо є не більш одного зламу, то він не підлягає мінімізації якщо елементів зламу два і більш, то мінімізація полягає в тому, що будується новий шлях Lн (da, dj) шляху L (da, dj), де dj — елемент зламу шляху, самий близький до кінцевому элементу.

2) Збудований знову подпуть Lн (da, dj) порівнюється по довжині з шляхом L (da, dj), і якщо новий шлях менше, то L (da, dj) замінюється на Lн (da, dj).

3) Мінімізація повторюється для наступного елемента зламу, самого близького до dj, і до тих пір, поки на Lн (da, dj) чи L (da, dj) залишиться один елемент излома.

Здійснюється мінімізація обох спочатку побудованих шляхів, отриманих при позитивному (лівому) і негативному (правом) обході групи перешкод, з яких вибирається мінімальний.

(малюнок 3).

2. Хвильової алгоритм трассировки.

Дискретне полі плати розбивають на три безлічі, описуваних з допомогою булевых матриц:

З — безліч елементів поля, потребують сполуки між собою (на малюнку 4 безліч, де i=0, 1, 2, 3);

Р — безліч елементів поля, заборонених для трасування (на малюнку 4, а (б) це безліч закрашено черным);

P.S — безліч вільних елементів поля платы.

Потрібна, використовуючи елементи безлічі P. S, з'єднати елементи безлічі З в одну ланцюг, не що перетинає Р.

Процес перебування мінімального шляху полягає з двох этапов:

* Поширення хвилі від джерела до зустрічі з одним з приемников;

* Визначення шляху від джерела до приемнику.

У ролі джерела вибирається один з елементів безлічі З, все інші елементи є приймачами. Означимо через Rk безліч елементів хвилі на кроці k і назвемо його k-фронтом хвилі, тоді Rk+1 належить Н-окрестности Rk.

На кожному кроці розширення робиться перевірка перетину фонта хвилі з приймачем. Як лише будь-якої елемент приймача буде включений в хвилю, процес поширення хвилі завершується, і від найближчого до джерелу елемента приймача починається побудова пути.

Для побудови хвилі використовуються матриці поширення хвиль в горизонтальному (Rk'), і вертикальному (Rk) напрямі і матриці точок повороту з вертикального напрями на горизонтальне (Mk) і з горизонтального напрями на вертикальне (Mk'), где.

;

;

.

На малюнку 5, а — р наведено відповідно матриці Rk, Rk', Mk, Mk', побудовані для k=12. Джерелом є фрагмент С0. Для наочності в клітинах, зайнятих хвилею, вказується номер кроку, на якому досягнуто ця точка.

На етапі побудови шляху визначається, яким фронтом досягнуть приймач: горизонтальним чи вертикальним. Від елемента перетину хвилі з приймачем в напрямі, відповідному останньому фронту хвилі, визначаємо елементи, не належать безлічі Р. При зустрічі з першим ж елементом безлічі точок повороту розглянутої напрями рух припиняється. Усі пройдені елементи включаються в шуканий шлях. Елемент зустрічі приймається за вихідний для руху по іншому фронту волны.

Напрям чергується таким чином до тих пір, поки не буде досягнуть елемент источника.

На малюнку 5, буд показаний приклад побудови шляху від приймача С1 до джерелу С0. Стрілками показано напрям руху. У подальшому процес поширення хвилі повторюється з урахуванням побудованого шляху. Такий вибір джерела забезпечує галуження ланцюга в будь-який її точке.

Процес закінчується, коли все елементи З будуть пов’язані в єдину ланцюг (малюнок 5, е), або коли решта елементи цього безлічі вже не можуть бути приєднано до источнику.