Пошук найкоротшого шляху на графі за допомогою клітинних автоматів
Вантажиться...
Дата
2022
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Актуальність теми. Визначення оптимального маршруту між об’єктами може здійснюватися в статичному, динамічному режимах і режимах реального часу. Це питання розглядається в багатьох важливих програмах у сфері GPS, відеоігор, робототехніки, логістики та симуляції натовпу - часові середовища. Проблема пошуку шляху може мати багато різних форм, включаючи ті, що стосуються одного агенту, групи агентів, конкурентного пошуку, динамічних змін навколишнього середовища, неоднорідної місцевості, мобільних пристроїв і неповна інформація. Алгоритм пошуку шляху та створення графіка для його реалізації є двома основними компонентами пошуку рушення проблеми.
Метою роботи є розробка програмного забезпечення, яке може вирішити проблему пошуку найкоротшого шляху на графі за допомогою клітинних автоматів.
Завдання дослідження:
- Проаналізувати існуючі програмні застосунки, що досліджують алгоритми пошуку шляху за допомогою клітинних автоматів
- Встановити набір правил для генерації клітинного автомату, що дозволяє моделювати пошук найкоротшого шляху на графі
- Реалізувати програмний продукт для дослідження використання клітинних автоматів для пошуку шляху на графі на основі встановлених правил
Об’єктом дослідження є динамічні системи.
Предмет дослідження є клітинні автомати.
Методи дослідження. При дослідженнях використовується методики порівняння, абстрагування та аналізу, динамічних систем, прикладної геометрії, комп’ютерної графіки.
Опис
Ключові слова
алгоритм пошуку найкоротшого шляху, мова програмування С++
Бібліографічний опис
Куйбіда, П. К. Пошук найкоротшого шляху на графі за допомогою клітинних автоматів : магістерська дис. : 122 Комп’ютерні науки / Куйбіда Павло Костянтинович. – Київ, 2022. – 99 с.