Gezgin Satıcı Problemi: Python, C++ Algoritma

Gezgin Satıcı Problemi (TSP) Nedir?

Gezgin Satıcı Problemi (TSP), teorik bilgisayar bilimlerinde klasik bir kombinatoryal optimizasyon problemidir. Şehirlerden oluşan bir grafik verildiğinde, TSP her düğümü tam olarak bir kez ziyaret eden ve başlangıç ​​şehrine geri dönen en kısa yolu bulmayı amaçlar.

Problem açıklamasında şehirlerin bir listesi ve her şehir çifti arasındaki mesafeler verilmiştir.

Amaç: Başlangıç ​​şehrinden yola çıkın, her şehri tam olarak bir kez ziyaret edin ve başlangıç ​​şehrine geri dönün. Amaç, mümkün olan en kısa gidiş-dönüş rotasını bulmaktır.

TSP örneği

Aşağıdaki grafikte 1, 2, 3 ve 4 şehirleri temsil ederken, her kenardaki ağırlık bu şehirler arasındaki mesafeyi göstermektedir.

Amaç, başlangıç ​​şehrinden yola çıkan, her şehri tam olarak bir kez ziyaret eden ve başlangıç ​​şehrine geri dönen mümkün olan en kısa turu bulmaktır.

Yukarıdaki grafik için en uygun rota şudur: 1-2-4-3-1En kısa turun maliyeti 10 + 25 + 30 + 15 = 'dir. 80.

Gezgin Satıcı Problemine Farklı Çözümler

Gezgin Satıcı Problemi, bilinen hiçbir polinom zamanlı algoritmanın tam olarak çözememesi nedeniyle NP-zor olarak sınıflandırılır. Karmaşıklık, şehir sayısıyla üstel olarak artar.

Gezgin Satıcı Problemi'ne (TSP) saldırmanın birçok yolu vardır. En yaygın yaklaşımlar şunlardır:

Kaba Kuvvet Yaklaşımı: Basit yöntem, her olası turu hesaplar ve bunları karşılaştırır. n şehirli bir grafikteki tur sayısı şöyledir: n!Bu durum, kaba kuvvet yöntemini yaklaşık on şehirden fazlası için hesaplama açısından çok pahalı hale getiriyor.

Dal ve Sınır Yöntemi: Sorun alt sorunlara ayrılır ve bu alt sorunların çözümleri bir araya gelerek en uygun çözümü oluşturur. Etkin eleme, mevcut en iyi maliyeti geçemeyen kısmi turları ortadan kaldırır.

Bu eğitim videosu aşağıdakileri göstermektedir: dinamik programlama yaklaşımıBu, dallanma ve sınırlandırma algoritmasının önbelleğe alınmış versiyonudur ve Bellman-Held-Karp algoritmasıyla eşleşir.

Dinamik program: Bu, örtüşmeyi yeniden kullanarak en uygun çözümü arayan kesin bir yöntemdir.ping Alt problem sonuçları. Bu, neredeyse en iyi olana göre daha yavaştır. açgözlü yöntemlerAncak her zaman küresel ölçekte en uygun turu sunar.

Bu yaklaşımın hesaplama karmaşıklığı O(N² × 2^N)Bu konuyu makalenin ilerleyen bölümlerinde ele alacağız.

En Yakın Komşu Yöntemi: Her zaman en yakın ziyaret edilmemiş şehre atlayan sezgisel açgözlü bir yaklaşım. Dinamik programlamadan çok daha ucuzdur, ancak optimal bir turu garanti etmez; bu nedenle, hızın kesin minimumlardan daha önemli olduğu durumlarda optimuma yakın çözümler için kullanılır.

Gezgin Satıcı Problemi Algoritması

Gezgin Satıcı Problemini (TSP) çözmek için dinamik programlama yaklaşımını kullanıyoruz. Algoritmaya başlamadan önce, birkaç terimi açıklığa kavuşturalım:

• Grafik G = (V, E) Köşeler ve kenarlardan oluşan bir kümedir.
• V Köşe noktalarının kümesidir.
• E Kenarlar kümesidir.
• Köşeler kenarlar aracılığıyla bağlanır.
• Dist(i, j) i ve j noktaları arasındaki negatif olmayan mesafeyi ifade eder.

