تحلیل و مقایسه ی الگوریتم های مسیریابی برای یافتن کوتاه ترین مسیر برای مسائل قابل تبدیل به گراف
محل انتشار: دوفصلنامه بازی جنگ، دوره: 6، شماره: 12
سال انتشار: 1402
نوع سند: مقاله ژورنالی
زبان: فارسی
مشاهده: 49
نسخه کامل این مقاله ارائه نشده است و در دسترس نمی باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_IJWG-6-12_004
تاریخ نمایه سازی: 30 بهمن 1402
چکیده مقاله:
هدف: جستجو تکنیک حل مسئله در هوش مصنوعی است. مسائل جستجو در گراف غالبا بصورت بازی های روی گراف بین چند عامل مدل سازی می شود. الگوریتم های جستجو بر روی گراف با دو کاربرد عمده پیمایش گراف و یافتن کوتاه ترین مسیر در بین دو راس یک گراف طراحی می گردند. روش: در مقاله حاضر، ابتدا مطالعه جامعی بر روی روش های جستجو انجام و سپس، به بررسی و مقایسه الگوریتم های مختلف جستجوی مسیر جهت دستیابی به بهینه ترین الگوریتم در یافتن کوتاه ترین مسیر پرداخته شده است. یافته ها: این الگوریتم ها شامل الگوریتم های جستجوی دایکستر، A* و IDA* می باشد که با استفاده از سه پارامتر زمان اجرا، پیچیدگی زمانی و پیچیدگی فضا با یکدیگر مورد مقایسه قرار گرفته شده اند. نتیجه گیری: برای انجام بررسی ها از یک حالت (زمین) بازی فرضی در دو شرایط با وجود مانع و بدون وجود مانع استفاده شده و برنامه نویسی ها با استفاده از زبان برنامه نویسی پایتون انجام شده است. نتایج نشان می دهد که الگوریتم دایکسترا و الگوریتم A* دارای پیچیدگی زمانی نسبتا یکسانی هستند و الگوریتم IDA* از نظر زمانی سریعتر از هر دو است؛ همچنین روش IDA* حافظه کمتری نسبت به روشA* اشغال می کند.
کلیدواژه ها:
نویسندگان
احمد الهیاری
دانشجوی دکتری، دانشکده مهندسی صنایع، دانشگاه آزاد اسلامی واحد تهران جنوب، تهران، ایران