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

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