S'nin, {1, 2, 3, …, n} kümesinden seçilen şehirlerin bir alt kümesi olduğunu varsayalım; burada i ve j bu alt kümedeki iki şehri temsil etmektedir. O halde cost(i, S, j) i noktasından başlayıp S kümesindeki her şehri tam olarak bir kez ziyaret eden ve j noktasında sona eren en kısa yolun uzunluğudur.

Örneğin, cost(1, {2, 3, 4}, 1) Aşağıdaki durumlarda en kısa yolu ifade eder:

• Başlangıç ​​şehri 1
• 2, 3 ve 4 numaralı şehirler yalnızca bir kez ziyaret edilir
• Bitiş noktası 1

Dinamik programlamanın yineleme bağıntısı şöyledir:

• set cost(i, {}, i) = 0Bu da i noktasında sıfır maliyetle başlayıp bittiğimiz anlamına gelir.
• Ne zaman |S| > 1, tanımlamak cost(i, S, 1) = ∞ için i ≠ 1Çünkü turun gerçek maliyeti henüz bilinmiyor.
• 1. şehirden başlayarak, bir sonraki şehri şu şekilde seçin: cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] için i ∈ S hem de i ≠ j.

Yukarıdaki grafik için komşuluk matrisi aşağıdaki gibidir:

Algoritmanın işleyiş şekli şu şekildedir:

) 1 Adım Yolculuk 1. şehirden başlar, diğer tüm şehirleri birer kez ziyaret eder ve tekrar 1. şehre döner.

) 2 Adım S, şehirlerin bir alt kümesidir. Her |S| > 1 için, başlangıç ​​değerini belirleyin. cost(i, S, 1) = ∞. İşte cost(i, S, j) i noktasından başlayan, S kümesindeki şehirleri bir kez ziyaret eden ve j noktasına ulaşan bir turu ifade eder. Mesafe bu noktada bilinmediği için sonsuzdan başlıyoruz. Dolayısıyla değerler şunlardır:

cost(2, {3, 4}, 1) = ∞ Bu, 2. şehirden başlayıp 3. ve 4. şehirlerden geçerek 1. şehre ulaşacağımız anlamına gelir; maliyeti ise bilinmiyor. Benzer şekilde:

cost(3, {2, 4}, 1) = ∞

cost(4, {2, 3}, 1) = ∞

) 3 Adım S kümesinin her alt kümesi için şunu hesaplayın:

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ], Burada j ∈ S hem de i ≠ j.

Bu, i şehrinden başlayan, şehirlerin alt kümesini bir kez ziyaret eden ve j şehrine geri dönen minimum maliyetli turdur. Tur 1. şehirden başladığı için, optimal maliyet şöyledir: cost(1, {other cities}, 1).

Tekrarlama İşlemini Adım Adım Uygulamak

Şimdi S = {1, 2, 3, 4}. Dört eleman var, dolayısıyla alt küme sayısı şöyledir: 2^4 = 16Bu alt kümeler şunlardır:

1) |S| = 0: {Φ}

2) |S| = 1: {{1}, {2}, {3}, {4}}

3) |S| = 2: {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}

4) |S| = 3: {{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}

5) |S| = 4: {{1, 2, 3, 4}}

Tur 1. şehirden başladığı için, ara maliyetleri hesaplarken 1. şehri içeren tüm alt kümeleri atabiliriz.

Algoritmanın hesaplama süreci şu şekilde ilerler:

1) |S| = Φ:

• maliyet(2, Φ, 1) = mesafe(2, 1) = 10
• maliyet(3, Φ, 1) = mesafe(3, 1) = 15
• maliyet(4, Φ, 1) = mesafe(4, 1) = 20

2) |S| = 1:

• maliyet(2, {3}, 1) = mesafe(2, 3) + maliyet(3, Φ, 1) = 35 + 15 = 50
• maliyet(2, {4}, 1) = mesafe(2, 4) + maliyet(4, Φ, 1) = 25 + 20 = 45
• maliyet(3, {2}, 1) = mesafe(3, 2) + maliyet(2, Φ, 1) = 35 + 10 = 45
• maliyet(3, {4}, 1) = mesafe(3, 4) + maliyet(4, Φ, 1) = 30 + 20 = 50
• maliyet(4, {2}, 1) = mesafe(4, 2) + maliyet(2, Φ, 1) = 25 + 10 = 35
• maliyet(4, {3}, 1) = mesafe(4, 3) + maliyet(3, Φ, 1) = 30 + 15 = 45

