بررسی الگوریتم های ترتیبی و موازی جهت حل مساله چرخه همیلتونی

چکیده مقاله

مسئله چرخه همیلتونی، که در پی یافتن مسیری در یک گراف است که تمام راس ها را دقیقا یکبار ملاقات کرده و به راس شروع بازگردد، از مسائل کلاسیک و مهم در حوزه نظریه گراف و علوم کامپیوتر است این مسئله در دسته مسائل ان پی کامل قرار دارد و حل آن به صورت قطعی و کارآمد در حالت کلی ممکن نیست، اما کاربردهای فراوانی در دنیای واقعی دارد در این مقاله، راه حل های ترتیبی و موازی برای حل این مسئله بررسی و پیاده سازی شده اند الگوریتم بازگشتی با پسگرد به عنوان یک روش ترتیبی و ترکیب روش های تقسیم و حل و بازگشتی با پسگرد به عنوان یک روش موازی، پیاده سازی شده اند نتایج اجرای الگوریتم ها بر روی مجموعه ای از گراف ها نشان می دهد که روش ترتیبی برای گراف های کوچک و متوسط کارآمد است، اما با افزایش تعداد رئوس، زمان اجرا به صورت نمایی افزایش می یابد روش موازی در سیستم های با پردازنده های زیاد برای گراف های کوچک و متوسط کارآمد نیست، اما برای گراف های بزرگ با پردازنده های بیشتر، عملکرد بهتری نسبت به روش ترتیبی دارد به طور کلی، انتخاب بین روش ترتیبی و موازی بستگی به اندازه و ساختار گراف و تعداد پردازنده های سیستم دارد

کلیدواژه‌ها

نویسندگان

الیاس هادی زاده تثبیتی

دانشجوی کارشناسی ارشد مهندسی کامپیوتر، دانشگاه بین المللی امام خمینی ره ، قزوین، ایران

هادی زاده تثبیتی، الیاس،1403،بررسی الگوریتم های ترتیبی و موازی جهت حل مساله چرخه همیلتونی،بیست و چهارمین کنفرانس ملی علوم و مهندسی کامپیوتر و فناوری اطلاعات،بابل

ارائه‌شده در

مجموعه مقالات بیست و چهارمین کنفرانس ملی علوم و مهندسی کامپیوتر و فناوری اطلاعات26 مهر 1403 · بابل