تحلیل و مقایسه‌ی الگوریتم‌های مسیریابی برای یافتن کوتاه‌ترین مسیر برای مسائل قابل تبدیل به گراف

نوع مقاله : مقاله پژوهشی

نویسنده

دانشجوی دکتری، دانشکده مهندسی صنایع، دانشگاه آزاد اسلامی واحد تهران جنوب، تهران، ایران

10.22034/ijwg.2023.405659.1062

چکیده

هدف: جستجو تکنیک حل مسئله در هوش مصنوعی است. مسائل جستجو در گراف غالباً بصورت بازی‌های روی گراف بین چند عامل مدل‌سازی می شود. الگوریتم‌های جستجو بر روی گراف با دو کاربرد عمده پیمایش گراف و یافتن کوتاه‌ترین مسیر در بین دو رأس یک گراف طراحی می‌گردند.
روش: در مقاله حاضر، ابتدا مطالعه جامعی بر روی روش‌های جستجو انجام و سپس، به بررسی و مقایسه الگوریتم‌های مختلف جستجوی مسیر جهت دستیابی به بهینه‌ترین الگوریتم در یافتن کوتاه‌ترین مسیر پرداخته شده است.
یافته‌ها: این الگوریتم‌ها شامل الگوریتم‌های جستجوی دایکستر، A* و IDA* می‌باشد که با استفاده از سه پارامتر زمان اجرا، پیچیدگی زمانی و پیچیدگی فضا با یکدیگر مورد مقایسه قرار گرفته‌ شده‌اند.
نتیجه‌گیری: برای انجام بررسی‌ها از یک حالت (زمین)‌ بازی فرضی در دو شرایط با وجود مانع و بدون وجود مانع استفاده شده و برنامه‌نویسی‌ها با استفاده از زبان برنامه‌نویسی پایتون انجام شده است. نتایج نشان می‌دهد که الگوریتم دایکسترا و الگوریتم A* دارای پیچیدگی زمانی نسبتاً یکسانی هستند و الگوریتم IDA* از نظر زمانی سریعتر از هر دو است؛ همچنین روش IDA* حافظه کمتری نسبت به روشA* اشغال می‌کند.

کلیدواژه‌ها

موضوعات

