Kombinatoryal Optimizasyon

Zor

Aho

Sedgewick

Gezgin Satıcı Problemini (TSP) çözmek için kesin çözümler sunan kaba kuvvet aramasından, hızlı ve etkili 2-Opt yerel iyileştirme ve yaklaşıklık algoritmalarına kadar geniş bir spektrumu inceler.

Gezgin Satıcı ve Yerel Arama (Traveling Salesman & Local Search) Algoritması

Gezgin Satıcı ve Yerel Arama (Traveling Salesman & Local Search) Açıklaması

Gezgin Satıcı Problemi (TSP), verilen n adet şehirden her birine tam olarak birer kez uğrayıp başlangıç noktasına dönen en kısa yolu bulma problemidir. NP-Zor yapısıyla bilinir.

Kapsamlı Arama (Exhaustive Search), tüm olası (n-1)! / 2 turları inceleyerek kesin çözümü bulur, ancak n > 12 için pratik değildir. Bu sebeple pratikte sezgisel (heuristics) ve yaklaşıklık (approximation) algoritmaları tercih edilir.

Yerel Arama (Local Search) yöntemlerinden en popüleri olan 2-Opt algoritması, mevcut bir turun kesişen veya verimsiz iki kenarını çıkarıp yolları ters çevirerek birleştirir. Bu işlem lokal iyileştirme yapılamayana kadar sürdürülür. En Yakın Komşu (Nearest Neighbor) ise başlangıç noktasına en yakın şehri seçerek ilerleyen açgözlü bir yaklaşıklık algoritmasıdır.

Kaynak Notları

2-Opt algoritması yerel minimumlara takılabilir. Bunu aşmak için çoklu başlangıçlı yerel arama (multi-start local search) uygulanır.
Öklid uzayında Nearest Neighbor sezgisel yöntemi genellikle en iyi tur uzunluğunun 1.25 katı civarında sonuçlar verir.

Çalışma Prensibi

En Yakın Komşu Heuristiği:
Boş bir ziyaret listesi oluştur ve başlangıç şehrini ekle.
Şu anki şehre en yakın ve henüz ziyaret edilmemiş olan şehri bul.
O şehre git ve ziyaret edildi olarak işaretle.
Tüm şehirler bittiğinde başlangıç şehrine geri dönerek turu tamamla.
2-Opt İyileştirmesi:
Mevcut bir tur al (örneğin En Yakın Komşu ile üretilmiş).
Her i ve j kenar çifti için (i+1 < j):
İki kenarı çıkar, aradaki yolu ters çevirerek bağla ve yeni tur uzunluğunu hesapla.
Eğer yeni uzunluk eskisinden kısaysa, değişikliği kalıcı yap ve aramayı baştan başlat.
Daha fazla iyileştirme yapılamayana (2-opt local minimum) kadar döngüyü sürdür.

Kod Örnekleri

Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.

Gezgin Satıcı ve Yerel Arama (Traveling Salesman & Local Search) Algoritması - TypeScript

1function getDistance(x1: number, y1: number, x2: number, y2: number): number {
2  return Math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2);
3}
4
5export function calculateTotalDistance(tour: number[], pts: [number, number][]): number {
6  let dist = 0;
7  for (let i = 0; i < tour.length; i++) {
8    const p1 = pts[tour[i]];
9    const p2 = pts[tour[(i + 1) % tour.length]];
10    dist += getDistance(p1[0], p1[1], p2[0], p2[1]);
11  }
12  return dist;
13}
14
15export function twoOpt(pts: [number, number][]): number[] {
16  const n = pts.length;
17  // Initialize with a simple 0..n-1 tour
18  let tour = Array.from({ length: n }, (_, i) => i);
19  let improved = true;
20  
21  while (improved) {
22    improved = false;
23    for (let i = 1; i < n - 1; i++) {
24      for (let j = i + 1; j < n; j++) {
25        // 2-opt swap: reverse segment from i to j
26        const newTour = [...tour.slice(0, i), ...tour.slice(i, j + 1).reverse(), ...tour.slice(j + 1)];
27        if (calculateTotalDistance(newTour, pts) < calculateTotalDistance(tour, pts)) {
28          tour = newTour;
29          improved = true;
30          break;
31        }
32      }
33      if (improved) break;
34    }
35  }
36  return tour;
37}

