Розділ ii.розв'язання лабіринту

Розв’язання лабіринту

Отже, лабіринт створений і завантажений у пам’ять комп’ютера. Тепер потрібно навчитись розв’язувати його. Під розв’язуванням мається на увазі пошук шляху з деякої стартової локації в іншу (фінішну). Стартова і фінішна локації не фіксовані, тобто ми можемо спробувати вирішити лабіринт для будь-якої пари локацій. Ми зупинимось на двох найбільш популярних і часто використовуваних методах: рекурсивному обході і алгоритмі хвильового трасування.

Рекурсивний обхід

Рекурсія — спосіб організації обробки даних, за якого програма викликає безпосередньо сама себе, або з інших програм.

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

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

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

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

Рис 2.1 Розв’язок, знайдений за допомогою рекурсивного обходу

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

Недоліки алгоритму:

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

Рис 2.2Проблематичний лабіринт для процедури рекурсивного обходу

лабіринт трасування алгоритм.