Дослідження хвильового алгоритму Лі і променевого алгоритму трасування

Мета: вивчити хвильовий алгоритм Лі і променевий алгоритм трасування та набути навичок використання.

3.1 Теоретичні відомості

Хвильовий алгоритм Лі

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

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

2. При проведенні нової траси дозволено використовувати тільки вільні місця, число яких з проведенням трас буде скорочено.

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

Місце, де починається хвиля впливів, називають джерелом, а наступні місця – спадкоємцем хвилі. Щоб мати можливість стежити за проходженням фронту хвилі впливів, його фрагментам на кожному етапі присвоюють деякі ваги:

(3.1)

де P_k і P_k-1 – ваги місць k-го і "k-1)-го фронтів;

φ(ƒ₁, ƒ₂,..., ƒ_g) – вагова функція, що є показником якості проведення шляху, кожен параметр якої ƒ_i (i=1,2,..,g) характеризує шлях з точки зору одного із критеріїв якості (довжини шляху, кількість перегинів).

На P_k накладають одне обмеження – ваги місць попередніх фронтів не повинні бути більше ваг місць наступних фронтів. Фронт буде поширено тільки на сусідні місця, які мають із місцями попереднього фронту або загальну сторону, або хоча б одну загальну точку. Процес

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

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

Щоб виключити невизначеність при проведенні шляху для випадку, коли кілька місць мають однакову мінімальну вагу, вводять поняття шляхових координат, що задають перевагу проведення траси. Кожен напрямок кодують двійковим числом за mod q, де q – число сусідніх місць.

Істотними недоліками хвильового алгоритму є мала швидкодія і великий обсяг оперативної пам'яті ЕОМ, необхідний для зберігання інформації про поточний стан всіх місць комутаційного поля, можливість побудови лише з'єднань типу "введення-виведення". Спроби усунути зазначені недоліки привели до створення ряду модифікацій хвильового алгоритму.

Модифікований алгоритм Лі (метод зустрічної хвилі)

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

Аналіз кількості місць при використанні джерела однієї або двох точок, що потрібно з'єднати. Нехай відстань між точками R, тоді для першого випадку в момент досягнення хвилею точки-приймача площа переглянутого окола дорівнює: Q⁽²⁾ πR² (знак рівності відповідає відсутності перешкод на шляху поширення хвилі). Для другого випадку в момент зустрічі фронтів двох хвиль площа переглянутого окола дорівнює:Q⁽²⁾ ≤ 2π (0,5R)² = 0,5πR².

Таким чином, при використанні методу зустрічної хвилі час, що затрачено на етапі поширення хвилі, зменшено приблизно вдвічі.

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

Променевий алгоритм трасування

У даному алгоритмі, що запропонований Л. Б. Абрайтисом, вибір місць для визначення шляху між точками A і B, що необхідно з'єднати, проводять по заданих напрямках, подібних до променів. Це дозволяє скоротити число місць, що аналізуються алгоритмом, а отже, і час на аналіз і кодування їх стану, однак приводить до зниження ймовірності знаходження шляхів складної конфігурації, і ускладнює облік конструктивних вимог до технології друкованої плати.

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

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

Промені

1. A(1): нагору, вліво.

2. A(2): уліво, нагору.

3. B(1): униз, вправо.

4. B(2): вправо, вниз.

На другому кроці промінь B(1) виявлено заблокованим, а на четвертому кроці буде блоковано і промінь A(2). Промені A(1) і B(2) зустрічаються в точці C на восьмому кроці.

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

3.2 Порядок виконання роботи

1. Відповідно до схеми з'єднань обрати елемент, що має максимальну кількість з'єднань і з'єднати даний елемент з іншими, що мають спільні безпосередні зв'язки використовуючи алгоритм Лі.

2. Виконати трасування наступних елементів на схемі. При відсутності вільних зон для продовження трасування необхідно створити наступний шар і продовжити трасування на ньому.

3. Відповідно до схеми з'єднань провести трасування, використовуючи променевий алгоритм.

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

5. Порівняти значення критеріїв.

3.3 Зміст звіту

1. Мета та цілі роботи.

2. Розрахункова частина. (Основні розрахункові формули та розрахунок)

3. Програма, написана мовою програмування (C++, C# , Pascal), що виконує задачу поставлену у лабораторній роботі.

4. Висновки.

3.4 Контрольні запитання

1. Принципи роботи алгоритму Лі.

2. Принципи роботи променевого алгоритму.

3. До якої групи алгоритмів відносяться алгоритм Лі і променевий алгоритм?

4. Які критерії використовуються для оцінювання якості трасування?

5. Поясніть трасування між двома елементами, що найбільш завантажені.

6. В якому випадку необхідно збільшувати кількість шарів при трасуванні?

3.5 Варіанти завдань

№	Схема місць	Схема з'єднань
1	2	3
1