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

By: Sarah Chen Sarah Chen
Hours Güncellenmiş

Gezgin Satıcı Problemi (TSP) Nedir?

Gezgin Satıcı Problemi (TSP), teorik bilgisayar biliminin klasik bir kombinatorik problemidir. Problem, tüm düğümlerin yalnızca bir kez ziyaret edilmesi ve başlangıç ​​şehre geri dönülmesi koşuluyla bir grafikteki en kısa yolun bulunmasını istemektedir.

Problem tanımı, şehirlerin bir listesini, her şehir arasındaki mesafelerle birlikte verir.

Amaç: Başlangıç ​​şehrinden başlamak için diğer şehirleri yalnızca bir kez ziyaret edin ve tekrar orijinal şehre dönün. Hedefimiz gidiş-dönüş rotasını tamamlamak için mümkün olan en kısa yolu bulmaktır.

TSP örneği

Burada 1, 2, 3 ve 4'ün şehirleri temsil ettiği ve her kenarın ağırlığının bu şehirler arasındaki mesafeyi temsil ettiği bir grafik verilmektedir.

TSP örneği

Amaç, başlangıç ​​şehirden başlayan, diğer şehirleri veya düğümleri yalnızca bir kez ziyaret ederek grafiği geçen ve başlangıç ​​şehre dönen tur için mümkün olan en kısa yolu bulmaktır.

Yukarıdaki grafik için en uygun rota minimum maliyet yolunu takip etmektir: 1-2-4-3-1. Ve bu en kısa rotanın maliyeti 10+25+30+15 =80 olur

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

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

Seyahat Eden Satıcı Problemi (TSP), polinom zamanlı bir algoritmaya sahip olmaması nedeniyle NP-zor bir problem olarak sınıflandırılır. Karmaşıklık, şehir sayısının artmasıyla üstel olarak artar.

Gezgin satıcı problemini (tsp) çözmenin birden fazla yolu vardır. Bazı popüler çözümler şunlardır:

Kaba kuvvet yaklaşımı saf bir yöntemdir Gezgin satıcı problemlerini çözmek için. Bu yaklaşımda öncelikle olası tüm yolları hesaplıyoruz ve sonra bunları karşılaştırıyoruz. N şehirden oluşan bir grafikteki yol sayısı n! Bu kaba kuvvet yaklaşımıyla gezgin satıcı problemini çözmek hesaplama açısından çok pahalıdır.

Dal ve sınır yöntemi: Bu yaklaşımda problem alt problemlere bölünür. Bu bireysel alt problemlerin çözümü en uygun çözümü sağlayacaktır.

Bu eğitimde, seyahat eden satıcı problemini çözmek için bu dal-sınır yönteminin özyinelemeli versiyonu olan dinamik bir programlama yaklaşımı gösterilecektir.

Dinamik program olası tüm rotaları analiz ederek en uygun çözümleri aramaya yönelik bir yöntemdir. Gezgin satıcı problemlerini nispeten daha yüksek maliyetle çözen kesin çözüm yöntemlerinden biridir. açgözlü yöntemler optimale yakın bir çözüm sağlar.

Bu yaklaşımın hesaplama karmaşıklığı Ç(N^2 * 2^N) Bu konu makalenin ilerleyen kısımlarında ele alınacaktır.

En yakın komşu yöntemi en yakın komşu düğümünü seçtiğimiz sezgisel tabanlı açgözlü bir yaklaşımdır. Bu yaklaşım, dinamik yaklaşımdan hesaplama açısından daha az maliyetlidir. Ancak en iyi çözümün garantisini sağlamaz. Bu yöntem, en iyiye 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ı kullanacağız.

Algoritmaya başlamadan önce bazı terminolojileri tanıyalım:

  • Bir dizi köşe ve kenardan oluşan bir G=(V, E) grafiği.
  • V köşeler kümesidir.
  • E kenarlar kümesidir.
  • Köşeler kenarlar aracılığıyla bağlanır.
  • Dist(i,j), i ve j adlı iki köşe arasındaki negatif olmayan mesafeyi belirtir.

