10.10: Gezgin Satıcı Problemi (TSP)

⚠️ Neden Bu Kadar Zor?

📊 Olası Tur Sayısı: (n-1)! / 2

n = 5 şehir:	12 tur	✓ Saniyeler
n = 10 şehir:	181,440 tur	✓ Milisaniyeler
n = 15 şehir:	43,589,145,600 tur	△ Dakikalar
n = 20 şehir:	60,822,550,204,416,000 tur	✗ Yıllar!

🔴 NP-Hard Problem

TSP hem NP-Hard hem de NP-Complete'dir (karar versiyonu). Bu demek ki:

Polinom zamanlı kesin çözüm algoritması bilinmiyor
Büyük n için exact çözüm pratik değil
Heuristics ve approximation algoritmaları kullanılır

🔧 Çözüm Yaklaşımları

1️⃣ Brute Force

O(n!)

Tüm permütasyonları dene, en kısasını bul.

✅ Optimal sonuç garantili
❌ n > 10 için pratik değil

2️⃣ Dynamic Programming

O(n² × 2ⁿ)

Held-Karp algoritması. Alt problemleri önbelleğe al.

✅ Optimal sonuç garantili
✅ n ~ 20 için pratik
❌ Exponential space

3️⃣ Greedy

O(n² log n)

En yakın komşu heuristic. Her adımda en yakın şehre git.

✅ Hızlı
❌ Optimal değil
△ Optimale yakın olabilir

4️⃣ 2-Opt Improvement

O(n² × iterasyon)

Mevcut turu iyileştir. Kenarları çaprazla.

✅ Genelde iyi sonuç
✅ Büyük n için pratik
❌ Local optimum'a takılabilir

1️⃣ Brute Force Çözüm

Algoritma

Şehir 0'dan başla (simetri nedeniyle sabit)
Diğer (n-1) şehrin tüm permütasyonlarını oluştur
Her permütasyon için toplam mesafeyi hesapla
En kısa olanı döndür

TSP - Brute Force

from itertools import permutations
import math

def tsp_brute_force(dist):
    """
    TSP Brute Force - Tüm permütasyonları dene
    
    Karmaşıklık: O(n!)
    Küçük graflar için (n ≤ 10)
    
    Args:
        dist: n×n mesafe matrisi
        
    Returns:
        (minimum_mesafe, optimal_tur)
    """
    n = len(dist)
    
    # Şehir 0'dan başla, diğerlerinin permütasyonlarını dene
    cities = list(range(1, n))
    
    min_distance = float('inf')
    best_tour = None
    permutation_count = 0
    
    for perm in permutations(cities):
        permutation_count += 1
        
        # Tur: 0 → perm[0] → perm[1] → ... → 0
        tour = [0] + list(perm) + [0]
        
        # Toplam mesafe
        total = 0
        for i in range(len(tour) - 1):
            total += dist[tour[i]][tour[i+1]]
        
        if total < min_distance:
            min_distance = total
            best_tour = tour
    
    return min_distance, best_tour, permutation_count


# ===== DEMO =====
print("=" * 50)
print("TSP - BRUTE FORCE")
print("=" * 50)

# Örnek: 5 şehir
# Mesafe matrisi (simetrik)
dist = [
    [0, 10, 15, 20, 25],
    [10, 0, 35, 25, 30],
    [15, 35, 0, 30, 20],
    [20, 25, 30, 0, 15],
    [25, 30, 20, 15, 0]
]

print("\n🗺️ Mesafe Matrisi:")
for i, row in enumerate(dist):
    print(f"  Şehir {i}: {row}")

min_dist, best_tour, count = tsp_brute_force(dist)

print(f"\n📊 Kontrol edilen permütasyon: {count}")
print(f"✅ Optimal Tur: {' → '.join(map(str, best_tour))}")
print(f"📏 Minimum Mesafe: {min_dist}")

