тм - алгоритм, що дозволяє знайти мінімальний шлях у графі з ребрами одиничної довжини.
На двовимірної картатій мапі (матриці), що складається з В«прохіднихВ» і В«непрохіднихВ» клітин, позначена клітина старту і клітина фінішу. Мета алгоритму - прокласти найкоротший шлях від клітини старту до клітки фінішу, якщо це, звичайно, можливо. Від старту в усі напрямки поширюється хвиля, причому кожна пройдена хвилею клітина позначається як В«пройденаВ». Хвиля, у свою чергу, не може проходити через клітини, помічені як В«пройденіВ» або В«непрохідніВ». Хвиля рухається, поки не досягне точки фінішу або поки не залишиться непройденого клітин. Якщо хвиля пройшла всі доступні клітини, але так і не досягла клітини фінішу, значить, шлях від старту до фінішу прокласти неможливо. Після досягнення хвилею фінішу, від фінішу прокладається шлях до старту і зберігається в масиві. p align="justify"> Реалізація хвильового алгоритму відносна проста. У конкретному випадку використовується хвильової алгоритм з 8 напрямів. Покажемо приклад роботи алгоритму візуально:
В
Рисунок 1 - Приклад хвильового алгоритму
Алгоритм включає в себе дві стадії:
прямий хід. Прямий хід забезпечується ітераційним процесом запуску хвилі. На малюнку 1 прямий хід зображений на стадіях 1 - 5;
зворотний хід. Зворотний хід полягає в пошуку шляху, що з'єднує початковий і кінцевий стан. Зворотний хід виконується тільки у випадку, якщо під час прямого ходу хвиля досягла кінцевого стану. Зворотний хід на малюнку 1 зображена на стадії 6. br/>
. Розробка концептуальної об'єктної моделі системи
Для програмної реалізації процесу трасування використовуємо об'єктно-орієнтовану модель. Згідно даної моделі слід виділити всі основні сутності, які будуть використовуватися при реалізації процесу трасування. Розглянемо і опишемо кожну з сутностей:
контактна площадка. Контактна майданчик, яка повинна розташовуватися на полі трасування;
провідник. Шматок провідника, який з'єднує дві клітини поля трасування;
поле трасування. Поле для трасування розміром n на m, на якому будуть розташовуватися контактні площадки і провідники;
зв'язок. Контейнерна сутність. Містить у собі інформацію про зв'язок двох контактних майданчиків, яка є комбінацією контактних майданчиків і набором провідників, що забезпечують зв'язок даних майданчиків;
діаграма щільності трасування. Діаграма, на якій показана щільність заповнення поля трасування. p> Для управління даними сутностями і реалізації логіки роботи алгоритму слід створити об'єкт менеджер В«трасуванняВ». Даний об'єкт буде інкапсуліровать інформацію про поле трасування, список контактних майданчиків, зв'язків і містити діаграми густин трасування. Менеджер керуватиме життям сутностей, обмежувати доступ, забезпечувати контроль вводятьсязначень та інше. p> Безпосереднє управління з кл...
