ВИКОРИСТАННЯ АЛГОРИТМІВ КЛІТИННИХ АВТОМАТІВ В ЗАДАЧАХ ПОШУКУ МІНІМАЛЬНОГО ШЛЯХУ
Анотація
роботі розглядається використання клітинних автоматів для удосконалення пошуку найкоротшого шляху між об'єктами, на шляху до яких є перепони. В запропонованому алгоритмі, за основу взято клітинний автомат, а саме гра «Життя). Правила побудови структури клітинного автомату вимагають змін, в залежності від вимог, що стоять перед користувачем. В статті наведений можливий варіант пошуку найкоротшого шляху за допомогою клітинного автомату на прикладі гри. Метою гри є дістатись певної наперед заданої клітинки ігрового поля за мінімальну кількість кроків. Задача має багато аналогів та використовується в різних сферах науки від звичайних ігр до закритих військових стратегій.
Розглянуті існуючі аналоги алгоритмів пошуку найкоротшого шляху володіють рядом недоліків. До них можна віднести роботу лише з структурою графів, знаходження найкоротшого шляху тільки з однієї вершини та інші. Також існує недолік, що притаманний всім методам - вони завжди намагаються просуватися в напрямку мети, навіть якщо це неправильний шлях. Ці недоліки приводять до збільшення часу реалізації алгоритму, застрягання персонажів в кутках та між перепонами.
В наведеному алгоритмі поле розглядається як елемент поля клітинного автомату. На першому кроці випадковим чином генеруються перешкоди, що не зникають протягом всієї гри. Визначаємо клітину, як об’єкт який рухається по певному набору правил, що залежать від заповнення сусідніх клітин. Якщо на даній позиції є перешкода руху, то в залежності від того який об’єм займає фігура присвоюємо значення 1 або 0 в характеристичній матриці відповідної розмірності. Правила руху визначаються наявністю перешкоди, на скільки сильно ця перешкода заповнює простір (чи є можливість рухатись далі по клітинці, чи необхідно здійснювати обхід перешкод).
При наведеному алгоритмі зникають наведені недолі алгоритму, а швидкість виконання значно зменшується.
Ключові слова: мінімальний шлях, клітинний автомат, правила побудови клітинних автоматів, алгоритми пошуку мінімальної відстані.
Завантаження