# 6 şehir örneği
print("\n" + "-" * 50)
print("\n🗺️ 6 Şehir Örneği:")

dist6 = [
    [0, 12, 29, 22, 13, 24],
    [12, 0, 19, 3, 25, 6],
    [29, 19, 0, 21, 23, 28],
    [22, 3, 21, 0, 4, 5],
    [13, 25, 23, 4, 0, 16],
    [24, 6, 28, 5, 16, 0]
]

min_dist6, best_tour6, count6 = tsp_brute_force(dist6)

print(f"📊 Kontrol edilen permütasyon: {count6}")
print(f"✅ Optimal Tur: {' → '.join(map(str, best_tour6))}")
print(f"📏 Minimum Mesafe: {min_dist6}")

Çıktı bekleniyor...

2️⃣ Dynamic Programming (Held-Karp)

Fikir: Bit Masking ile Alt Problem Tanımı

dp[mask][i] = "mask" kümesindeki şehirler ziyaret edildi ve son şehir "i" ise minimum mesafe

mask: Hangi şehirlerin ziyaret edildiğini gösteren bitmask
Örnek: mask = 0b1011 → şehir 0, 1, 3 ziyaret edildi

TSP - Held-Karp (DP)

def tsp_held_karp(dist):
    """
    TSP Dynamic Programming - Held-Karp Algoritması
    
    Karmaşıklık: O(n² × 2ⁿ) zaman, O(n × 2ⁿ) alan
    n ≤ 20 için pratik
    
    Args:
        dist: n×n mesafe matrisi
        
    Returns:
        (minimum_mesafe, optimal_tur)
    """
    n = len(dist)
    
    # dp[mask][i] = mask kümesi ziyaret edildi, son şehir i ise min mesafe
    # Başlangıç: sadece şehir 0 ziyaret edildi
    INF = float('inf')
    
    dp = [[INF] * n for _ in range(1 << n)]
    parent = [[-1] * n for _ in range(1 << n)]
    
    # Base case: şehir 0'dan başla
    dp[1][0] = 0  # mask=0b1, şehir 0 ziyaret edildi
    
    # Tüm mask'ları küçükten büyüğe işle
    for mask in range(1 << n):
        for last in range(n):
            # mask'ta last şehri var mı?
            if not (mask & (1 << last)):
                continue
            # Bu duruma ulaşmak mümkün mü?
            if dp[mask][last] == INF:
                continue
            
            # last'tan diğer şehirlere git
            for next_city in range(n):
                # next_city zaten ziyaret edilmiş mi?
                if mask & (1 << next_city):
                    continue
                
                new_mask = mask | (1 << next_city)
                new_dist = dp[mask][last] + dist[last][next_city]
                
                if new_dist < dp[new_mask][next_city]:
                    dp[new_mask][next_city] = new_dist
                    parent[new_mask][next_city] = last
    
    # Tüm şehirler ziyaret edildi, şehir 0'a dön
    full_mask = (1 << n) - 1
    min_dist = INF
    last_city = -1
    
    for i in range(n):
        total = dp[full_mask][i] + dist[i][0]
        if total < min_dist:
            min_dist = total
            last_city = i
    
    # Yolu geri izle (backtrack)
    tour = [0]
    mask = full_mask
    current = last_city
    
    while current != 0:
        tour.append(current)
        prev = parent[mask][current]
        mask = mask ^ (1 << current)  # current'ı kaldır
        current = prev
    
    tour.append(0)
    tour.reverse()
    
    return min_dist, tour


# ===== DEMO =====
print("=" * 50)
print("TSP - HELD-KARP (Dynamic Programming)")
print("=" * 50)

# Aynı örnek
dist = [
    [0, 10, 15, 20, 25],
    [10, 0, 35, 25, 30],
    [15, 35, 0, 30, 20],
    [20, 25, 30, 0, 15],
    [25, 30, 20, 15, 0]
]

