دانشگاه فرماندهی و ستاد آجا دوفصلنامه بازی جنگ 2676-5284 6 12 2023 08 23 Analyzing and comparing routing algorithms to find the shortest path in graph transformable problems تحلیل و مقایسه‌ی الگوریتم‌های مسیریابی برای یافتن کوتاه‌ترین مسیر برای مسائل قابل تبدیل به گراف 85 114 185139 10.22034/ijwg.2023.405659.1062 FA احمد الهیاری دانشجوی دکتری، دانشکده مهندسی صنایع، دانشگاه آزاد اسلامی واحد تهران جنوب، تهران، ایران 0000-0002-0718-5998 Journal Article 2023 07 06 <strong>Objective</strong>: Search is a problem solving technique in artificial intelligence. Graph search problems are often modeled as graph games between multiple agents. Graph search algorithms are designed with two main applications of graph traversal and finding the shortest path between two vertices of a graph.<br /><strong>Method:</strong> In this article, first a comprehensive study on search methods has been conducted and then, various route search algorithms have been investigated and compared in order to achieve the most optimal algorithm in finding the shortest route.<br /><strong>Findings:</strong> These algorithms include Dijkstra, A*, and IDA* search algorithms, which have been compared with each other using the three parameters of execution time, time complexity, and space complexity.<br /><strong>Conclusion:</strong> To carry out investigations, a hypothetical game state (field) was used in two conditions, with and without obstacles, and programming was done using Python programming language. The results show that the Dijkstra algorithm and the A* algorithm have relatively the same time complexity, and the IDA* algorithm is faster than both; Also, the IDA* method occupies less memory than the A* method. <strong>هدف:</strong> جستجو تکنیک حل مسئله در هوش مصنوعی است. مسائل جستجو در گراف غالباً بصورت بازی‌های روی گراف بین چند عامل مدل‌سازی می شود. الگوریتم‌های جستجو بر روی گراف با دو کاربرد عمده پیمایش گراف و یافتن کوتاه‌ترین مسیر در بین دو رأس یک گراف طراحی می‌گردند.<br /><strong>روش:</strong> در مقاله حاضر، ابتدا مطالعه جامعی بر روی روش‌های جستجو انجام و سپس، به بررسی و مقایسه الگوریتم‌های مختلف جستجوی مسیر جهت دستیابی به بهینه‌ترین الگوریتم در یافتن کوتاه‌ترین مسیر پرداخته شده است.<br /><strong>یافته‌ها:</strong> این الگوریتم‌ها شامل الگوریتم‌های جستجوی دایکستر، A* و<span style="font-size: 13.3333px;"> </span>IDA* می‌باشد که با استفاده از سه پارامتر زمان اجرا، پیچیدگی زمانی و پیچیدگی فضا با یکدیگر مورد مقایسه قرار گرفته‌ شده‌اند.<br /><strong>نتیجه‌گیری:</strong> برای انجام بررسی‌ها از یک حالت (زمین)‌ بازی فرضی در دو شرایط با وجود مانع و بدون وجود مانع استفاده شده و برنامه‌نویسی‌ها با استفاده از زبان برنامه‌نویسی پایتون انجام شده است. نتایج نشان می‌دهد که الگوریتم دایکسترا و الگوریتم A* دارای پیچیدگی زمانی نسبتاً یکسانی هستند و الگوریتم IDA* از نظر زمانی سریعتر از هر دو است؛ همچنین روش IDA* حافظه کمتری نسبت به روشA* اشغال می‌کند. http://www.ijwg.ir/article_185139_1d8a31c2a4d5661768b78c9960de7021.pdf