3) |S| = 2:

• maliyet(2, {3, 4}, 1) = min [ mesafe(2, 3) + maliyet(3, {4}, 1) = 35 + 50 = 85, mesafe(2, 4) + maliyet(4, {3}, 1) = 25 + 45 = 70 ] = 70
• maliyet(3, {2, 4}, 1) = min [ mesafe(3, 2) + maliyet(2, {4}, 1) = 35 + 45 = 80, mesafe(3, 4) + maliyet(4, {2}, 1) = 30 + 35 = 65 ] = 65
• maliyet(4, {2, 3}, 1) = min [ mesafe(4, 2) + maliyet(2, {3}, 1) = 25 + 50 = 75, mesafe(4, 3) + maliyet(3, {2}, 1) = 30 + 45 = 75 ] = 75

4) |S| = 3:

• maliyet(1, {2, 3, 4}, 1) = min [ mesafe(1, 2) + maliyet(2, {3, 4}, 1) = 10 + 70 = 80, mesafe(1, 3) + maliyet(3, {2, 4}, 1) = 15 + 65 = 80, mesafe(1, 4) + maliyet(4, {2, 3}, 1) = 20 + 75 = 95 ] = 80

Dolayısıyla en uygun çözüm şudur: 1-2-4-3-1.

sözde kod

Algorithm: Traveling-Salesman-Problem
Cost (1, {}, 1) = 0
for s = 2 to n do
    for all subsets S belongs to {1, 2, 3, ..., n} of size s
        Cost (s, S, 1) = Infinity
    for all i in S and i != 1
        Cost (i, S, j) = min {Cost (i, S - {i}, j) + dist(i, j) for j in S and i != j}
Return min(i) Cost (i, {1, 2, 3, ..., n}, j) + d(j, i)

C/'de uygulamaC++

İşte uygulamanın kendisi. C++Aşağıdaki sürüm, kaynak kodun başındaki hatayı düzeltiyor. return Hata, tüm turları listelemek yerine ilk permütasyondan sonra geri döndü.

#include <bits/stdc++.h>
using namespace std;
#define V 4
#define MAX 1000000

int tsp(int graph[][V], int s) {
    vector<int> vertex;
    for (int i = 0; i < V; i++)
        if (i != s)
            vertex.push_back(i);

    int min_cost = MAX;
    do {
        int current_cost = 0;
        int j = s;
        for (int i = 0; i < vertex.size(); i++) {
            current_cost += graph[j][vertex[i]];
            j = vertex[i];
        }
        current_cost += graph[j][s];
        min_cost = min(min_cost, current_cost);
    } while (next_permutation(vertex.begin(), vertex.end()));

    return min_cost;
}

int main() {
    int graph[][V] = {
        { 0, 10, 15, 20 },
        { 10, 0, 35, 25 },
        { 15, 35, 0, 30 },
        { 20, 25, 30, 0 }
    };
    int s = 0;
    cout << tsp(graph, s) << endl;
    return 0;
}

Çıktı:

80

Uygulama Python

MKS Python uygulama şunu yansıtıyor C++ Bu sürüm, kaynağın hatasını düzeltir. from itertools, import Virgül yazım hatası, yanlış yerleştirilmiş return iç döngünün içinde ve üzerindeki rastgele girinti s = 0.

from sys import maxsize
from itertools import permutations

V = 4

def tsp(graph, s):
    vertex = []
    for i in range(V):
        if i != s:
            vertex.append(i)

    min_cost = maxsize
    for perm in permutations(vertex):
        current_cost = 0
        k = s
        for j in perm:
            current_cost += graph[k][j]
            k = j
        current_cost += graph[k][s]
        min_cost = min(min_cost, current_cost)
    return min_cost

graph = [[0, 10, 15, 20],
         [10, 0, 35, 25],
         [15, 35, 0, 30],
         [20, 25, 30, 0]]