print("\n🗺️ 5 Şehir Örneği:")
min_dist, tour = tsp_held_karp(dist)

print(f"✅ Optimal Tur: {' → '.join(map(str, tour))}")
print(f"📏 Minimum Mesafe: {min_dist}")

# Daha büyük örnek
print("\n" + "-" * 50)
print("\n🗺️ 8 Şehir Örneği:")

import random
random.seed(42)
n = 8
dist8 = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(i+1, n):
        d = random.randint(10, 50)
        dist8[i][j] = d
        dist8[j][i] = d

min_dist8, tour8 = tsp_held_karp(dist8)

print(f"✅ Optimal Tur: {' → '.join(map(str, tour8))}")
print(f"📏 Minimum Mesafe: {min_dist8}")
print(f"\n📊 DP tablo boyutu: {n} × {2**n} = {n * (2**n):,} hücre")

Çıktı bekleniyor...

3️⃣ Greedy: En Yakın Komşu

Algoritma (Nearest Neighbor)

Rastgele bir şehirden başla
Henüz ziyaret edilmemiş en yakın şehre git
Tüm şehirler ziyaret edilene kadar tekrarla
Başlangıç şehrine dön

Not: Optimal değil ama hızlı! Genelde optimalin %20-25 üstünde.

TSP - Greedy (En Yakın Komşu)

def tsp_nearest_neighbor(dist, start=0):
    """
    TSP Greedy - En Yakın Komşu Heuristic
    
    Karmaşıklık: O(n²)
    Her boyut için pratik, ama optimal değil!
    
    Args:
        dist: n×n mesafe matrisi
        start: başlangıç şehri
        
    Returns:
        (mesafe, tur)
    """
    n = len(dist)
    visited = [False] * n
    tour = [start]
    visited[start] = True
    total_dist = 0
    current = start
    
    for _ in range(n - 1):
        # En yakın ziyaret edilmemiş şehri bul
        nearest = -1
        nearest_dist = float('inf')
        
        for next_city in range(n):
            if not visited[next_city] and dist[current][next_city] < nearest_dist:
                nearest = next_city
                nearest_dist = dist[current][next_city]
        
        # En yakın şehre git
        visited[nearest] = True
        tour.append(nearest)
        total_dist += nearest_dist
        current = nearest
    
    # Başlangıca dön
    tour.append(start)
    total_dist += dist[current][start]
    
    return total_dist, tour


# ===== DEMO =====
print("=" * 50)
print("TSP - GREEDY (En Yakın Komşu)")
print("=" * 50)

dist = [
    [0, 10, 15, 20, 25],
    [10, 0, 35, 25, 30],
    [15, 35, 0, 30, 20],
    [20, 25, 30, 0, 15],
    [25, 30, 20, 15, 0]
]

print("\n🗺️ 5 Şehir Örneği:")

# Her başlangıç noktasını dene
for start in range(len(dist)):
    greedy_dist, greedy_tour = tsp_nearest_neighbor(dist, start)
    print(f"  Şehir {start}'dan: {' → '.join(map(str, greedy_tour))} = {greedy_dist}")

# En iyi greedy sonucu
best_greedy = min(tsp_nearest_neighbor(dist, s) for s in range(len(dist)))
print(f"\n✅ En iyi Greedy: {best_greedy[0]}")
print(f"📊 Optimal: 80 (Brute Force ile)")
print(f"📈 Fark: %{((best_greedy[0] - 80) / 80 * 100):.1f}")

# Daha büyük örnek
print("\n" + "-" * 50)
print("\n🗺️ 15 Şehir Örneği (Brute Force için çok büyük!):")

import random
random.seed(42)
n = 15
dist15 = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(i+1, n):
        d = random.randint(10, 100)
        dist15[i][j] = d
        dist15[j][i] = d

