Held – Karp algoritması - Held–Karp algorithm

Held – Karp algoritması, olarak da adlandırılır Bellman – Held – Karp algoritması, bir dinamik program 1962'de bağımsız olarak önerilen algoritma Bellman^[1] ve Düzenlendi ve Karp^[2] çözmek için Seyahat Eden Satıcı Sorunu (TSP). TSP, Hamilton devre problemi. Sorun şu şekilde tanımlanabilir: bir ülkede N şehir turu bulmak (ziyaret edilecek tüm şehirlerin ulaşılabilir olduğu varsayılarak), tur (a) her şehri yalnızca bir kez ziyaret etmeli, (b) başlangıç noktasına dönmeli ve (c ) minimum mesafede olun.^[3]Genel olarak, TSP simetrik seyyar satıcı problemi (sTSP), asimetrik seyyar satıcı problemi (aTSP) ve çoklu seyahat eden satıcı problemi (mTSP) olarak sınıflandırılır.^{[kaynak belirtilmeli ]}

Grafik modeli

sTSP: İzin Vermek V = {v₁ ,..., v_n } bir dizi şehir, E = {(r, s) | r, s ∈ V} kenar seti olun ve d_rs = d_sr kenar ile ilişkili bir maliyet ölçüsü olabilir (r, s) ∈ E.

aTSP: Eğer d_rs ≠ d_sr en az bir (r, s) daha sonra sTSP bir aTSP olur. sTSP bir yönsüz grafik aTSP, bir Yönlendirilmiş grafik.

mTSP: Çoklu TSP probleminde, aynı şehirden başlayan birkaç satıcı var; Başlangıç şehri dışındaki her şehir, tam olarak bir satıcı tarafından tam olarak bir kez ziyaret edilmeli ve turlarının toplam uzunlukları en aza indirilmelidir. MTSP'ye, başlangıç şehrini yeniden ziyaret etmesine izin verilen standart TSP'nin bir değişikliği olarak bakılabilir. MTSP genellikle rahatlamış araç yönlendirme sorunu.

Algoritma

Açıklama

Dinamik programlama prosedürü aşağıdadır:

TSP için bir optimizasyon özelliği vardır:

   Minimum mesafeli bir yolun her alt yolu, minimum mesafenin kendisidir.

En küçüğünden başlayarak tüm alt problemlerin çözümlerini hesaplayın. Bir çözümü hesaplamak, yukarıdaki özyinelemeli denklemleri kullanarak daha küçük problemler için çözümler gerektirdiğinde, halihazırda hesaplanmış olan bu çözümlere bakın. Minimum mesafe turunu hesaplamak için, son denklemi kullanarak 1. düğümü oluşturun ve diğer düğümler için tekrarlayın. problem, hangi alt problemleri çözmemiz gerektiğini bilemeyiz, bu yüzden hepsini çözeriz.

Yinelemeli formülasyon

Şehirleri 1, 2, numaralandırın. . . , N ve şehir 1'den başladığımızı ve şehirler arasındaki mesafeyi ben ve şehir j dır-dir d_{ben, j}. Alt kümeleri düşünün S ⊆ {2, . . . , N} şehir ve için c ∈ S, İzin Vermek D(S, c) 1. şehirden başlayarak, tüm şehirleri ziyaret ederek minimum mesafe S ve şehirde bitirmek c.

İlk aşama: eğer S = {c}, sonra D(S, c) = d_1,c. Aksi takdirde: D(S, c) = dak_x∈S−c (D(S − c, x) + d_x,c ).

İkinci aşama: Tüm şehirlerin eksiksiz bir turu için minimum mesafeM = dk_{c∈ {2, ...,N}} (D({2, . . . , N}, c) + d_c,1 )

Bir tur n₁ , . . ., n_N tam tatmin ettiği zaman minimum mesafedir M = D({2, . . . , N}, n_N ) + d_{n_N,1} .

Misal^[4]

Mesafe matrisi:

{ displaystyle C = { begin {pmatrix} 0 & 2 & 9 & 10 1 & 0 & 6 & 4 15 & 7 & 0 & 8 6 & 3 & 12 & 0 end {pmatrix}}}

Fonksiyon açıklaması:

g (x, S) - 1'den başlayarak, yol min maliyeti köşe x'te biter, S kümesindeki köşeleri tam olarak bir kez geçerek
c_xy - kenar maliyeti y'den x'de biter
p (x, S) - S kümesinden sondan ikinciye kadar olan tepe noktasından x'e, TSP yolunu en sonunda oluşturmak için kullanılır.

k = 0, boş küme:

∅ ayarla:

       g (2, ∅) = c₂₁ = 1 g (3, ∅) = c₃₁ = 15 g (4, ∅) = c₄₁ = 6