مراجع

  • Bhadoria, A., & Singh, R. K. (2014). Optimized angular a star algorithm for global path search based on neighbor node evaluation. International Journal of Intelligent Systems and Applications, 6(8), 46.
  • Candra, A., Budiman, M. A., & Pohan, R. I. (2021). Application of A-Star Algorithm on Pathfinding Game. Journal of Physics: Conference Series, 1898(1), 012047. https://doi.org/10.1088/1742-6596/1898/1/012047
  • Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271. https://doi.org/10.1007/BF01386390/METRICS
  • Duchon, F., Babinec, A., Kajan, M., Beno, P., Florek, M., Fico, T., & Jurišica, L. (2014). Path planning with modified A star algorithm for a mobile robot. Procedia Engineering, 96, 59–69. https://doi.org/10.1016/J.PROENG.2014.12.098
  • Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM), 34(3), 596–615. https://doi.org/10.1145/28869.28874
  • Gibert, F., & Nofrarias, M. (2021). Application of A-Star Algorithm on Pathfinding Game Application of A-Star Algorithm on Pathfinding Game. https://doi.org/10.1088/1742-6596/1898/1/012047
  • Goyal, A., Mogha, P., Luthra, R., & Sangwan, N. (2014). Path finding: A* or Dijkstra’s? International Journal in IT & Engineering, 2(1), 1–15.
  • Gross, J. L., & Yellen, J. (2005). Graph theory and its applications. CRC press.
  • Guruji, A. K., Agarwal, H., & Parsediya, D. K. (2016). Time-efficient A* Algorithm for Robot Path Planning. Procedia Technology, 23, 144–149. https://doi.org/10.1016/J.PROTCY.2016.03.010
  • Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. https://doi.org/10.1109/TSSC.1968.300136
  • Hassan, F., Sunar, N., Mohd Basri, M. A., Mahmud, M. S. A., Ishak, M. H. I., & Mohamed Ali, M. S. (Eds.). (2023). Methods and Applications for Modeling and Simulation of Complex Systems. 1912. https://doi.org/10.1007/978-981-99-7243-2
  • Jindal, P., & Kumar, A. (2010). Analysis of shortest path algorithms. Global Journal of Computer Science and Technology, 10(8).
  • Kapi, A. (2020). A Review on Informed Search Algorithms for Video Games Pathfinding. International Journal of Advanced Trends in Computer Science and Engineering, 9, 2756–2764. https://doi.org/10.30534/ijatcse/2020/42932020
  • Keshuai, Z., & Pingqing, F. (2021). Improved A~* algorithm and artificial potential field algorithm for mobile robot path planning [J]. Electronic Devices, 44(02), 368–374.
  • Lanning, D. R., Harrell, G. K., & Wang, J. (2014). Dijkstra’s Algorithm and Google Maps. Proceedings of the 2014 ACM Southeast Regional Conference, ACM SE 2014. https://doi.org/10.1145/2638404.2638494
  • Li, Y., Harms, J., & Holte, R. (2007). No Title. IEEE International Conference on Communications, 123–130. https://doi.org/10.1109/ICC.2007.29
  • Meng, Q., & Zhang, J. (2019). Optimization and application of artificial intelligence routing algorithm. Cluster Computing, 22(4), 8747–8755. https://doi.org/10.1007/s10586-018-1963-z
  • Pemmaraju, S., & Skiena, S. (2003). Computational discrete mathematics: Combinatorics and graph theory with mathematica®. Cambridge university press.
  • Peng, J., Huang, Y., & Luo, G. (2015a). Robot path planning based on improved A* algorithm. Cybernetics and Information Technologies, 15(2), 171–180.
  • Peng, J., Huang, Y., & Luo, G. (2015b). Robot path planning based on improved A* algorithm. Cybernetics and Information Technologies, 15(2), 171–180.
  • Phaneendhar Reddy Vanam. (2011). Shortest path using A∗ Algorithm. http://cs.indstate.edu/~pvanam/phani.pdf
  • Qiong, W., Meiwan, L., Weijian, R., & Tianren, W. (2019). Overview of common algorithms for UAV path planning. Journal of Jilin University (Information Science Edition), 37(01), 58–67.
  • Russell, S. J., & Norvig, P. (2009). Artificial Intelligence A Modern Approach (M. Pompili, Ed.). Alan Apt.
  • Sharma, Cs. K. (2015). Shortest path searching for road network using a* algorithm.
  • Sinthamrongruk, T., Mahakitpaisarn, K., & Manopiniwes, W. (2013). A Performance Comparison between A* Pathfinding and Waypoint Navigator Algorithm on Android and iOS Operating System. International Journal of Engineering and Technology, 5(4), 498.
  • Skiena, S. (1991). Implementing discrete mathematics: combinatorics and graph theory with Mathematica. Addison-Wesley Longman Publishing Co., Inc.
  • Song, Y., & Ma, P. (2021). Research on mobile robot path planning based on improved A-star algorithm. 2021 International Conference on Electronic Information Engineering and Computer Science (EIECS), 683–687.
  • Tang, G., Tang, C., Claramunt, C., Hu, X., & Zhou, P. (2021). Geometric A-Star Algorithm: An Improved A-Star Algorithm for AGV Path Planning in a Port Environment. IEEE Access, 9, 59196–59210. https://doi.org/10.1109/ACCESS.2021.3070054
  • Vamja, H., Shaikh, A., & Rami, S. (2017). Comparative Analysis of Different Path Finding Algorithms to Study Limitations and Progress. The Fourteenth International Conference on Networks, 7(9), 68–75.
  • Wang, H., Qi, X., Lou, S., Jing, J., He, H., & Liu, W. (2021). An Efficient and Robust Improved A* Algorithm for Path Planning. Symmetry 2021, Vol. 13, Page 2213, 13(11), 2213. https://doi.org/10.3390/SYM13112213
  • Wang, H., Yin, P., Zheng, W., Wang, H., & Zuo, J. (2020). Mobile robot path planning based on improved A* algorithm and dynamic window method. Robot, 42(03), 346–353.
  • Wang, Q., Hao, Y., & Chen, F. (2021). Deepening the IDA* algorithm for knowledge graph reasoning through neural network architecture. Neurocomputing, 429, 101–109. https://doi.org/https://doi.org/10.1016/j.neucom.2020.12.040
  • Whiting, P. D., & Hillier, J. A. (1960). A method for finding the shortest route through a road network. Journal of the Operational Research Society, 11, 37–40.
  • Yu, X., Huahua, L., Mingbo, D. U., Tao, M., & Zhiling, W. (2014a). An improved A* algorithm that can search infinite neighborhoods [J]. Robot, 36(05), 627–633.
  • Yu, X., Huahua, L., Mingbo, D. U., Tao, M., & Zhiling, W. (2014b). An improved A* algorithm that can search infinite neighborhoods [J]. Robot, 36(05), 627–633.
  • Zhang, C., Ao, L., Yang, J., & Xie, W. (2020). An Improved A* Algorithm Applying to Path Planning of Games. Journal of Physics: Conference Series, 1631(1), 012068. https://doi.org/10.1088/1742-6596/1631/1/012068
  • Zikky, Moh. (2016). Review of A* (A Star) Navigation Mesh Pathfinding as the Alternative of Artificial Intelligent for Ghosts Agent on the Pacman Game. EMITTER International Journal of Engineering Technology, 4(1), 141–149. https://doi.org/10.24003/EMITTER.V4I1.117

 

فایل ها

هم رسانی

ارجاع به این مقاله

آمار