best_greedy15 = min(tsp_nearest_neighbor(dist15, s) for s in range(n))
print(f"✅ Greedy Sonuç: {best_greedy15[0]}")
print(f"🛤️ Tur: {' → '.join(map(str, best_greedy15[1]))}")

Çıktı bekleniyor...

4️⃣ 2-Opt İyileştirme

Fikir: Çaprazlayan Kenarları Düzelt

Mevcut turda iki kenar seç, sil ve farklı şekilde bağla. Eğer daha kısa olursa kabul et.

Önce:  A → B ... C → D
Sonra: A → C ... B → D  (B-C arası tersine çevrilir)

TSP - 2-Opt İyileştirme

def calculate_tour_distance(tour, dist):
    """Tur toplam mesafesini hesapla"""
    total = 0
    for i in range(len(tour) - 1):
        total += dist[tour[i]][tour[i+1]]
    return total


def tsp_2opt(dist, initial_tour=None):
    """
    TSP 2-Opt Local Search
    
    Mevcut turu iteratif olarak iyileştir
    
    Args:
        dist: n×n mesafe matrisi
        initial_tour: başlangıç turu (None ise greedy kullan)
        
    Returns:
        (mesafe, tur, iyileştirme_sayısı)
    """
    n = len(dist)
    
    # Başlangıç turu
    if initial_tour is None:
        # Greedy ile başla
        _, initial_tour = tsp_nearest_neighbor(dist)
    
    tour = initial_tour.copy()
    best_distance = calculate_tour_distance(tour, dist)
    improvements = 0
    
    improved = True
    while improved:
        improved = False
        
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                # Kenarları değiştirmenin kazancını hesapla
                # Eski kenarlar: tour[i-1]→tour[i] ve tour[j]→tour[j+1]
                # Yeni kenarlar: tour[i-1]→tour[j] ve tour[i]→tour[j+1]
                
                old_dist = (dist[tour[i-1]][tour[i]] + 
                           dist[tour[j]][tour[(j+1) % n]])
                new_dist = (dist[tour[i-1]][tour[j]] + 
                           dist[tour[i]][tour[(j+1) % n]])
                
                if new_dist < old_dist:
                    # İyileştirme bulduk! i ile j arasını tersine çevir
                    tour[i:j+1] = reversed(tour[i:j+1])
                    best_distance -= (old_dist - new_dist)
                    improved = True
                    improvements += 1
    
    return best_distance, tour, improvements


def tsp_nearest_neighbor(dist, start=0):
    """En yakın komşu heuristic"""
    n = len(dist)
    visited = [False] * n
    tour = [start]
    visited[start] = True
    current = start
    
    for _ in range(n - 1):
        nearest = min(
            (c for c in range(n) if not visited[c]),
            key=lambda c: dist[current][c]
        )
        visited[nearest] = True
        tour.append(nearest)
        current = nearest
    
    tour.append(start)
    return sum(dist[tour[i]][tour[i+1]] for i in range(n)), tour


# ===== DEMO =====
print("=" * 50)
print("TSP - 2-OPT İYİLEŞTİRME")
print("=" * 50)

dist = [
    [0, 10, 15, 20, 25],
    [10, 0, 35, 25, 30],
    [15, 35, 0, 30, 20],
    [20, 25, 30, 0, 15],
    [25, 30, 20, 15, 0]
]

print("\n🗺️ 5 Şehir Örneği:")

# Greedy sonucu
greedy_dist, greedy_tour = tsp_nearest_neighbor(dist)
print(f"Greedy: {' → '.join(map(str, greedy_tour))} = {greedy_dist}")

# 2-Opt iyileştirme
opt_dist, opt_tour, improvements = tsp_2opt(dist, greedy_tour)
print(f"2-Opt:  {' → '.join(map(str, opt_tour))} = {opt_dist}")
print(f"📈 İyileştirme sayısı: {improvements}")