k = 1, 1 öğeli kümeleri düşünün:

{2} ayarla:

       g (3, {2}) = c₃₂ + g (2, ∅) = c₃₂ + c₂₁ = 7 + 1 = 8 p (3, {2}) = 2 g (4, {2}) = c₄₂ + g (2, ∅) = c₄₂ + c₂₁ = 3 + 1 = 4 p (4, {2}) = 2

{3} ayarla:

       g (2, {3}) = c₂₃ + g (3, ∅) = c₂₃ + c₃₁ = 6 + 15 = 21 p (2, {3}) = 3 g (4, {3}) = c₄₃ + g (3, ∅) = c₄₃ + c₃₁ = 12 + 15 = 27 p (4, {3}) = 3

{4} ayarla:

       g (2, {4}) = c₂₄ + g (4, ∅) = c₂₄ + c₄₁ = 4 + 6 = 10 p (2, {4}) = 4 g (3, {4}) = c₃₄ + g (4, ∅) = c₃₄ + c₄₁ = 8 + 6 = 14 p (3, {4}) = 4

k = 2, 2 öğeden oluşan kümeleri düşünün:

{2,3} ayarla:

         g (4, {2,3}) = dk {c₄₂ + g (2, {3}), c₄₃ + g (3, {2})} = min {3 + 21, 12 + 8} = min {24, 20} = 20 p (4, {2,3}) = 3

{2,4} ayarla:

         g (3, {2,4}) = min {c₃₂ + g (2, {4}), c₃₄ + g (4, {2})} = min {7 + 10, 8 + 4} = min {17, 12} = 12 p (3, {2,4}) = 4

{3,4} ayarlayın:

          g (2, {3,4}) = dk {c₂₃ + g (3, {4}), c₂₄ + g (4, {3})} = min {6 + 14, 4 + 27} = min {20, 31} = 20 p (2, {3,4}) = 3

Optimal bir turun uzunluğu:

 f = g (1, {2,3,4}) = min {c₁₂ + g (2, {3,4}), c₁₃ + g (3, {2,4}), c₁₄ + g (4, {2,3})} = min {2 + 20, 9 + 12, 10 + 20} = min {22, 21, 30} = 21

1. düğümün öncülü: p (1, {2,3,4}) = 3

3. düğümün öncülü: p (3, {2,4}) = 4

4. düğümün öncülü: p (4, {2}) = 2

2. düğümün öncülü: p (2, {}) = 1

Bu nedenle, optimal bir TSP turu 1 → 2 → 4 → 3 → 1 ile verilir.

Sözde kod^[5]

işlevi algoritması TSP (G, n) dır-dir    için k: = 2 ila n yapmak        C ({k}, k): = d_{1, k}    sonu için    için s: = 2 -e n − 1 yapmak        hepsi için S ⊆ {2,. . . , n}, | S | = s yapmak            hepsi için k ∈ S yapmak                C (S, k): = dakika_{m ≠ k, m∈S} [C (S  {k}, m) + d_{m, k}]            sonu için        sonu için    sonu için    opt: = min_{k ≠ 1} [C ({2, 3,.., N}, k) + d_{k, 1}]    dönüş (tercih)son işlev

Karmaşıklık

Kapsamlı sayım

Herhangi bir şehirde başlayan bu kaba kuvvet yöntemi, mümkün olan her şeyi numaralandırır. permütasyonlar Ziyaret edilecek şehirler ve her permütasyonun mesafesini bulun ve minimum mesafeden birini seçin. Tümünü kapsayan toplam olası rota sayısı ${ displaystyle N}$ şehirler olarak verilebilir ${ displaystyle (N-1)!}$ ve ${ displaystyle { frac {1} {2}} (N-1)!}$ sırasıyla aTSP ve sTSP'de.^[6]

Dinamik programlama yaklaşımı

Bu algoritma, kapsamlı numaralandırmaya göre daha hızlı (ancak yine de üstel zaman) yürütme sunar ve çok fazla alan kullanmanın dezavantajı: bu algoritmanın en kötü durum zaman karmaşıklığı ${ displaystyle O (2 ^ {n} n ^ {2})}$ ve boşluk ${ displaystyle O (2 ^ {n} n)}$ .

Zaman: Hesaplamada kullanılan temel işlemler, eklemeler ve karşılaştırmalardır. İlk aşamadaki her birinin sayısı şu şekilde verilir: ${ displaystyle sol ( toplamı _ {k = 2} ^ {n-1} k (k-1) { binom {n-1} {k}} sağ) + (n-1) = (n -1) (n-2) 2 ^ {n-3} + (n-1)}$

