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

 

РЕФЕРАТ
на задану тему: "Алгоритми трасування "

 

Запровадження

Нині використовуються різні варіанти хвильового алгоритму, зокрема, променевою і маршрутні.

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

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

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

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

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

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

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

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

2) обхід перешкод;

3) мінімізація побудованого шляху.

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

0 1 2 3 4 5 6 7

sgn(xb-xk)

1 1 0 -1 -1 -1 0 1

sgn(yb-yk)

0 1 1 1 1 -1 -1 -1

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

3 2 1
4 A 0
5 6 7

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

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

Для описи дискретного простору, у якому будуємо шлях, використовуємо булеву матрицю З розміром m

Схожі реферати:

Навігація