# Daha büyük örnek
print("\n" + "-" * 50)
print("\n🗺️ 20 Şehir Örneği:")

import random
random.seed(42)
n = 20
dist20 = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(i+1, n):
        d = random.randint(10, 100)
        dist20[i][j] = d
        dist20[j][i] = d

greedy_dist20, greedy_tour20 = tsp_nearest_neighbor(dist20)
opt_dist20, opt_tour20, improvements20 = tsp_2opt(dist20, greedy_tour20)

print(f"Greedy Mesafe: {greedy_dist20}")
print(f"2-Opt Mesafe:  {opt_dist20}")
print(f"📈 İyileştirme: %{((greedy_dist20 - opt_dist20) / greedy_dist20 * 100):.1f}")
print(f"🔄 İyileştirme adımı: {improvements20}")

Çıktı bekleniyor...

🎮 İnteraktif TSP Görselleştirme

Canvas'a tıklayarak şehir ekleyin, sonra her iki algoritmayı da çalıştırarak karşılaştırın:

🟢 Greedy (Nearest Neighbor)

🔵 Greedy + 2-Opt

📊 Yöntem Karşılaştırması

Yöntem	Zaman	Alan	Optimal?	Pratik n
Brute Force	O(n!)	O(n)	✓ Evet	≤ 10
Held-Karp (DP)	O(n² × 2ⁿ)	O(n × 2ⁿ)	✓ Evet	≤ 20
Nearest Neighbor	O(n²)	O(n)	✗ Hayır	Herhangi
2-Opt	O(n² × iter)	O(n)	△ Lokal	Herhangi
Simulated Annealing	Değişken	O(n)	△ Yaklaşık	Herhangi
Genetic Algorithm	Değişken	O(pop × n)	△ Yaklaşık	Herhangi

🌍 Gerçek Hayat Uygulamaları

📦 Lojistik & Dağıtım

Amazon, UPS, FedEx: Günlük binlerce teslimatı optimize etmek. TSP'nin genellemesi: VRP (Vehicle Routing Problem).

🔧 PCB Üretimi

Devre kartı delme makinesi: Binlerce deliği en kısa sürede delmek için drill head'in rotası.

🔬 DNA Sıralama

Genom assembly: DNA parçalarını (contigs) en uygun sırada birleştirmek.

✈️ Uçak Rotaları

Havayolları: Crew scheduling, fuel optimization, minimum connection time.

🤖 Robot Hareketi

Fabrika robotları: Pick-and-place işlemlerinde en kısa hareket rotası.

🔭 Teleskop Konumlandırma

Uzay teleskobu: Gözlemlenecek yıldızları en verimli sırayla ziyaret etmek.

🧳 10.10: Gezgin Satıcı Problemi

📌 Problem Tanımı

⚠️ Neden Bu Kadar Zor?

📊 Olası Tur Sayısı: (n-1)! / 2

🔴 NP-Hard Problem

🔧 Çözüm Yaklaşımları

1️⃣ Brute Force

2️⃣ Dynamic Programming

3️⃣ Greedy

4️⃣ 2-Opt Improvement

1️⃣ Brute Force Çözüm

Algoritma

2️⃣ Dynamic Programming (Held-Karp)

Fikir: Bit Masking ile Alt Problem Tanımı

3️⃣ Greedy: En Yakın Komşu

Algoritma (Nearest Neighbor)

4️⃣ 2-Opt İyileştirme

Fikir: Çaprazlayan Kenarları Düzelt

🎮 İnteraktif TSP Görselleştirme

🟢 Greedy (Nearest Neighbor)

🔵 Greedy + 2-Opt

📊 Yöntem Karşılaştırması

🌍 Gerçek Hayat Uygulamaları

📦 Lojistik & Dağıtım

🔧 PCB Üretimi

🔬 DNA Sıralama

✈️ Uçak Rotaları

🤖 Robot Hareketi

🔭 Teleskop Konumlandırma