S'nin şehirlerin alt kümesi olduğunu ve {1, 2, 3, …, n}'ye ait olduğunu varsayalım; burada 1, 2, 3…n şehirler ve i, j bu alt kümedeki iki şehirdir. Şimdi maliyet(i, S, j), S'deki düğümü ziyaret eden en kısa yolun uzunluğu olarak tanımlanır; bu, başlangıç ​​ve bitiş noktalarının sırasıyla i ve j olduğu tam bir kezdir.

Örneğin maliyet (1, {2, 3, 4}, 1), en kısa yolun uzunluğunu belirtir; burada:

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

Dinamik programlama algoritması şöyle olacaktır:

  • Maliyet(i, , i) = 0'ı ayarlayın; bu, i'de başlayıp i'de bittiğimiz ve maliyetin 0 olduğu anlamına gelir.
  • Ne zaman |S| > 1, maliyet(i, S, 1) = ∝'yi tanımlarız, burada i !=1 . Çünkü başlangıçta diğer şehirler üzerinden i. şehirden 1. şehre ulaşmanın maliyetini tam olarak bilmiyoruz.
  • Şimdi saat 1’den başlayıp turu tamamlamamız gerekiyor. Bir sonraki şehri şu şekilde seçmeliyiz:

maliyet(i, S, j)=min maliyet (i, S−{i}, j)+dist(i,j) burada i∈S ve i≠j

Verilen şekil için komşuluk matrisi şu şekilde olacaktır:

Gezgin Satıcı Problemi Algoritması

uzaklık(i,j) 1 2 3 4
1 0 10 15 20
2 10 0 35 25
3 15 35 0 30
4 20 25 30 0

Algoritmamızın nasıl çalıştığını görelim:

) 1 Adım Yolculuğumuzu 1. şehirden başlayıp, diğer şehirleri bir kez ziyaret edip 1. şehre dönmeyi düşünüyoruz.

) 2 Adım S, şehirlerin alt kümesidir. Algoritmamıza göre, her |S| > 1 için mesafe maliyetini (i, S, 1) = ∝ olarak ayarlayacağız. Burada maliyet (i, S, j), i şehrinden başladığımız, S'nin şehirlerini bir kez ziyaret ettiğimiz ve şimdi j şehrinde olduğumuz anlamına gelir. Mesafeyi henüz bilmediğimiz için bu yol maliyetini sonsuz olarak ayarladık. Bu nedenle değerler şu şekilde olacaktır:

Maliyet (2, {3, 4}, 1) = ∝ ; bu gösterim 2. şehirden başladığımızı, 3. ve 4. şehirlerden geçerek 1'e ulaştığımızı gösterir. Ve yolun maliyeti sonsuzdur. Benzer şekilde-

maliyet(3, {2, 4}, 1) = ∝

maliyet(4, {2, 3}, 1) = ∝

) 3 Adım Şimdi, S'nin tüm alt kümeleri için aşağıdakileri bulmamız gerekiyor:

maliyet(i, S, j)=min maliyet (i, S−{i}, j)+dist(i,j), burada j∈S ve i≠j

Bu, i'den başlayıp şehirlerin alt kümesinden bir kez geçip j şehrine dönmenin minimum maliyet yolu anlamına gelir. Yolculuğun 1. şehirden başladığını düşünürsek, en uygun yol maliyeti = maliyet(1, {diğer şehirler}, 1) olacaktır.

İLGİLİ MAKALELER

Bunu nasıl başarabileceğimizi öğrenelim:

Şimdi S = {1, 2, 3, 4}. Dört unsur var. Dolayısıyla alt kümelerin sayısı 2^4 veya 16 olacaktır. Bu alt kümeler:

1) |S| = Boş:

{Φ}

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}}

1'den başladığımız için şehir 1'i içeren alt kümeleri atabiliriz.

Algoritma hesaplaması:

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,

dist[2,4]+Maliyet(4,{3},1) = 25+45 = 70 ] = 70

maliyet (3, {2, 4}, 1) = min [ dist[3,2]+Maliyet(2,{4},1) = 35+45 = 80,

dist[3,4]+Maliyet(4,{2},1) = 30+35 = 65 ] = 65

maliyet (4, {2, 3}, 1) = min [ dist[4,2]+Cost(2,{3},1) = 25+50 = 75

dist[4,3]+Maliyet(3,{2},1) = 30+45 = 75 ] = 75

