الگوریتم فروشنده دوره‌گرد (TSP): حل معمای سفر بهینه 🧳🗺️

مسئله فروشنده دوره‌گرد (Traveling Salesman Problem یا TSP) یک مسئله بهینه‌سازی کلاسیک در علوم کامپیوتر و ریاضیات است. هدف آن یافتن کوتاه‌ترین مسیر برای بازدید از n شهر به گونه‌ای است که:

• هر شهر دقیقاً یک بار بازدید شود.

• فروشنده به شهر شروع بازگردد.

این مسئله به ظاهر ساده، یکی از مشهورترین مسائل NP-Hard است که حل دقیق آن برای تعداد شهرهای زیاد، غیرممکن می‌شود.

📌 فرمول‌بندی ریاضی

فرض کنید:

• n شهر با مختصات (xᵢ, yᵢ) داریم.

• d(i,j) فاصله بین شهر i و j است.

• هدف پیدا کردن جایگشت π = (π₁, π₂, ..., πₙ) است که کمینه‌سازی کند:

  Total Distance = d(π₁, π₂) + d(π₂, π₃) + ... + d(πₙ, π₁)

⚙️ روش‌های حل مسئله

۱. روش‌های دقیق (Exact Algorithms)

۲. روش‌های تقریبی (Heuristics)

۳. روش‌های تقریبی با تضمین (Approximation Algorithms)

• الگوریتم کریستوفیدس (Christofides):

  • شرط: فاصله‌ها مثلثی باشند (Metric TSP).

  • ضریب تقریب: 1.5 برابر جواب بهینه.

  • مراحل:

    1. ساخت درخت پوشای کمینه (MST).

    2. پیدا کردن تطابق کمینه روی رأس‌های فردالدرجه.

    3. ساخت دور اویلری و حذف تکرارها.

📊 مثال عددی (۴ شهر)

فرض کنید شهرها به صورت زیر باشند:

محاسبه فاصله‌ها (فاصله اقلیدسی):

d(A,B) = √(1² + 2²) ≈ 2.24  
d(B,C) = √(2² + 1²) ≈ 2.24  
d(C,D) = √(1² + 2²) ≈ 2.24  
d(D,A) = √(4² + 3²) = 5  
d(A,C) = √(3² + 1²) ≈ 3.16  
... (بقیه فواصل)

جواب بهینه: A → B → C → D → A با مجموع ≈ 2.24 + 2.24 + 2.24 + 5 = 11.72

💻 پیاده‌سازی در پایتون (الگوریتم Nearest Neighbor)

import numpy as np

def tsp_nearest_neighbor(dist_matrix):
    n = len(dist_matrix)
    unvisited = set(range(n))
    path = [0]
    unvisited.remove(0)
    
    while unvisited:
        current = path[-1]
        nearest = min(unvisited, key=lambda x: dist_matrix[current][x])
        path.append(nearest)
        unvisited.remove(nearest)
    
    path.append(0)
    total_distance = sum(dist_matrix[path[i]][path[i+1]] for i in range(n))
    return path, total_distance

# مثال: ماتریس فاصله 4x4
dist_matrix = [
    [0, 2.24, 3.16, 5],
    [2.24, 0, 2.24, 3.61],
    [3.16, 2.24, 0, 2.24],
    [5, 3.61, 2.24, 0]
]

path, distance = tsp_nearest_neighbor(dist_matrix)
print(f"مسیر: {path}، مسافت کل: {distance:.2f}")

🌐 کاربردهای واقعی

1. بهینه‌سازی تحویل کالا: شرکت‌هایی مانند Amazon و UPS از TSP برای کاهش مسافت و مصرف سوخت استفاده می‌کنند.

2. طراحی مدارهای الکترونیکی: کمینه‌سازی مسیر مته در بردهای مدار چاپی.

3. زیست‌شناسی مولکولی: تحلیل توالی‌های DNA.

4. نجوم: برنامه‌ریزی حرکت تلسکوپ‌های فضایی.

🔥 چالش‌ها و محدودیت‌ها

• پیچیدگی زمانی: الگوریتم‌های دقیق برای n>20 غیرعملی هستند.

• عدم قطعیت: در نسخه دینامیک TSP، موقعیت شهرها ممکن است تغییر کند.

• ابعاد بالا: در مسائل واقعی با هزاران شهر، نیاز به روش‌های هوشمندانه‌تر است.

🔮 آینده تحقیق در TSP

• کامپیوترهای کوانتومی: الگوریتم‌هایی مانند الگوریتم گروور (Grover) برای سرعت بخشیدن به جستجو.

• یادگیری عمیق: مدل‌های ترانسفورماتور برای پیش‌بینی مسیرهای بهینه.

• بهینه‌سازی چندهدفه: توامندسازی عواملی مانند زمان، هزینه و آلایندگی.

📚 منابع پیشنهادی

1. کتاب: "The Traveling Salesman Problem: A Computational Study" توسط David L. Applegate

2. مقاله: "A 1.5-Approximation Algorithm for the Metric TSP" (Christofides, 1976)

3. دوره آنلاین: Coursera: Discrete Optimization

سوال تفکربرانگیز:
آیا می‌توانید راهکاری برای حل TSP با ۱۰۰۰ شهر در زمان معقول پیشنهاد دهید؟ ایده‌های خود را به اشتراک بگذارید!