s = 0
print(tsp(graph, s))

Çıktı:

80

TSP'ye Akademik Çözümler

Bilgisayar bilimcileri, Gezgin Satıcı Problemi için geliştirilmiş polinom zamanlı algoritmalar bulmak için on yıllardır çalışıyorlar. Şimdiye kadar, Gezgin Satıcı Problemi hala NP-zor bir problem olarak kalmıştır.

Yayınlanmış çeşitli teknikler, TSP örneklerinin belirli aileleri için pratik karmaşıklığı azaltmaktadır:

• Klasik simetrik TSP, aşağıdaki yöntemle çözülür: Sıfır Sonek Yöntemi.
• MKS Biyocoğrafya Tabanlı Optimizasyon Algoritması TSP'ye karşılık gelen optimizasyon problemlerini çözmek için göç stratejilerini kullanır.
• MKS Çok Amaçlı Evrimsel Algoritma Çok amaçlı TSP için tasarlanmıştır ve NSGA-II üzerine kurulmuştur.
• MKS Çoklu Ajan Sistemi Bu yaklaşım, sabit hesaplama kaynaklarıyla N şehir için Gezgin Satıcı Problemini (TSP) çözer.
• MKS Lin-Kernighan sezgisel yaklaşımı ve halefi LKH Milyonlarca şehir içeren örneklerde, turları optimumun %2-3'ü içinde gerçekleştirin.
• Anlaşma On binlerce şehri içeren kıyaslama örnekleri için kesin optimumları hesaplamak amacıyla kesme düzlemlerini ve dallanma-kesme yöntemini kullanır.

Gezgin Satıcı Probleminin Uygulanması

Gezgin Satıcı Problemi, gerçek dünyada hem saf hem de değiştirilmiş biçimlerde karşımıza çıkar. Başlıca uygulamalarından bazıları şunlardır:

• Planlama, lojistik ve mikroçip üretimi: Mikroçip endüstrisindeki çip yerleştirme problemleri, robot kolunun hareket süresini en aza indirmek için TSP varyantları olarak modellenmiştir.
• DNA dizilimi: DNA dizilemesinde, şehirlerin DNA parçalarını, mesafelerin ise parçalar arasındaki benzerliği temsil ettiği değiştirilmiş bir TSP (Transparency Projection) kullanılır.
• Astronomi: Gökbilimciler, gözlem hedefleri arasında teleskopları hareket ettirmek için harcanan süreyi en aza indirmek amacıyla TSP'yi kullanırlar.
• Optimal kontrol: TSP formülasyonları, geçiş maliyetini en aza indirirken birden fazla kısıtlamaya uyulması gereken optimal kontrol problemlerini modeller.
• Son kilometre teslimatı: AmazonUPS ve yemek dağıtım uygulamaları, sürücüler için durakları sıralamak üzere dinamik TSP varyantlarını çözüyor.
• Depo toplama: Robotik ve insanlı sipariş toplama ekipleri, dağıtım merkezleri içindeki seyahat süresini kısaltan, TSP (Taşıyıcı Servis Planlaması) optimizasyonlu rotaları takip eder.

TSP'nin Karmaşıklık Analizi

• Zaman Karmaşıklığı: Held-Karp dinamik programlama yaklaşımı 2 problemi çözer.^N Her bir başlangıç ​​düğümü için alt kümeler elde edilir, bu da N × 2^N Alt problemler. Her bir alt problemin birleştirilmesi doğrusal zaman alır. Başlangıç ​​düğümü belirtilmemişse, N düğüm üzerinde bir dış döngü gereklidir. Toplam zaman karmaşıklığı şöyledir: O(N² × 2^N).
• Uzay Karmaşıklığı: DP tablosu depolar C(S, i) Köşe kümesinin her bir alt kümesi S için 2 tane vardır.^N Düğüm başına alt küme sayısı, dolayısıyla alan karmaşıklığı şöyledir: O(N × 2^N)Genellikle şu şekilde yazılır: O(2^N) N'nin sabit kabul edildiği durumda.

Daha sonra aşağıdakiler hakkında bilgi edinin: Eratosthenes Algoritmasının Süzülmesi.

SSS