بهینه سازی مسیر در TSP (انگلیسی : Traveling Salesman Problem Optimization)، در ریاضیات (Mathematics)
انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :
بهینه سازی مسیر در TSP (انگلیسی : Traveling Salesman Problem Optimization) :
📌 تعریف: مسئله فروشنده دوره گرد (Traveling Salesman Problem - TSP) یک مسئله کلاسیک در بهینه سازی ترکیبیاتی است. در این مسئله، یک فروشنده باید از یک شهر شروع کند، از تمام شهرهای دیگر دقیقا یک بار دیدن کند و به شهر اول بازگردد، به گونه ای که مجموع مسافت طی شده (یا هزینه) کمینه شود. TSP یک مسئله NP-hard است، به این معنی که هیچ الگوریتم کارآمدی برای یافتن جواب دقیق در زمان چندجمله ای برای ابعاد بزرگ وجود ندارد.
🔧 روش های حل TSP
روش های دقیق (Exact Methods):
برنامه ریزی پویا (Dynamic Programming): الگوریتم هلد-کارپ (Held-Karp) با پیچیدگی
\[ O(n^2 2^n) \]که برای nهای کوچک (حدود ۲۰) قابل استفاده است.
شاخه و کران (Branch and Bound): با استفاده از کران پایین (مانند درخت پوشای کمینه) برای هرس کردن فضای جستجو.
برنامه ریزی خطی صحیح (Integer Linear Programming): فرمول بندی با متغیرهای باینری و اضافه کردن قیود حذف زیرتور (Subtour Elimination Constraints).
روش های ابتکاری (Heuristic Methods):
حریصانه (Greedy): الگوریتم نزدیک ترین همسایه (Nearest Neighbor).
الگوریتم های بهبود (Improvement Heuristics): مانند 2-opt، 3-opt که با جابجایی یال ها سعی در بهبود مسیر دارند.
الگوریتم کریستوفیدس (Christofides Algorithm): برای مسئله TSP متریک، یک الگوریتم تقریبی با ضریب ۱.۵.
فراابتکاری ها (Metaheuristics):
الگوریتم ژنتیک (GA)، بهینه سازی کلونی مورچگان (ACO)، شبیه سازی تبرید (SA)، جستجوی ممنوعه (TS)، و... این روش ها می توانند جواب های بسیار خوبی برای TSPهای بزرگ (هزاران شهر) پیدا کنند.
