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

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

Keywords:

چرخه همیلتونی , الگوریتم ترتیبی , الگوریتم موازی , نظریه گراف