ВІЗУАЛІЗАЦІЯ АЛГОРИТМУ ПОШУКУ ОПТИМАЛЬНОГО ШЛЯХУ МІЖ ДВОМА ТОЧКАМИ КЛІТИННОГО ЛАБІРИНТУ З ПЕРЕШКОДАМИ, ЩО ДИНАМІЧНО ЗМІНЮЮТЬСЯ
DOI:
https://doi.org/10.31548/itees.2026.01.035Ключові слова:
пошук у глибину, пошук у ширину, теорія графів, пошук оптимального шляху, динамічне середовище, алгоритм Дейкстри, алгоритм A*, алгоритм D Lite*, візуалізація алгоритмів, клітинний лабіринт, інформаційно-аналітична підтримкаАнотація
У даній роботі досліджується актуальна проблема пошуку оптимального шляху в динамічних середовищах, що моделюються як клітинні лабіринти з перешкодами. Проблема пошуку оптимального шляху між двома точками клітинного лабіринту є актуальною через її універсальність, прикладну цінність і фундаментальне значення для розвитку сучасних технологій. Основна увага приділяється розробці та програмній реалізації системи візуалізації алгоритмів на графах, яка дозволяє в реальному часі спостерігати за процесом прийняття рішень автономним агентом. У роботі проведено детальний порівняльний аналіз класичних методів, таких як алгоритм Дейкстри та A*, а також спеціалізованих інкрементальних підходів, зокрема D* Lite. Обґрунтовано переваги використання теорії графів для вирішення задач природокористування, логістики та робототехніки, де середовище може змінюватися непередбачувано. Метою представленої роботи є розробка програми для візуалізації алгоритму пошуку оптимального шляху на полі, яке можна уявити у вигляді лабіринту з переборними і непереборними перешкодами. Задача полягає в тому, щоб знайти оптимальний шлях між двома точками на полі та відобразити його. Практична частина дослідження включає розробку програмного забезпечення на мові C#, яке демонструє процес перебудови маршруту при виникненні нових перешкод без необхідності повного перерахунку всієї мережі. Це критично важливо для мінімізації обчислювальних витрат у складних інформаційно-аналітичних системах. Окремий акцент зроблено на освітньому аспекті: розроблена візуалізація інтегрована у навчальний процес для викладання дисциплін «Алгоритми і структури даних» та «Об’єктно-орієнтоване програмування», що значно покращує засвоєння складних математичних концепцій студентами. Результати роботи підтверджують, що поєднання теоретичних методів пошуку шляху з інтерактивною візуалізацією забезпечує високу надійність і прозорість функціонування сучасних навігаційних та екологічних систем моніторингу. Програма візуалізації алгоритму пошуку оптимального шляху в лабіринті має величезне практичне значення і може застосовуватися у робототехніці та автономних системах для навігації роботів у реальному середовищі, у мережах і телекомунікаціях здійснює пошук оптимального маршруту передачі даних. Візуалізація алгоритму пошуку оптимального шляху в клітинному лабіринті з динамічними перешкодами дозволяє глибше зрозуміти принципи роботи алгоритмів, оцінити їх ефективність у реальному часі, експериментувати з різними стратегіями перебудови маршруту.
Отримано 2026-02-23
Прийнято 2026-04-01
Посилання
1. Minor, E.S., Urban, D.L. (2008), A Graph-Theory Framework for Evaluating Landscape Connectivity and Conservation Planning. Conservation Biology, 22: 297-307. https://doi.org/10.1111/j.1523-1739.2007.00871.x.
2. Shanu, S., Wattasseril, J. I., Qureshi, Q., & Jhala, Y. V., Bhattacharya S. (2016). A graph theoretic approach for modelling wildlife corridors. arXiv. https://doi.org/10.48550/arXiv.1603.01939
3. Choi, S., Ullah, Z., & Son, M. (2026). A graph-based machine learning framework for river water quality management under data limitations. Journal of Environmental Management, 398, 128575. https://doi.org/10.1016/j.jenvman.2026.128575.
4. Aho, K., Kriloff, C., Godsey, S. E., Ramos, R., Wheeler, C., You, Y., Warix, S., Derryberry, D., Zipper, S., Hale, R. L., Bond, C. T., & Kuehn, K. A. (2023). Non-perennial stream networks as directed acyclic graphs: The R-package streamDAG. Environmental Modelling & Software, 167, 105775. https://doi.org/10.1016/j.envsoft.2023.105775.
5. Dunne, J. A., & Williams, R. J., Martinez N. D. (2002). Food-web structure and network theory: The role of connectance and size, 99 (20) 12917-12922. https://doi.org/10.1073/pnas.19240769
6. Longjas, A. ; Tejedor, A. ; Foufoula-Georgiou, E. (2017). Graph Theory Approach for Studying Food Webs. American Geophysical Union, Fall Meeting 2017, abstract #IN33B-0119. https://ui.adsabs.harvard.edu/abs/2017AGUFMIN33B0119L/abstract.
7. Evans D.M., Pocock M.J. O., Memmott J. (2013). The robustness of a network of ecological networks to habitat loss. Ecology Letters, 16(7). https://doi.org/10.1111/ele.12117.
8. Ormsbee, L. E., & Lansey, K. E. (2024). Graph theory applications in water distribution system design and optimization. Journal of Water Resources Planning and Management, 150(4), 04023012. https://doi.org/10.1061/JWRMD5.WRENG-6001.
9. Zheng, Y. (2025) Historical Evolution and Future Optimization of A*-Based Path Planning in Static and Dynamic Environments. Highlights in Science, Engineering and Technology. https://hsetdata.com/index.php/ojs/article/view/838.
10. Liao, T., Chen, F., Wu, Y., Zeng, H., Ouyang, S., Guan, J. (2024) Research on Path Planning with the Integration of Adaptive A-Star Algorithm and Improved Dynamic Window Approach Electronics 13(2), 455; https://doi.org/10.3390/electronics13020455.
11. Sinkevych, O., Boyko, Y., Sokolovskyy, B., Rechynskyi, O. (2024) Study of Pathfinding Approach Based on A* With Adaptive Occupancy Grid. ACPS. 9(2)б, 95–100, https://doi.org/10.23939/acps2024.02.095.
12. Stawarz, P., Ozog, D., Łabuński, W. (2024) Supported Influence Mapping for Mobile Robot Pathfinding in Dynamic Indoor Environments Sensors. 24(22),. 7240, https://www.mdpi.com/1424-8220/24/22/7240.
13. Gao, Y., Han, Q., Feng, S., Wang, Z., Meng, T., Yang, J. (2024) Improvement and Fusion of D*Lite Algorithm and Dynamic Window Approach for Path Planning in Complex Environments Machines, 12(8), 525; https://doi.org/10.3390/machines12080525.
14. Chen, L., & Wang, Y. (2025). Time and memory trade-offs in shortest-path algorithms for dynamic road networks. Journal of Applied Mathematics and Computing, 71(3), 442–459. https://doi.org/10.1007/s12190-025-01842-x.
15. Aldhafferi N. (2025) Time and Memory Trade-Offs in Shortest-Path Algorithms Across Graph Topologies: A*, Bellman–Ford, Dijkstra, AI-Augmented A* and a Neural Baseline. Computers, 14(12), 545; https://doi.org/10.3390/computers14120545.
16. Patel, A. (n.d.). Introduction to the A* algorithm. Red Blob Games. Retrieved May 22, 2024, https://www.redblobgames.com/pathfinding/a-star/introduction.html.
17. Ji, Y., Zuo, T., & Hu, L. (2023). Pareto optimal path generation algorithm in stochastic transportation networks with reliability constraints. Transportation Research Part C: Emerging Technologies, 148, Article 104039. https://doi.org/10.1016/j.trc.2023.104039.
18. Vanin, V., Zalevska, O., Jablonskiy, P. (2020). The application of graph theory for improving and rendering algorithm for finding the shortest path in the mathematical models of video games [Zastosuvannia teorii hrafiv dlia udoskonalennia ta vizualizatsii alhorytmu poshuku naikorotshoho shliakhu v matematychnii modeli videoihry]. Applied Geometry and Engineering Graphics. 97, 23–28, https://doi.org/10.32347/0131-579x.2020.97.23-28.
Завантаження
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2026 Інформаційні технології в економіці та природокористуванні
Усі матеріали розповсюджуються згідно з умовами міжнародної публічної ліцензії Creative Commons Attribution 4.0 International Public License, що дозволяє іншим поширювати статтю з визнанням авторства та першої публікації в цьому журналі.