Kendi Verilerinizle Test Edin

Şehir koordinatlarını girerek 2-Opt yerel iyileştirmesi ve Kapsamlı Aramayı karşılaştırın.

TSP ve Yerel Arama Görselleştirici

Şehir koordinatlarını girerek 2-Opt yerel iyileştirmesi ve Kapsamlı Aramayı karşılaştırın.

Girdi

Sonuç

Henüz çalıştırılmadı

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

En İyi Durum: O(n^2) - Basit sezgisel

Ortalama Durum: O(k * n^2) - 2-Opt iyileştirmesi

En Kötü Durum: O(n!) - Kapsamlı Arama

Alan Karmaşıklığı

O(n) - Tur dizisi saklama - Bu algoritmanın karmaşıklığı belirtilmemiş.

Heuristik ve Kesin Çözüm Kıyaslaması

Kapsamlı Arama n=10 için yaklaşık 180,000 tur incelerken, n=15 için bu sayı 43 milyara çıkar ve hesaplanamaz hale gelir.
2-Opt algoritması, n=100 gibi büyük boyutlarda bile milisaniyeler içinde optimuma çok yakın (%2-5 fark) çözümler üretebilir.
Yerel aramanın kalitesi, başlangıç turuna çok bağımlıdır; bu nedenle önce Nearest Neighbor ile makul bir tur üretip ardından 2-Opt uygulamak yaygındır.

Avantajlar ve Dezavantajlar

Avantajlar

2-Opt, uygulaması kolay ve son derece hızlı çalışan bir lokal optimize edicidir.
Çok büyük şehir setlerinde kabul edilebilir sürelerde oldukça kısa turlar sunar.
NP-Zor bir problemi saniyeler bazında çözmek için idealdir.

Dezavantajlar

Sezgisel yöntemlerin hiçbirisi global optimal çözümü garanti etmez.
Lokal minimum tuzaklarına takılıp kalabilir.
Büyük şehir adetlerinde 2-Opt araması da $O(n^2)$ yapısı gereği yavaşlayabilir.

İlgili Algoritmalar

Gezgin Satıcı ve Yerel Arama (Traveling Salesman & Local Search) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar:

Genetik Algoritmalar

TSP gibi zor optimizasyonlarda çaprazlama ve mutasyon kullanarak arama yapan evrimsel yöntem.

Simulated Annealing

Lokal minimum tuzaklarından kaçmak için kötü hamleleri olasılıksal olarak kabul eden meta-sezgisel.

Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...

Gezgin Satıcı ve Yerel Arama (Traveling Salesman & Local Search) Algoritması

Gezgin Satıcı ve Yerel Arama (Traveling Salesman & Local Search) Açıklaması

Gezgin Satıcı Problemi (TSP), verilen n adet şehirden her birine tam olarak birer kez uğrayıp başlangıç noktasına dönen en kısa yolu bulma problemidir. NP-Zor yapısıyla bilinir.

Kaynak Notları

2-Opt algoritması yerel minimumlara takılabilir. Bunu aşmak için çoklu başlangıçlı yerel arama (multi-start local search) uygulanır.
Öklid uzayında Nearest Neighbor sezgisel yöntemi genellikle en iyi tur uzunluğunun 1.25 katı civarında sonuçlar verir.

Çalışma Prensibi