4) |S| = 3:

maliyet (1, {2, 3, 4}, 1) = min [ dist[1,2]+Maliyet(2,{3,4},1) = 10+70 = 80

dist[1,3]+Maliyet(3,{2,4},1) = 15+65 = 80

dist[1,4]+Maliyet(4,{2,3},1) = 20+75 = 95 ] = 80

Yani en uygun çözüm şu olacaktır 1-2-4-3-1

Gezgin Satıcı Problemi Algoritması

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 Є S and i ≠ 1 
      Cost (i, S, j) = min {Cost (i, S – {i}, j) + dist(i, j) for j Є S and i ≠ j} 
Return min(i) Cost (i, {1, 2, 3, …, n}, j) + d(j, i)

C/'de uygulamaC++

İşte uygulama C++:

#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;
    while(next_permutation(vertex.begin(), vertex.end()))
     {
        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);
        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

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
	next_permutation=permutations(vertex)
	for i in next_permutation:
		current_cost = 0
		k = s
		for j in i:
			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, Seyahat Eden Satıcı Problemi için geliştirilmiş bir polinom zamanlı algoritma aramak için yıllar harcadılar. Şimdiye kadar, problem hala NP-zor.

Son yıllarda karmaşıklığı bir miktar azaltan bazı çözümler yayınlanmıştır:

  • Klasik simetrik TSP, Sıfır Sonek Yöntemi ile çözülür.
  • Biyocoğrafya Tabanlı Optimizasyon Algoritması, TSP olarak planlanabilecek optimizasyon problemlerini çözmek için geçiş stratejisini temel almaktadır.
  • Çok Amaçlı Evrimsel Algoritma, NSGA-II'ye dayalı birden fazla TSP'yi çözmek için tasarlanmıştır.
  • Çoklu Ajan Sistemi, N şehrin TSP'sini sabit kaynaklarla çözer.

Gezgin Satıcı Probleminin Uygulanması

Gezgin Satıcı Problemi (TSP), gerçek dünyada hem en saf hem de değiştirilmiş haliyle uygulanmaktadır. Bunlardan bazıları:

  • Mikroçiplerin planlanması, lojistik ve üretimi: Mikroçip sektöründe doğal olarak çip yerleştirme sorunları ortaya çıkmaktadır. Bu problemler gezici satıcı problemi olarak planlanabilir.
  • DNA dizi analizi: Seyahat eden satıcı probleminin küçük bir modifikasyonu DNA dizilemesinde kullanılabilir. Burada şehirler DNA parçalarını, mesafe ise iki DNA parçası arasındaki benzerlik ölçüsünü temsil ediyor.
  • Astronomi: Gezgin Satıcı Problemi, gökbilimciler tarafından çeşitli kaynakları gözlemlemek için harcanan zamanı en aza indirmek için uygulanır.
  • Optimum kontrol problemi: Gezgin Satıcı Problemi formülasyonu optimal kontrol problemlerinde uygulanabilir. Eklenen başka kısıtlamalar da olabilir.

TSP'nin Karmaşıklık Analizi

  • Zaman Karmaşıklığı: Toplam 2 tane var.N Her düğüm için alt problemler Yani alt problemlerin toplam sayısı N*2 olacaktır.N. Alt problemlerin her birinin çözümü doğrusal zaman gerektirir. Eğer orijin düğümü belirtilmezse N düğüm için döngü çalıştırmamız gerekir.

    Bu nedenle, optimum bir çözüm için toplam zaman karmaşıklığı, Düğüm sayısı * Alt problem sayısı * Her bir alt problemi çözmek için gereken zaman olacaktır. Zaman karmaşıklığı O(N) olarak tanımlanabilir2 * 2^N).

  • Uzay Karmaşıklığı: Dinamik programlama yaklaşımı, S'nin köşe kümesinin bir alt kümesi olduğu C(S, i)'yi depolamak için belleği kullanır. Toplam 2 tane varN her düğüm için alt kümeler. Bu nedenle, uzay karmaşıklığı O(2^N)'dir.

Daha sonra şunları öğreneceksiniz: Eratosthenes Algoritmasının Süzülmesi

Beğenebilirsin: