DAA - Seyahat Eden Satıcı Sorunu

Sorun bildirimi

Bir gezginin, tüm şehirler arasındaki mesafelerin bilindiği ve her şehrin yalnızca bir kez ziyaret edilmesi gereken bir listeden tüm şehirleri ziyaret etmesi gerekir. Her şehri tam olarak bir kez ziyaret edip asıl şehre geri döndüğü en kısa rota nedir?

Çözüm

Seyahat eden satıcı problemi, en kötü şöhretli hesaplama problemidir. Olası her turu değerlendirmek ve en iyisini seçmek için kaba kuvvet yaklaşımını kullanabiliriz. İçinn bir grafikteki köşe sayısı, (n - 1)! olasılık sayısı.

Dinamik programlama yaklaşımını kullanan kaba kuvvet yerine, polinom zaman algoritması olmasa da, çözüm daha kısa sürede elde edilebilir.

Bir grafik düşünelim G = (V, E), nerede V bir dizi şehirdir ve Eağırlıklı kenarlar kümesidir. Kenare(u, v) o köşeleri temsil eder u ve vbağlılar. Köşe arası mesafeu ve v dır-dir d(u, v), negatif olmamalıdır.

Şehirde başladığımızı varsayalım 1 ve bazı şehirleri ziyaret ettikten sonra şimdi şehirdeyiz j. Dolayısıyla bu kısmi bir tur. Kesinlikle bilmemiz gerekiyorj, çünkü bu hangi şehirlerin bir sonraki ziyaret için en uygun olduğunu belirleyecektir. Ayrıca şimdiye kadar ziyaret edilen tüm şehirleri de bilmemiz gerekiyor, böylece hiçbirini tekrar etmeyelim. Dolayısıyla bu uygun bir alt problemdir.

Bir şehir alt kümesi için S Є {1, 2, 3, ... , n} içerir 1, ve j Є S, İzin Vermek C(S, j) içindeki her düğümü ziyaret eden en kısa yolun uzunluğu S tam olarak bir kez 1 ve bitiyor j.

Ne zaman |S| > 1, tanımlarızC(S, 1) = ∝ çünkü yol başlayamaz ve bitemez 1.

Şimdi ifade edelim C(S, j)daha küçük alt problemler açısından. Başlamamız gerek1 ve biter j. Bir sonraki şehri öyle bir şekilde seçmeliyiz ki

$$ C (S, j) = min \: C (S - \ lbrace j \ rbrace, i) + d (i, j) \: burada \: i \ in S \: ve \: i \ neq jc ( S, j) = minC (s- \ lbrace j \ rbrace, i) + d (i, j) \: burada \: i \ in S \: ve \: i \ neq j $$

Algorithm: Traveling-Salesman-Problem 
C ({1}, 1) = 0 
for s = 2 to n do 
   for all subsets S Є {1, 2, 3, … , n} of size s and containing 1 
      C (S, 1) = ∞ 
   for all j Є S and j ≠ 1 
      C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j} 
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)

Analiz

En çok $ 2 ^ nn $ alt problemleri vardır ve her birinin çözülmesi doğrusal zaman alır. Bu nedenle, toplam çalışma süresi $ O (2 ^ nn ^ 2) $ şeklindedir.

Misal

Aşağıdaki örnekte, seyyar satıcı problemini çözme adımlarını göstereceğiz.

Yukarıdaki grafikten aşağıdaki tablo hazırlanmıştır.

	1	2	3	4
1	0	10	15	20
2	5	0	9	10
3	6	13	0	12
4	8	8	9	0

S = Φ

$$ \ small Maliyet (2, \ Phi, 1) = d (2,1) = 5 \ small Cost (2, \ Phi, 1) = d (2,1) = 5 $$

$$ \ small Maliyet (3, \ Phi, 1) = d (3,1) = 6 \ small Cost (3, \ Phi, 1) = d (3,1) = 6 $$

$$ \ small Maliyet (4, \ Phi, 1) = d (4,1) = 8 \ small Cost (4, \ Phi, 1) = d (4,1) = 8 $$

S = 1

$$ \ small Maliyet (i, s) = min \ lbrace Maliyet (j, s - (j)) + d [i, j] \ rbrace \ small Maliyet (i, s) = min \ lbrace Maliyet (j, s ) - (j)) + d [i, j] \ rbrace $$

$$ \ small Maliyet (2, \ lbrace 3 \ rbrace, 1) = d [2,3] + Maliyet (3, \ Phi, 1) = 9 + 6 = 15cost (2, \ lbrace3 \ rbrace, 1) = d [2,3] + maliyet (3, \ Phi, 1) = 9 + 6 = 15 $$

$$ \ small Maliyet (2, \ lbrace 4 \ rbrace, 1) = d [2,4] + Maliyet (4, \ Phi, 1) = 10 + 8 = 18cost (2, \ lbrace4 \ rbrace, 1) = d [2,4] + maliyet (4, \ Phi, 1) = 10 + 8 = 18 $$

$$ \ small Maliyet (3, \ lbrace 2 \ rbrace, 1) = d [3,2] + Maliyet (2, \ Phi, 1) = 13 + 5 = 18cost (3, \ lbrace2 \ rbrace, 1) = d [3,2] + maliyet (2, \ Phi, 1) = 13 + 5 = 18 $$

$$ \ small Maliyet (3, \ lbrace 4 \ rbrace, 1) = d [3,4] + Maliyet (4, \ Phi, 1) = 12 + 8 = 20cost (3, \ lbrace4 \ rbrace, 1) = d [3,4] + maliyet (4, \ Phi, 1) = 12 + 8 = 20 $$

$$ \ small Maliyet (4, \ lbrace 3 \ rbrace, 1) = d [4,3] + Maliyet (3, \ Phi, 1) = 9 + 6 = 15cost (4, \ lbrace3 \ rbrace, 1) = d [4,3] + maliyet (3, \ Phi, 1) = 9 + 6 = 15 $$

$$ \ small Maliyet (4, \ lbrace 2 \ rbrace, 1) = d [4,2] + Maliyet (2, \ Phi, 1) = 8 + 5 = 13cost (4, \ lbrace2 \ rbrace, 1) = d [4,2] + maliyet (2, \ Phi, 1) = 8 + 5 = 13 $$

S = 2

$$ \ small Maliyet (2, \ lbrace 3, 4 \ rbrace, 1) = \ begin {case} d [2, 3] + Cost (3, \ lbrace 4 \ rbrace, 1) = 9 + 20 = 29 \ \ d [2, 4] + Maliyet (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 = 25 \ small Cost (2, \ lbrace 3,4 \ rbrace, 1) \\\ lbrace d [ 2,3] + \ küçük maliyet (3, \ lbrace4 \ rbrace, 1) = 9 + 20 = 29d [2,4] + \ small Cost (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 \ end {case} = 25 $$

$$ \ small Maliyet (3, \ lbrace 2, 4 \ rbrace, 1) = \ begin {case} d [3, 2] + Cost (2, \ lbrace 4 \ rbrace, 1) = 13 + 18 = 31 \ \ d [3, 4] + Maliyet (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 = 25 \ small Cost (3, \ lbrace 2,4 \ rbrace, 1) \\\ lbrace d [ 3,2] + \ küçük maliyet (2, \ lbrace4 \ rbrace, 1) = 13 + 18 = 31d [3,4] + \ small Cost (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 \ end {case} = 25 $$

$$ \ small Maliyet (4, \ lbrace 2, 3 \ rbrace, 1) = \ begin {case} d [4, 2] + Cost (2, \ lbrace 3 \ rbrace, 1) = 8 + 15 = 23 \ \ d [4, 3] + Maliyet (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 = 23 \ small Cost (4, \ lbrace 2,3 \ rbrace, 1) \\\ lbrace d [ 4,2] + \ küçük maliyet (2, \ lbrace3 \ rbrace, 1) = 8 + 15 = 23d [4,3] + \ small Cost (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 \ end {case} = 23 $$

S = 3

$$ \ small Maliyet (1, \ lbrace 2, 3, 4 \ rbrace, 1) = \ begin {case} d [1, 2] + Maliyet (2, \ lbrace 3, 4 \ rbrace, 1) = 10 + 25 = 35 \\ d [1, 3] + Maliyet (3, \ lbrace 2, 4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1, 4] + Maliyet (4, \ lbrace 2, 3 \ rbrace, 1) = 20 + 23 = 43 = 35 maliyet (1, \ lbrace 2,3,4 \ rbrace), 1) \\ d [1,2] + maliyet (2, \ lbrace 3,4 \ rbrace , 1) = 10 + 25 = 35 \\ d [1,3] + maliyet (3, \ lbrace 2,4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1,4] + maliyet (4 , \ lbrace 2,3 \ rbrace, 1) = 20 + 23 = 43 = 35 \ end {case} $$

Minimum maliyet yolu 35'tir.

Maliyetten başla {1, {2, 3, 4}, 1}asgari değeri alıyoruz d [1, 2]. Ne zamans = 31'den 2'ye kadar olan yolu seçin (maliyet 10'dur) ve sonra geriye gidin. Ne zamans = 2asgari değeri alıyoruz d [4, 2]. 2'den 4'e kadar yolu seçin (maliyet 10'dur), sonra geriye gidin.

Ne zaman s = 1asgari değeri alıyoruz d [4, 3]. 4'ten 3'e kadar olan yolu seçerek (maliyet 9'dur), sonra gideceğiz ve sonras = Φadım. Minimum değeri alıyoruzd [3, 1] (maliyet 6'dır).