Розробка програмної моделі проходження лабіринтів
Структури даних та діаграми класів для розв’язання задачі
жүктеу/скачать 215.73 Kb.
|
| Структури даних та діаграми класів для розв’язання задачі
Алгоритм роботи програми Проходження лабіринтів, безумовно складається з алгоритмів і їх у світі – безліч, враховуючи тип лабіринту, алгоритмів усього два: генерація лабіринту та пошук шляху з нього. Я використав алгоритм Ейлера для генерації і «Правило руки». Суть Ейлера полягає в тому, що лабіринт не має замкнутих маршрутів, тобто таких, котрі створюють замкнуту петлю. Замкнутий маршрут виникає в тому випадку, коли існує обмеження стінками «острів», котрий не з’єднується з іншими стінками лабіринту. Лабіринт з одним, чи більше островів називається багатозв’язним [8,9]. Одним із методів складається в тому, щоб в кожній вузловій точці вибирати одне і те ж направлення. Наприклад, можна завжди повертати на крайню праву гілку. Якщо цей шлях закінчюється тупиком, слід повернутися до вузлової точки і вібрати наступну гілку. Може виявитися, що в результаті ви пройдете по кожній гілці двічі – по одному разу в кожному направленні, але зрештою ви доберетеся до цілі. На зворотному шляху можна продовжати вибирати крайні праві гілки в кожному вузлі, або кожен раз повертатимете на крайню ліву гілку. Метод вибору однієї і тієї ж – правої або лівої – гілки називається особистим правилом правої або лівої руки [8,9]. Короткий алгоритм роботи програми на рисунку 2.1. жүктеу/скачать 215.73 Kb. Достарыңызбен бөлісу:
|