En Yakın Komşu Heuristiği:
Boş bir ziyaret listesi oluştur ve başlangıç şehrini ekle.
Şu anki şehre en yakın ve henüz ziyaret edilmemiş olan şehri bul.
O şehre git ve ziyaret edildi olarak işaretle.
Tüm şehirler bittiğinde başlangıç şehrine geri dönerek turu tamamla.
2-Opt İyileştirmesi:
Mevcut bir tur al (örneğin En Yakın Komşu ile üretilmiş).
Her i ve j kenar çifti için (i+1 < j):
İki kenarı çıkar, aradaki yolu ters çevirerek bağla ve yeni tur uzunluğunu hesapla.
Eğer yeni uzunluk eskisinden kısaysa, değişikliği kalıcı yap ve aramayı baştan başlat.
Daha fazla iyileştirme yapılamayana (2-opt local minimum) kadar döngüyü sürdür.

Kod Örnekleri

Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.

Gezgin Satıcı ve Yerel Arama (Traveling Salesman & Local Search) Algoritması - TypeScript

1function getDistance(x1: number, y1: number, x2: number, y2: number): number {
2  return Math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2);
3}
4
5export function calculateTotalDistance(tour: number[], pts: [number, number][]): number {
6  let dist = 0;
7  for (let i = 0; i < tour.length; i++) {
8    const p1 = pts[tour[i]];
9    const p2 = pts[tour[(i + 1) % tour.length]];
10    dist += getDistance(p1[0], p1[1], p2[0], p2[1]);
11  }
12  return dist;
13}
14
15export function twoOpt(pts: [number, number][]): number[] {
16  const n = pts.length;
17  // Initialize with a simple 0..n-1 tour
18  let tour = Array.from({ length: n }, (_, i) => i);
19  let improved = true;
20  
21  while (improved) {
22    improved = false;
23    for (let i = 1; i < n - 1; i++) {
24      for (let j = i + 1; j < n; j++) {
25        // 2-opt swap: reverse segment from i to j
26        const newTour = [...tour.slice(0, i), ...tour.slice(i, j + 1).reverse(), ...tour.slice(j + 1)];
27        if (calculateTotalDistance(newTour, pts) < calculateTotalDistance(tour, pts)) {
28          tour = newTour;
29          improved = true;
30          break;
31        }
32      }
33      if (improved) break;
34    }
35  }
36  return tour;
37}

Kendi Verilerinizle Test Edin

Şehir koordinatlarını girerek 2-Opt yerel iyileştirmesi ve Kapsamlı Aramayı karşılaştırın.

TSP ve Yerel Arama Görselleştirici

Şehir koordinatlarını girerek 2-Opt yerel iyileştirmesi ve Kapsamlı Aramayı karşılaştırın.

Girdi

Sonuç

Henüz çalıştırılmadı

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

En İyi Durum: O(n^2) - Basit sezgisel

Ortalama Durum: O(k * n^2) - 2-Opt iyileştirmesi

En Kötü Durum: O(n!) - Kapsamlı Arama

Alan Karmaşıklığı

O(n) - Tur dizisi saklama - Bu algoritmanın karmaşıklığı belirtilmemiş.

Heuristik ve Kesin Çözüm Kıyaslaması

Kapsamlı Arama n=10 için yaklaşık 180,000 tur incelerken, n=15 için bu sayı 43 milyara çıkar ve hesaplanamaz hale gelir.
2-Opt algoritması, n=100 gibi büyük boyutlarda bile milisaniyeler içinde optimuma çok yakın (%2-5 fark) çözümler üretebilir.
Yerel aramanın kalitesi, başlangıç turuna çok bağımlıdır; bu nedenle önce Nearest Neighbor ile makul bir tur üretip ardından 2-Opt uygulamak yaygındır.

Avantajlar ve Dezavantajlar

Avantajlar

2-Opt, uygulaması kolay ve son derece hızlı çalışan bir lokal optimize edicidir.
Çok büyük şehir setlerinde kabul edilebilir sürelerde oldukça kısa turlar sunar.
NP-Zor bir problemi saniyeler bazında çözmek için idealdir.

Dezavantajlar

Sezgisel yöntemlerin hiçbirisi global optimal çözümü garanti etmez.
Lokal minimum tuzaklarına takılıp kalabilir.
Büyük şehir adetlerinde 2-Opt araması da $O(n^2)$ yapısı gereği yavaşlayabilir.