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

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

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

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

А як би стала вирішувати лабіринт людина? Зрозуміло, що копіювання людських дій — не єдиний спосіб досягнення розв’язку; цілком можна застосувати і інші моделі поведінки. Наприклад, таку: уявимо, що в стартовій локації ми перекинули бочку води (а ще краще, густого киселю). Рідина починає розтікатися по сторонах, поступово добираючись навіть до найвіддаленіших локацій лабіринту. Рано чи пізно вода досягне і фінішної локації: в цьому випадку треба прослідити, яким чином рідина туди потрапила — а це і буде маршрут від старту до фінішу (причому найкоротший!). Якщо киселю вже нікуди текти, а фінішна локація гак і не досягнута, це означає, що розв’язку не існує. Моделюванням такої поведінки займається алгоритм хвильового трасування.

Помітимо спочатку всі локації лабіринту нулями (це означає «локація не містить киселю»). Стартову локацію помітимо одиницею (вилили кисіль). Тепер виконуємо дії:

знайти в лабіринті локації, помічені одиницями;

для кожної з чотирьох сусідніх з нею локацій, перевірити дві умови:

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

Малюнок 2.3 ілюструє сказане.

Рис2.3 Перша ітерація алгоритму хвильового трасування

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

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

знайти в лабіринті локації помічені двійками;

для кожної з чотирьох сусідніх локацій перевірити ті ж умови;

якщо обидві умови виконані, то помічаємо сусідню локацію трійкою.

На N-й ітерації нам доведеться виконати дії:

• а) знайти в лабіринті локації, помічені числом N;
• б) для кожної з чотирьох сусідніх з нею локацій перевірити ті ж умови;
• в) якщо обидві умови виконані, позначаємо сусідню локацію числом N + 1.

Рис 2.4 Результат роботи алгоритму хвильового трасування

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

Якщо розв’язок знайдений на N-й ітерації (у нашому випадку — на восьмій), фінішна локація помічена числом N + 1. Тепер залишилося лише визначити власне шлях. Зробити це нескладно: у фінішну локацію (номер N + 1) ми потрапили з тієї сусідньої локації, яка має номер 14; у свою чергу, в неї можна потрапити з локації з номером N — 1 і т.д. Якщо в процесі визначення шляху ми знайшли дві локації, звідки можна було потрапити в поточну, можна вибрати будь-яку з них — обидва маршрути будуть оптимальними. Зрозуміло, треба стежити, щоб між сусідніми локаціями маршруту не було стіни.

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