ve ikinci aşamada her birinin oluşum sayısı ${ displaystyle toplamı _ {k = 2} ^ {n-1} k = {n (n-1) bölü 2} -1}$

Uzay: ${ displaystyle sol ( toplamı _ {k = 2} ^ {n-1} k { binom {n-1} {k}} sağ) + (n-1) = (n-1) 2 ^ {n-2}}$

Alan karmaşıklığı, boyut alt kümeleri için minimum maliyetlerin hesaplanmasının farkına vararak biraz iyileştirilebilir. s yalnızca boyutun alt kümelerini gerektirir s-1.

Yalnızca boyutun alt kümelerini depolayarak s-1 ve s algoritmanın herhangi bir noktasında uzay karmaşıklığı şu şekilde azalır: ${ displaystyle max _ {2 leq s$

İlgili algoritmalar

TSP'yi çözmek için kesin algoritma

Dinamik Programlamanın yanı sıra, Doğrusal programlama ve Dallara bağlı algoritma, TSP'yi çözebilen hassas algoritmalardır. Doğrusal programlama, kesme düzlemi yöntemi için geçerlidir. Tamsayılı programlama Örneğin, modeldeki iki kısıtla oluşturulan DP'yi çözme ve ardından optimum bir çözüme kademeli olarak yakınsamak için eşitsizlik kısıtlaması ekleyerek kesme düzlemini arama. İnsanlar bir kesme düzlemi bulmak için bu yöntemi uyguladıklarında, genellikle deneyime bağlıdırlar. Dolayısıyla bu yöntem nadiren genel bir yöntem olarak kabul edilir.

Dallara bağlı algoritma, büyük ölçekli problemi çözmek için iyi olmasa da, yaygın olarak kullanılan bir arama algoritmasıdır. Arama sürecini etkili kısıtlayıcı sınır yoluyla kontrol eder, böylece mümkün olan en kısa sürede en uygun çözümü bulmak için uzay durumu ağacından en uygun çözüm dalını arayabilir. Bu algoritmanın kilit noktası, kısıtlayıcı sınırın seçimidir. Farklı kısıtlayıcı sınırlar, farklı dallara bağlı algoritmalar oluşturabilir.

TSP'yi çözmek için yaklaşık algoritma

Problemi çözmek için hassas algoritmanın uygulanması çok sınırlı olduğundan, genellikle yaklaşık algoritma veya sezgisel algoritma kullanırız. Algoritmanın sonucu C / C * ≤ ε ile değerlendirilebilir. C, yaklaşık algoritmadan üretilen toplam seyahat mesafesidir; C * en uygun seyahat mesafesidir; ε, yaklaşık çözümün toplam seyahat mesafesinin en kötü koşullarda optimal çözüme oranının üst sınırıdır. Ε> 1.0 değeri. 1.0'a ne kadar yakınsa, algoritma o kadar iyidir. Bu algoritmalar şunları içerir: İnterpolasyon algoritması, En yakın komşu algoritması, Clark & Wright algoritması, Çift kapsamlı ağaç algoritması, Christofides algoritması, Hibrit algoritma, Olasılıksal algoritma.

Referanslar

^ "Gezgin satıcı sorununun dinamik programlama tedavisi", Richard Bellman, Doç. Hesaplama Mach. 9. 1962.
^ 'Sorunları sıralamak için dinamik bir programlama yaklaşımı', Michael Held ve Richard M. Karp, Endüstriyel ve Uygulamalı Matematik Derneği Dergisi 1:10. 1962
^ http://www.cs.man.ac.uk/~david/algorithms/graphs.pdf
^ http://www.mafy.lut.fi/study/DiscreteOpt/tspdp.pdf
^ http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf^{[kalıcı ölü bağlantı ]}
^ Gutin, Gregory ve Abraham P. Punnen, editörler. Gezgin satıcı problemi ve çeşitleri. Cilt 12. Springer, 2002.

[1] "Gezgin satıcı sorununun dinamik programlama tedavisi", Richard Bellman, Doç. Hesaplama Mach. 9. 1962.

[2] 'Sorunları sıralamak için dinamik bir programlama yaklaşımı', Michael Held ve Richard M. Karp, Endüstriyel ve Uygulamalı Matematik Derneği Dergisi 1:10. 1962

[3] ttp://www.cs.man.ac.uk/~david/algorithms/graphs.pdf

[4] ttp://www.mafy.lut.fi/study/DiscreteOpt/tspdp.pdf

[5] ttp://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf^{[kalıcı ölü bağlantı ]}

[6] Gutin, Gregory ve Abraham P. Punnen, editörler. Gezgin satıcı problemi ve çeşitleri. Cilt 12. Springer, 2002.

[1]

[2]

[3]

[4]

[5]

[6]