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

مسئله فروشنده دورهگرد یکی از بنیادیترین و پرمطالعهترین مسائل بهینهسازی ترکیبی است. این مقاله مروری جامعی بر الگوریتمهای تقریبی حل این مسئله ارائه میدهد. پس از بیان تاریخچه، تعریف ریاضی و پیچیدگی محاسباتی، الگوریتمهای کلاسیک شامل نزدیکترین همسایه، حریصانه، روشهای درج و الگوریتم Christofides با نسبت تقریب ۱٫۵ بهطور مفصل بررسی میشوند. سپس روشهای جستجوی محلی، فراابتکاریهایی نظیر شبیهسازی تبرید، الگوریتم ژنتیک، کلونی مورچهها و بهینهسازی ازدحام ذرات، و نیز رویکردهای مبتنی بر یادگیری ماشین، شبکههای عصبی گرافی و محاسبات کوانتومی تحلیل میگردند. نتایج تجربی روی مسائل استاندارد TSPLIB، کاربردهای عملی در لجستیک، طراحی مدار، روباتیک و زیستشناسی محاسباتی، چالشهای باز نظری و عملی، و جهتهای آینده پژوهش نیز مورد بحث قرار میگیرند. یافتهها نشان میدهد الگوریتم Christofides همچنان بهترین تضمین نظری برای نسخه متریک است، در حالی که روشهای هیبریدی، فراابتکاریها و یادگیری عمیق در مقیاس بزرگ عملکرد عملی بالایی دارند.

کلیدواژه ها:

مسئله فروشنده دورهگرد ، الگوریتم تقریبی ، نسبت تقریب ، بهینهسازی ترکیبی ، یادگیری ماشین ، فراابتکاری ، شبکههای عصبی گرافی