کامپیوتر 31. روش های دقیق مربوط به مسئله فروشنده دوره گرد نامتقارن (TSP)

روش های دقیق مربوط به مسئله فروشنده دوره گرد نامتقارن (TSP)
چکیدهدر این فصل ما تمرکز خود را بر روی روش محاسبه دقیق در ارتباط با نامتقارن بودن TSP در بررسی های انجام شده، به دنبال تحقیقات افرادی چون بالاس و توس، قرار می دهیم. در بخش 2، دو روش مشخص شاخه و کران، بر مبنای راه حل مرتبط به مسئله انتقال به شکل بازسازی شده، نشان داده و مقایسه شده اند. در بخش 3، روش شاخه و کران بر مبنای محاسبه کران جمع پذیر شرح داده شده است، در حالی که در بخش 4 روش شاخه و کران به بحث گذاشته می شود. در نهایت تمام این روش ها بر مبنای محاسبه بر روی مجموعه بزرگی از نمونه ها تست شده، و با کدهای قابل اجرا شاخه و کران برای TSP نامتقارن مقایسه می گردند. 

الگوریتم ژنتیک و حل مسئله TSP

در این مقاله ابتدا الگوریتمهای ژنتیک را معرفی کرده و مراحل انجام چنین الگوریتمهایی توضیح داده می شود. بعد از اینکه یک دید کلی نسبت به الگوریتمهای ژنتیک پیدا کردیم به مساله TSP میپردازیم. ابتدا چند روشی که برای حل مسئله TSP ارائه شده است را بیان می کنیم و بعد سعی می کنیم الگوریتمهای ژنتیک مختلفی را برای این مساله مطرح کنیم و  پس بررسی می کنیم که کدام یک از این الگوریتمهای ژنتیک بهتر از بقیه روشها جواب می دهند. در پایان نیز مقایسه ای بین  الگوریتمهای ژنتیک و دیگر الگوریتمها انجام می دهیم.