Seyahat eden satıcı sorunu - Travelling salesman problem

Seyahat eden bir satıcı sorununun çözümü: Siyah çizgi, her kırmızı noktayı birbirine bağlayan mümkün olan en kısa döngüyü gösterir.

seyyar satıcı sorunu (ayrıca seyyar satıcı sorunu^[1] veya TSP) şu soruyu sorar: "Bir şehir listesi ve her bir şehir çifti arasındaki mesafeler göz önüne alındığında, her şehri tam olarak bir kez ziyaret edip başlangıç ​​şehrine geri dönen mümkün olan en kısa rota nedir?" O bir NP-zor problem kombinatoryal optimizasyon, önemli teorik bilgisayar bilimi ve yöneylem araştırması.

seyahat eden alıcı sorunu ve araç yönlendirme sorunu her ikisi de TSP'nin genellemeleridir.

İçinde hesaplama karmaşıklığı teorisi, TSP'nin karar versiyonu (bir uzunluk verildiğinde Lgörev, grafiğin en fazla turu olup olmadığına karar vermektir. L) sınıfına aittir NP tamamlandı sorunlar. Böylece, En kötü durumda çalışma süresi TSP artışları için herhangi bir algoritma için süper polinomik olarak (ama en fazla üssel olarak ) şehir sayısı ile.

Sorun ilk olarak 1930'da formüle edildi ve optimizasyonda en yoğun şekilde incelenen sorunlardan biridir. Olarak kullanılır kıyaslama birçok optimizasyon yöntemi için. Sorun hesaplama açısından zor olsa da, çoğu Sezgisel ve kesin algoritmalar Bilindiği gibi, on binlerce şehrin olduğu bazı örnekler tamamen çözülebilir ve milyonlarca şehirdeki sorunlar bile% 1'in küçük bir kısmı içinde yaklaşık olarak tahmin edilebilir.^[2]

TSP'nin en saf formülasyonunda bile çeşitli uygulamaları vardır, örneğin planlama, lojistik ve imalatı mikroçipler. Biraz değiştirilmiş, birçok alanda alt problem olarak görünmektedir. DNA dizilimi. Bu uygulamalarda kavram Kent örneğin müşterileri, lehim noktalarını veya DNA parçalarını ve kavramı temsil eder mesafe seyahat sürelerini veya maliyeti temsil eder veya benzerlik ölçüsü DNA parçaları arasında. TSP, birçok kaynağı gözlemleyen gökbilimciler teleskopu kaynaklar arasında hareket ettirmek için harcanan zamanı en aza indirmek isteyeceklerinden astronomide de ortaya çıkıyor. Çoğu uygulamada, sınırlı kaynaklar veya zaman pencereleri gibi ek kısıtlamalar getirilebilir.

Tarih

Gezgin satıcı sorununun kökenleri belirsizdir. 1832'den seyahat eden satıcılar için bir el kitabı, sorundan bahseder ve örnek turlar içerir. Almanya ve İsviçre ancak matematiksel işlem içermez.^[3]

William Rowan Hamilton

Gezici satıcı problemi, 1800'lerde İrlandalı matematikçi tarafından matematiksel olarak formüle edildi. W.R. Hamilton ve İngiliz matematikçi tarafından Thomas Kirkman. Hamilton's icosian oyunu bulmaya dayalı eğlence amaçlı bir bilmeceydi Hamilton döngüsü.^[4] TSP'nin genel formu ilk olarak matematikçiler tarafından 1930'larda Viyana'da ve Harvard'da, özellikle de Karl Menger, sorunu tanımlayan, bariz kaba kuvvet algoritmasını dikkate alan ve en yakın komşu buluşsal yönteminin iyimserliğini gözlemleyen:

İle belirtiyoruz haberci sorunu (pratikte bu soru her bir postacı tarafından, yine de birçok yolcu tarafından çözülmelidir), ikili mesafeleri bilinen sonlu sayıda nokta için noktaları birleştiren en kısa yolu bulma görevi. Tabii ki, bu problem sonlu sayıda deneme ile çözülebilir. Deneme sayısını verilen noktaların permütasyon sayısının altına itecek kurallar bilinmemektedir. Önce başlangıç ​​noktasından en yakın noktaya, sonra buna en yakın noktaya vb. Gitme kuralı, genel olarak en kısa rotayı vermez.^[5]

İlk olarak 1930'larda matematiksel olarak Merrill M. Taşkın bir okul otobüsü yönlendirme problemini çözmek isteyen.^[6]Hassler Whitney -de Princeton Üniversitesi "48 eyalet sorunu" olarak adlandırdığı soruna ilgi uyandırdı. "Gezici satıcı sorunu" ifadesini kullanan ilk yayın 1949'du. RAND Corporation tarafından rapor edildi Julia Robinson, "Hamiltonian maçında (seyyar satıcı sorunu)."^[7][8]

1950'lerde ve 1960'larda, sorun Avrupa ve ABD'deki bilim çevrelerinde giderek daha popüler hale geldi. RAND Corporation içinde Santa Monica sorunu çözme adımları için ödüller sundu.^[6] Tarafından dikkate değer katkılar yapılmıştır George Dantzig, Delbert Ray Fulkerson ve Selmer M. Johnson RAND Corporation'dan, sorunu bir tamsayı doğrusal program ve geliştirdi kesme düzlemi çözümü için yöntem. Bu yeni yöntemlerle 49 şehir örneğini bir tur kurarak ve başka hiçbir turun daha kısa olamayacağını kanıtlayarak optimalliğe çözdükleri konuya dair ufuk açıcı bir makale yazdılar. Bununla birlikte, Dantzig, Fulkerson ve Johnson, neredeyse optimal bir çözüm verildiğinde, az sayıda fazladan eşitsizlik (kesinti) ekleyerek optimalliği bulabileceğimizi veya optimumluğu kanıtlayabileceğimizi tahmin ettiler. Bu fikri, ilk 49 şehir problemini bir dizgi modeli kullanarak çözmek için kullandılar. 49 şehir sorununa çözüm bulmak için yalnızca 26 kesintiye ihtiyaç duyduklarını gördüler. Bu makale TSP problemlerine algoritmik bir yaklaşım vermezken, içinde yatan fikirler daha sonra TSP için kesin çözüm yöntemleri oluşturmak için vazgeçilmezdi, ancak bu kesintileri oluştururken algoritmik bir yaklaşım bulmak 15 yıl alacaktı.^[6] Dantzig, Fulkerson ve Johnson, uçak kesme yöntemlerinin yanı sıra dal ve sınır algoritmalar belki de ilk kez.^[6]

1959'da Jillian Beardwood, J.H. Halton ve John Hammersley Cambridge Philosophical Society dergisinde "Birçok Noktadan Geçen En Kısa Yol" başlıklı bir makale yayınladı.^[9] Beardwood-Halton-Hammersley teoremi, seyyar satıcı problemine pratik bir çözüm sağlar. Yazarlar, bir ev veya ofiste başlayan ve başlangıca dönmeden önce belirli sayıda yeri ziyaret eden bir satış elemanı için en kısa yolun uzunluğunu belirlemek için asimtotik bir formül türetmişlerdir.

Sonraki yıllarda, sorun birçok araştırmacı tarafından incelendi. matematik, bilgisayar Bilimi, kimya, fizik ve diğer bilimler. Ancak 1960'larda, optimal çözümler aramak yerine, uzunluğu ideal uzunluğun bir katı ile kanıtlanabilir şekilde sınırlanan bir çözüm üretecek ve bunu yaparken problem için daha düşük sınırlar yaratacak yeni bir yaklaşım yaratıldı; bunlar daha sonra dal ve sınır yaklaşımlarıyla kullanılabilir. Bunu yapmanın bir yöntemi, bir az yer kaplayan ağaç grafiğin tüm kenarlarını ikiye katlayın ve en uygun tur uzunluğunun minimum kapsayan ağacın ağırlığının en fazla iki katı olduğu sınırını oluşturur.^[6]

1976'da Christofides ve Serdyukov birbirinden bağımsız olarak bu yönde büyük bir ilerleme kaydetti:^[10] Christofides-Serdyukov algoritması en kötü durumda, optimal çözümden en fazla 1,5 kat daha uzun bir çözüm sağlar. Algoritma çok basit ve hızlı olduğu için, çoğu kişi, neredeyse optimal bir çözüm yöntemine yol açacağını umuyordu. Bu, en kötü durum senaryosuna sahip yöntem olarak kalır. Bununla birlikte, sorunun oldukça genel bir özel durumu için 2011'de küçük bir farkla yenildi.^[11]

Richard M. Karp 1972'de gösterdi ki Hamilton döngüsü sorun şuydu NP tamamlandı anlamına gelen NP sertliği TSP. Bu, optimum turları bulmanın görünen hesaplama zorluğu için matematiksel bir açıklama sağladı.

1970'lerin sonlarında ve 1980'de, Grötschel, Padberg, Rinaldi ve diğerlerinin 2,392'ye kadar şehirdeki örnekleri kesici uçaklar kullanarak tam olarak çözmeyi başardığı büyük ilerleme kaydedildi. dal ve sınır.

1990'larda, Applegate, Bixby, Chvátal, ve pişirmek programı geliştirdi Concorde son zamanlarda pek çok rekor çözümünde kullanılmış. Gerhard Reinelt, sonuçları karşılaştırmak için birçok araştırma grubu tarafından kullanılan farklı zorluk derecelerine sahip kıyaslama örneklerinden oluşan bir koleksiyon olan TSPLIB'yi 1991 yılında yayınladı. 2006 yılında Cook ve diğerleri, şu anda çözülmüş en büyük TSPLIB örneği olan bir mikroçip yerleşim problemi tarafından verilen 85.900 şehir örneği üzerinden optimal bir tur hesapladı. Milyonlarca şehir içeren diğer pek çok örnek için, optimum turun% 2–3'ü dahilinde olması garanti edilen çözümler bulunabilir.^[12]

2020'de biraz iyileştirilmiş bir yaklaşım algoritması geliştirildi.^[13][14]

Açıklama

Bir grafik problemi olarak

Dört şehirli simetrik TSP

TSP, bir yönsüz ağırlıklı grafik, öyle ki şehirler grafiğin köşeler yollar grafiğin kenarlar ve bir yolun mesafesi kenarın ağırlığıdır. Belirli bir hızda başlayan ve biten bir minimizasyon problemidir. tepe birbirimizi ziyaret ettikten sonra tepe tam olarak bir kez. Genellikle model bir tam grafik (yani, her köşe çifti bir kenarla bağlanır). İki şehir arasında herhangi bir yol yoksa, rastgele uzun bir kenar eklemek, grafiği optimum turu etkilemeden tamamlayacaktır.

Asimetrik ve simetrik

İçinde simetrik TSPiki şehir arasındaki mesafe, her bir zıt yönde aynıdır ve bir yönsüz grafik. Bu simetri, olası çözümlerin sayısını yarıya indirir. İçinde asimetrik TSPyollar her iki yönde de olmayabilir veya mesafeler farklı olabilir ve bir Yönlendirilmiş grafik. Trafik çarpışmaları, tek yönlü sokaklar ve farklı kalkış ve varış ücretleri olan şehirler için uçak biletleri, bu simetrinin nasıl bozulabileceğinin örnekleridir.

İlgili sorunlar

• Açısından eşdeğer bir formülasyon grafik teorisi : Verilen tam ağırlıklı grafik (köşelerin şehirleri, kenarların yolları temsil ettiği ve ağırlığın o yolun maliyeti veya mesafesi olduğu yerlerde), Hamilton döngüsü en az ağırlıkla.
• Başlangıç ​​şehrine geri dönme gerekliliği, hesaplama karmaşıklığı sorunun, bakın Hamilton yolu problemi.
• Bir diğer ilgili sorun da Darboğaz gezici satıcı sorunu (darboğaz TSP): Bir Hamilton döngüsünü bulun ağırlıklı grafik en ağır olanın minimum ağırlığı ile kenar. Örneğin, büyük otobüslerle dar sokaklardan kaçınmak.^[15] Sorun, bariz ulaşım ve lojistik alanlarından ayrı olarak, oldukça pratik öneme sahiptir. Klasik bir örnek baskılı devre üretim: bir rotanın planlanması matkap PCB'de delik açmak için makine. Robotik işleme veya delme uygulamalarında, "şehirler" işlenecek parçalardır veya delinecek deliklerdir (farklı boyutlarda) ve "seyahat maliyeti" robotun yeniden takımlanması için gereken zamanı içerir (tek makineli iş sıralama problemi).^[16]
• genelleştirilmiş seyyar satıcı sorunu "Seyahat eden politikacı sorunu" olarak da bilinen, "bir veya daha fazla" şehri olan "eyaletler" ile ilgilenir ve satıcı her "eyalet" den tam olarak bir "şehri" ziyaret etmek zorundadır. Bir çözüm için bir uygulama ile karşılaşılır. stok kesme sorunu bıçak değişikliklerini en aza indirmek için. Bir diğeri de sondajla ilgilidir yarı iletken imalat, örneğin bkz. ABD Patenti 7.054.798 . Noon ve Bean, genelleştirilmiş gezici satıcı sorununun, aynı sayıda şehirle standart bir gezgin satıcı sorununa dönüştürülebileceğini, ancak değiştirilebileceğini gösterdi. mesafe matrisi.
• Sıralı sıralama problemi, şehirler arasındaki öncelik ilişkilerinin mevcut olduğu bir dizi şehri ziyaret etme problemiyle ilgilenir.
• Google'da ortak bir mülakat sorusu, verilerin veri işleme düğümleri arasında nasıl yönlendirileceğidir; yollar, verilerin aktarılması için zamana göre değişir, ancak düğümler aynı zamanda, verilerin nereye gönderileceği sorununu birleştirerek, bilgi işlem gücü ve depolama açısından da farklılık gösterir.
• seyahat eden alıcı sorunu bir dizi ürünü satın almakla yükümlü olan bir alıcıyla ilgilenir. Bu ürünleri birkaç şehirden, ancak farklı fiyatlardan satın alabilir ve tüm şehirler aynı ürünleri sunmaz. Amaç, şehirlerin bir alt kümesi arasında toplam maliyeti (seyahat maliyeti + satın alma maliyeti) en aza indiren ve gerekli tüm ürünlerin satın alınmasını sağlayan bir rota bulmaktır.

Tamsayı doğrusal programlama formülasyonları

TSP şu şekilde formüle edilebilir: tamsayı doğrusal program.^[17][18][19] Birkaç formülasyon bilinmektedir. Miller – Tucker – Zemlin (MTZ) formülasyonu ve Dantzig – Fulkerson – Johnson (DFJ) formülasyonu iki önemli formülasyondur. DFJ formülasyonu daha güçlüdür, ancak MTZ formülasyonu belirli ayarlarda hala yararlıdır.^[20][21]

Miller – Tucker – Zemlin formülasyonu

Şehirleri 1,…, sayılarla etiketleyin n ve tanımlayın:

${displaystyle x_ {ij} = {egin {case} 1 & {ext {the path from city}} i {ext {to city}} j 0 & {ext {else}} end {case}}}$

İçin ben = 1, …, n, İzin Vermek ${displaystyle u_ {i}}$ kukla değişken olun ve sonunda ${displaystyle c_ {ij}> 0}$ şehre uzaklık olmak ben şehre j. O zaman TSP aşağıdaki tamsayı doğrusal programlama problemi olarak yazılabilir:

${displaystyle {egin {align} min & sum _ {i = 1} ^ {n} sum _ {jeq i, j = 1} ^ {n} c_ {ij} x_ {ij} kolon && & x_ {ij} in { 0,1} && i, j = 1, ldots, n; & u_ {i} in mathbf {Z} && i = 2, ldots, n; & sum _ {i = 1, ieq j} ^ {n} x_ {ij } = 1 && j = 1, ldots, n; & sum _ {j = 1, jeq i} ^ {n} x_ {ij} = 1 && i = 1, ldots, n; & u_ {i} -u_ {j} + nx_ {ij} leq n-1 && 2leq ieq jleq n; & 1leq u_ {i} leq n-1 && 2leq ileq n.end {hizalı}}}$

İlk eşitlikler kümesi, her şehre tam olarak bir başka şehirden ulaşılmasını gerektirir ve ikinci eşitlik kümesi, her şehirden tam olarak başka bir şehre gitmeyi gerektirir. Son kısıtlamalar, tüm şehirleri kapsayan yalnızca tek bir tur olduğunu ve yalnızca toplu olarak tüm şehirleri kapsayan iki veya daha fazla ayrık tur olmadığını zorunlu kılar. Bunu kanıtlamak için, aşağıda (1) her uygun çözümün yalnızca bir kapalı şehir dizisi içerdiği ve (2) tüm şehirleri kapsayan her bir tur için, kukla değişkenler için değerler olduğu gösterilmiştir. ${displaystyle u_ {i}}$ kısıtlamaları karşılayan. (Kukla değişkenler tur sırasını gösterir, öyle ki ${displaystyle u_ {i}$ şehir ima eder ${displaystyle i}$ şehirden önce ziyaret edildi ${displaystyle j}$. Bu, artırılarak gerçekleştirilebilir ${displaystyle u_ {i}}$ her ziyaret edildiğinde.)

Her uygulanabilir çözümün yalnızca bir kapalı şehir dizisi içerdiğini kanıtlamak için, uygulanabilir bir çözümdeki her alt turun Şehir 1'den geçtiğini göstermek yeterlidir (eşitliklerin böyle yalnızca bir tur olmasını sağladığına dikkat edin). Karşılık gelen tüm eşitsizlikleri toplarsak ${displaystyle x_ {ij} = 1}$ herhangi bir alt tur için k Şehir 1'den geçmeyen adımlar, şunu elde ederiz:

${displaystyle nkleq (n-1) k,}$

bu bir çelişkidir.

Şimdi, tüm şehirleri kapsayan her bir tur için, kukla değişkenler için değerler olduğu gösterilmelidir. ${displaystyle u_ {i}}$ kısıtlamaları karşılayan.

Genelliği kaybetmeden, turu şehir 1'de başlayan (ve biten) olarak tanımlayın. ${displaystyle u_ {i} = t}$ eğer şehir ben adım adım ziyaret edilir t (ben, t = 1, 2, ..., n). Sonra

${displaystyle u_ {i} -u_ {j} leq n-1,}$

dan beri ${displaystyle u_ {i}}$ daha büyük olamaz n ve ${displaystyle u_ {j}}$ 1'den az olamaz; bu nedenle kısıtlamalar ne zaman olursa olsun ${displaystyle x_ {ij} = 0.}$ İçin ${displaystyle x_ {ij} = 1}$, sahibiz:

${displaystyle u_ {i} -u_ {j} + nx_ {ij} = (t) - (t + 1) + n = n-1,}$

kısıtlamayı yerine getiriyor.

Dantzig – Fulkerson – Johnson formülasyonu

Şehirleri 1,…, sayılarla etiketleyin n ve tanımlayın:

${displaystyle x_ {ij} = {egin {case} 1 & {ext {the path from city}} i {ext {to city}} j 0 & {ext {else}} end {case}}}$

Al ${displaystyle c_ {ij}> 0}$ şehre uzaklık olmak ben şehre j. O zaman TSP aşağıdaki tamsayı doğrusal programlama problemi olarak yazılabilir:

${displaystyle {egin {align} min & sum _ {i = 1} ^ {n} sum _ {jeq i, j = 1} ^ {n} c_ {ij} x_ {ij} kolon && & x_ {ij} in { 0,1} && i, j = 1, ldots, n; & sum _ {i = 1, ieq j} ^ {n} x_ {ij} = 1 && j = 1, ldots, n; & sum _ {j = 1, jeq i} ^ {n} x_ {ij} = 1 && i = 1, ldots, n; & sum _ {iin Q} {sum _ {jeq i, jin Q} {x_ {ij}}} leq | Q | -1 && forall Qsubsetneq {1, ldots, n}, | Q | geq 2 end {hizalı}}}$

DFJ formülasyonunun son kısıtlaması, başlangıç ​​olmayan köşeler arasında alt turların olmamasını sağlar, bu nedenle geri döndürülen çözüm, daha küçük turların birliği değil, tek bir turdur. Bu, üstel sayıdaki olası kısıtlamalara yol açtığından, pratikte şu şekilde çözülür: gecikmiş sütun üretimi.

Bir çözüm hesaplanıyor

NP-zor sorunlar için geleneksel saldırı hatları şunlardır:

• Geliştirme kesin algoritmalar, yalnızca küçük sorun boyutları için oldukça hızlı çalışır.
• "Suboptimal" geliştirme veya sezgisel algoritmalar yani makul bir sürede yaklaşık çözümler sunan algoritmalar.
• Problem için daha iyi veya kesin sezgisel yöntemlerin mümkün olduğu özel durumlar ("alt problemler") bulma.

Kesin algoritmalar

En doğrudan çözüm, hepsini denemek olacaktır. permütasyonlar (sıralı kombinasyonlar) ve hangisinin en ucuz olduğunu görün (kullanarak kaba kuvvet arama ). Bu yaklaşım için çalışma süresi, bir polinom faktörü içinde yer alır. ${displaystyle O (n!)}$, faktöryel şehir sayısının artması nedeniyle bu çözüm sadece 20 şehir için bile pratik değildir.

En eski uygulamalarından biri dinamik program ... Held – Karp algoritması sorunu zamanında çözen ${displaystyle O (n ^ {2} 2 ^ {n})}$.^[22] Bu sınıra, dinamik programlama yaklaşımından önceki bir girişimde Dışlama-Dahil Etme ile de ulaşılmıştır.

Kaba kuvvet arama kullanarak 7 şehirli simetrik bir TSP'ye çözüm. Not: Permütasyon sayısı: (7−1)! / 2 = 360

Bu zaman sınırlarını iyileştirmek zor görünüyor. Örneğin, bir kesin algoritma zamanında çalışan TSP için ${displaystyle O (1,9999 ^ {n})}$ var.^[23]

Diğer yaklaşımlar şunları içerir:

• Çeşitli dal ve sınır 40–60 şehir içeren TSP'leri işlemek için kullanılabilen algoritmalar.

Basit bir Dal ve sınır algoritması kullanan 7 şehirli bir TSP'nin çözümü. Not: Permütasyon sayısı, Brute force aramasından çok daha azdır.

• Anımsatan teknikleri kullanan aşamalı iyileştirme algoritmaları doğrusal programlama. 200 şehre kadar iyi çalışır.
• Uygulamaları dal ve sınır ve soruna özel kesim oluşturma (dal ve kes^[24]); bu, büyük örnekleri çözmek için tercih edilen yöntemdir. Bu yaklaşım, 85.900 şehirli bir örneği çözerek mevcut rekoru elinde tutuyor, bkz. Applegate vd. (2006).

TSPLIB'den 15.112 Alman şehri için kesin bir çözüm 2001 yılında kesme düzlemi yöntemi öneren George Dantzig, Ray Fulkerson, ve Selmer M. Johnson 1954'te doğrusal programlama. Hesaplamalar, adresinde bulunan 110 işlemciden oluşan bir ağda gerçekleştirildi. Rice Üniversitesi ve Princeton Üniversitesi. Toplam hesaplama süresi, tek bir 500 MHz'de 22,6 yıla eşitti Alfa işlemci. Mayıs 2004'te, İsveç'teki 24.978 kasabanın tamamını ziyaret etmekle ilgili gezici satıcı sorunu çözüldü: yaklaşık 72.500 kilometre uzunluğunda bir tur bulundu ve daha kısa bir turun olmadığı kanıtlandı.^[25] Mart 2005'te, bir devre kartındaki 33.810 noktayı ziyaret eden gezgin satıcı sorunu, Concorde TSP Çözücü: 66.048.945 birim uzunluğunda bir tur bulundu ve daha kısa bir turun olmadığı kanıtlandı. Hesaplama yaklaşık olarak 15,7 CPU-yıl sürmüştür (Cook ve diğerleri 2006). Nisan 2006'da 85.900 puanlık bir örnek, kullanılarak çözüldü Concorde TSP Çözücü136 CPU yılını aşıyor, bkz. Applegate vd. (2006).

Sezgisel ve yaklaşık algoritmalar

Çeşitli Sezgisel ve yaklaşım algoritmaları Hızlı bir şekilde iyi çözümler üreten, tasarlandı. Bunlar şunları içerir: Çok parçalı algoritma. Modern yöntemler, son derece büyük problemlere (milyonlarca şehir) makul bir süre içinde çözümler bulabilir ve bu da yüksek olasılıkla optimum çözümden sadece% 2-3 uzakta olur.^[12]

Çeşitli sezgisel tarama kategorileri tanınır.

Yapıcı sezgisel yöntemler

7 şehirli bir TSP için En Yakın Komşu algoritması. Başlangıç ​​noktası değiştikçe çözüm de değişir

en yakın komşu (NN) algoritması (bir Açgözlü algoritma ) satıcının bir sonraki hamlesi olarak en yakın ziyaret edilmemiş şehri seçmesini sağlar. Bu algoritma hızlı bir şekilde etkili bir kısa yol sağlar. Bir düzleme rastgele dağıtılan N şehir için, algoritma ortalama olarak mümkün olan en kısa yoldan% 25 daha uzun bir yol verir.^[26] Bununla birlikte, NN algoritmasını en kötü yolu veren özel olarak düzenlenmiş birçok şehir dağıtımı vardır.^[27] Bu hem asimetrik hem de simetrik TSP'ler için geçerlidir.^[28] Rosenkrantz vd.^[29] NN algoritmasının yaklaşım faktörüne sahip olduğunu gösterdi ${displaystyle Theta (günlük | V |)}$ üçgen eşitsizliğini tatmin eden örnekler için. En yakın ziyaret edilmemiş şehirlerin bir grubunu (fragmanını) birbirine bağlayan En Yakın Parça (NF) operatörü adı verilen bir NN algoritması varyasyonu, ardışık yinelemelerle daha kısa rotalar bulabilir.^[30] NF operatörü, yalnızca daha iyi çözümlerin kabul edildiği elitist bir modelde daha fazla iyileştirme için NN algoritmasıyla elde edilen bir başlangıç ​​çözümüne de uygulanabilir.

bitonik tur bir dizi nokta minimum çevre tek tonlu çokgen köşeleri noktaları olan; verimli bir şekilde hesaplanabilir dinamik program.

Bir diğeri yapıcı sezgisel, Match Twice ve Stitch (MTS), iki ardışık gerçekleştirir eşleşmeler, ikinci eşleşmenin, bir dizi döngü elde etmek için ilk eşleşmenin tüm kenarları silindikten sonra yürütüldüğü yer. Döngüler daha sonra son turu oluşturmak için dikilir.^[31]

Christofides ve Serdyukov'un Algoritması

Bir eşleşme oluşturma

Yukarıdaki eşleşmeyle oluşturulan grafikte bir kısayol sezgisel kullanarak

Christofides ve Serdyukov'un algoritması benzer bir taslağı takip eder, ancak minimum yayılma ağacını başka bir problemin çözümü olan minimum ağırlık ile birleştirir. mükemmel eşleşme. Bu, optimumun en fazla 1,5 katı olan bir TSP turu sağlar. İlklerden biriydi yaklaşım algoritmaları ve çözülemeyen problemlere pratik bir yaklaşım olarak yaklaşım algoritmalarına dikkat çekmekten kısmen sorumluydu. Nitekim, "algoritma" terimi genel olarak yaklaştırma algoritmalarına genişletilmemiştir; Christofides algoritmasına başlangıçta Christofides buluşsal yöntemi deniyordu.^[10]

Bu algoritma, minimum kapsama ağacının maliyetinin iki katına çıkarılmasından kaynaklanan TSP'nin LB'sini iyileştirmeye yardımcı olan grafik teorisinin bir sonucunu kullanarak olaylara farklı şekilde bakar. Verilen bir Euler grafiği bulabiliriz Euler turu içinde ${displaystyle O (n)}$ zaman.^[6] Öyleyse, bir TSP'den şehirlerin köşeleri olduğu bir Eulerian grafiğimiz olsaydı, bir TSP çözümü bulmak için bir Euler turu bulmak için böyle bir yöntemi kullanabileceğimizi kolayca görebiliriz. Tarafından üçgen eşitsizlik TSP turunun Euler turundan daha uzun olamayacağını biliyoruz ve bu nedenle TSP için bir LB'ye sahibiz. Böyle bir yöntem aşağıda açıklanmaktadır.

1. Problem için minimum bir yayılma ağacı bulun
2. Bir Euler grafiği oluşturmak için her kenar için kopyalar oluşturun
3. Bu grafik için bir Euler turu bulun
4. TSP'ye dönüştürün: Bir şehir iki kez ziyaret edilirse, turda bundan önce şehirden bundan sonrasına bir kısayol oluşturun.

Alt sınırı iyileştirmek için, bir Euler grafiği oluşturmanın daha iyi bir yolu gereklidir. Üçgen eşitsizliğe göre, en iyi Eulerian grafiği, en iyi seyyar satıcı turu ile aynı maliyete sahip olmalıdır, bu nedenle en uygun Euler grafiklerini bulmak en az TSP kadar zordur. Bunu yapmanın bir yolu minimum ağırlıktır eşleştirme algoritmalarını kullanarak ${displaystyle O (n ^ {3})}$.^[6]

Bir Euler grafiğine bir grafik yapmak, minimum yayılma ağacıyla başlar. O zaman tek sıranın tüm köşeleri eşit olmalıdır. Bu nedenle, her tek dereceli tepe noktasının sırasını birer birer artıran tek dereceli köşeler için bir eşleştirme eklenmelidir.^[6] Bu, bize her köşe noktasının eşit düzende olduğu ve dolayısıyla Euler olduğu bir grafik bırakır. Yukarıdaki yöntemin uyarlanması, Christofides ve Serdyukov'un algoritmasını verir.

1. Problem için minimum bir yayılma ağacı bulun
2. Tek sıra şehirler kümesiyle problem için bir eşleştirme oluşturun.
3. Bu grafik için bir Euler turu bulun
4. Kısayolları kullanarak TSP'ye dönüştürün.

İkili değişim

2 seçenekli yineleme örneği

İkili değişim veya 2 seçenekli teknik, iki kenarın yinelemeli olarak kaldırılmasını ve bunları, kenar kaldırma işlemiyle oluşturulan parçaları yeni ve daha kısa bir turda yeniden birleştiren iki farklı kenarla değiştirmeyi içerir. Benzer şekilde, 3 seçenekli teknik 3 kenarı kaldırır ve daha kısa bir tur oluşturmak için bunları yeniden birleştirir. Bunlar, k-opt yöntemi. Etiket Lin-Kernighan 2 seçenekli için sıklıkla duyulan bir yanlış isimdir. Lin – Kernighan aslında daha genel k-opt yöntemidir.

Öklid örnekleri için, 2 seçenekli buluşsal yöntem ortalama olarak Christofides'in algoritmasından yaklaşık% 5 daha iyi çözümler sunar. Bir ilk çözümle başlarsak, Açgözlü algoritma, ortalama hamle sayısı yeniden büyük ölçüde azalır ve ${displaystyle O (n)}$. Ancak rastgele başlangıçlar için ortalama hamle sayısı ${displaystyle O (nlog (n))}$. Bununla birlikte, bu boyutta küçük bir artış olsa da, küçük problemler için başlangıçtaki hamle sayısı, açgözlü bir buluşsal yöntemle yapılana kıyasla rastgele bir başlangıç ​​için 10 kat daha büyüktür. Bunun nedeni, bu tür 2-seçenekli buluşsal yöntemlerin, geçişler gibi bir çözümün 'kötü' kısımlarını kullanmasıdır. Bu tür sezgisel yöntemler genellikle Araç yönlendirme sorunu rota çözümlerini yeniden optimize etmek için sezgisel yöntemler.^[26]

k-opt sezgisel veya Lin – Kernighan buluşsal yöntemi

Lin – Kernighan buluşsal yöntemi, özel bir durumdur. V-opt veya değişken-opt tekniği. Aşağıdaki adımları içerir:

1. Bir tur verildiğinde, sil k karşılıklı ayrık kenarlar.
2. Kalan parçaları bir turda yeniden birleştirin, hiçbir ayrık alt tur bırakmayın (yani, bir parçanın uç noktalarını birbirine bağlamayın). Bu, aslında söz konusu TSP'yi çok daha basit bir soruna dönüştürür.
3. Her bir parçanın uç noktası bağlanabilir 2k − 2 diğer olasılıklar: 2k toplam parça uç noktaları mevcutsa, söz konusu parçanın iki uç noktasına izin verilmez. Böyle kısıtlı bir 2k-city TSP, daha sonra, orijinal fragmanların en düşük maliyetli rekombinasyonunu bulmak için kaba kuvvet yöntemleriyle çözülebilir.

En popüler olanı k-opt yöntemleri, Shen Lin tarafından tanıtıldığı üzere 3-opt. Bell Laboratuvarları 1965'te. Özel bir 3-opt durumu, kenarların ayrık olmadığı durumdur (kenarlardan ikisi birbirine bitişiktir). Uygulamada, genel 3-seçeneğin kombinatoryal maliyeti olmaksızın 2-seçime göre önemli iyileştirme elde etmek, 3-değişikliğin çıkarılan kenarlardan ikisinin bitişik olduğu bu özel alt kümeyle sınırlandırılması ile mümkündür. Bu sözde iki buçuk seçenek, tipik olarak, hem elde edilen turların kalitesi hem de bu turları gerçekleştirmek için gereken süre açısından, 2 ve 3 seçenek arasında kabaca ortasına düşer.

V-opt sezgisel

Değişken-tercih yöntemi ile ilgilidir ve k-opt yöntemi. Oysa k-opt yöntemleri sabit bir sayıyı kaldırır (k) Orijinal turdan kenarlar, değişken-opt yöntemleri kaldırılacak kenar kümesinin boyutunu sabitlemez. Bunun yerine, arama süreci devam ederken seti büyütürler. Bu ailede en iyi bilinen yöntem Lin – Kernighan yöntemidir (yukarıda 2-opt için yanlış bir isim olarak bahsedilmiştir). Shen Lin ve Brian Kernighan yöntemini ilk olarak 1972'de yayınladı ve yaklaşık yirmi yıldır seyahat eden satıcı sorunlarını çözmek için en güvenilir buluşsal yöntemdi. David Johnson ve araştırma ekibi tarafından 1980'lerin sonlarında Bell Laboratuvarlarında daha gelişmiş değişken-opt yöntemleri geliştirildi. Bu yöntemler (bazen Lin – Kernighan – Johnson ) Lin – Kernighan yöntemini temel alarak tabu araması ve evrimsel hesaplama. Temel Lin – Kernighan tekniği, en az 3 seçenekli olması garantili sonuçlar verir. Lin – Kernighan – Johnson yöntemleri bir Lin – Kernighan turu hesaplar ve ardından turu, en az dört kenarı ortadan kaldıran ve turu farklı bir şekilde yeniden birleştiren bir mutasyon olarak tanımlanan şeyle tedirgin eder, sonra V-yeni turu açmak. Mutasyon genellikle turu yerel minimum Lin – Kernighan tarafından tanımlanmıştır. V-opt yöntemleri, yaygın olarak problem için en güçlü buluşsal yöntemler olarak kabul edilir ve Hamilton Döngü Problemi ve diğer sezgisel yöntemlerin başarısız olduğu diğer metrik olmayan TSP'ler gibi özel durumları ele alabilir. Lin – Kernighan – Johnson, uzun yıllar boyunca, optimal bir çözümün bilindiği ve yöntemin denendiği tüm diğer TSP'ler için en iyi bilinen çözümleri belirlediği tüm TSP'ler için en uygun çözümleri belirlemişti.

Rastgele iyileştirme

Optimize edilmiş Markov zinciri Yerel arama sezgisel alt algoritmalarını kullanan algoritmalar, 700 ila 800 şehir için optimum rotaya oldukça yakın bir rota bulabilir.

TSP, aşağıdaki gibi kombinasyonel optimizasyon için tasarlanmış birçok genel buluşsal yöntem için bir mihenk taşıdır. genetik algoritmalar, benzetimli tavlama, tabu araması, karınca kolonisi optimizasyonu, nehir oluşum dinamikleri (görmek Sürü zekası ) ve çapraz entropi yöntemi.

Karınca kolonisi optimizasyonu

Yapay zeka araştırmacı Marco Dorigo 1993'te TSP'ye sezgisel olarak "iyi çözümler" üretme yöntemini bir karınca kolonisinin simülasyonu aranan ACS (karınca kolonisi sistemi).^[32] Yiyecek kaynakları ile yuvaları arasında kısa yollar bulmak için gerçek karıncalarda gözlemlenen davranışları modeller. ortaya çıkan Her karıncanın takip etme tercihinden kaynaklanan davranış iz feromonları diğer karıncalar tarafından bırakılır.

ACS, haritadaki birçok olası rotayı keşfetmek için çok sayıda sanal karınca ajanı gönderir. Her karınca, olasılıksal olarak, şehre olan mesafeyi ve şehrin kenarında biriken sanal feromon miktarını birleştiren bir buluşsal yönteme dayalı olarak ziyaret edilecek bir sonraki şehri seçer. Karıncalar, bir turu tamamlayana kadar, geçtikleri her kenara feromon bırakarak keşfederler. Bu noktada en kısa turu tamamlayan karınca, tüm tur rotası boyunca sanal feromon bırakır (genel iz güncelleme). Yatırılan feromon miktarı, tur uzunluğu ile ters orantılıdır: tur ne kadar kısa olursa, o kadar fazla para yatırır.

7 şehirli bir TSP için karınca kolonisi optimizasyon algoritması: Feromon haritasındaki kırmızı ve kalın çizgiler daha fazla feromon varlığını gösterir

Özel durumlar

Metrik

İçinde metrik TSP, Ayrıca şöyle bilinir delta-TSP veya Δ-TSP, şehirlerarası mesafeler, üçgen eşitsizliği.

TSP'nin çok doğal bir kısıtlaması, şehirler arasındaki mesafelerin bir metrik tatmin etmek üçgen eşitsizliği; bu doğrudan bağlantıdır Bir -e B hiçbir zaman ara yoldan geçen rotadan daha uzak değildir C:

${displaystyle d_ {AB} leq d_ {AC} + d_ {CB}}$.

Kenar genişler ve ardından bir metrik köşeler kümesinde. Şehirler uçaktaki noktalar olarak görüldüğünde, birçok doğal mesafe fonksiyonları metriklerdir ve TSP'nin pek çok doğal örneği bu kısıtlamayı karşılar.

Aşağıda, çeşitli metrikler için bazı metrik TSP örnekleri verilmiştir.

• Öklid TSP'sinde (aşağıya bakınız) iki şehir arasındaki mesafe, Öklid mesafesi karşılık gelen noktalar arasında.
• Doğrusal TSP'de iki şehir arasındaki mesafe, iki şehir arasındaki farkların mutlak değerlerinin toplamıdır. x- ve y- koordinatlar. Bu metriğe genellikle Manhattan mesafesi veya şehir bloğu metriği.
• İçinde maksimum ölçü, iki nokta arasındaki mesafe, bunların arasındaki farkların mutlak değerlerinin maksimumudur. x- ve y- koordinatlar.

Son iki ölçüm, örneğin, belirli bir delik kümesini bir baskılı devre kartı. Manhattan metriği, önce bir koordinatı, sonra diğerini ayarlayan bir makineye karşılık gelir, bu nedenle yeni bir noktaya geçme süresi her iki hareketin toplamıdır. Maksimum metrik, her iki koordinatı aynı anda ayarlayan bir makineye karşılık gelir, bu nedenle yeni bir noktaya geçme süresi iki hareketten daha yavaştır.

TSP, tanımında şehirlerin iki kez ziyaret edilmesine izin vermez, ancak birçok uygulama bu kısıtlamaya ihtiyaç duymaz. Bu gibi durumlarda, simetrik, metrik olmayan bir örnek, metrik olana indirgenebilir. Bu, orijinal grafiği şehirler arası mesafenin gösterildiği eksiksiz bir grafikle değiştirir. ${displaystyle d_ {AB}}$ ile değiştirilir en kısa yol arasında Bir ve B orijinal grafikte.

Öklid

Giriş numaraları rastgele gerçek sayılar olabildiğinde, Öklid TSP özel bir metrik TSP durumudur, çünkü bir düzlemdeki mesafeler üçgen eşitsizliğine uymaktadır. Girdi sayılarının tam sayı olması gerektiğinde, tur uzunluklarının karşılaştırılması, kareköklerin toplamlarının karşılaştırılmasını içerir.

Genel TSP gibi, Öklid TSP de her iki durumda da NP-zordur. Rasyonel koordinatlar ve ayrıklaştırılmış metrikle (bir tam sayıya yuvarlanmış mesafeler), sorun NP-tamamlandı.^[33] Rasyonel koordinatlar ve gerçek Öklid metriği ile Öklid TSP'nin Sayım Hiyerarşisinde olduğu bilinmektedir,^[34] bir PSPACE alt sınıfı. Rastgele gerçek koordinatlarla Öklid TSP'si bu sınıflarda olamaz, çünkü sayılamayacak kadar çok sayıda olası girdi vardır. Bununla birlikte, Öklid TSP muhtemelen yaklaşım için en kolay versiyondur.^[35] Örneğin, bir Öklid TSP örneğiyle ilişkili grafiğin minimum yayılma ağacı bir Öklid asgari kapsayan ağaç ve dolayısıyla beklenen O (n günlük n) zaman için n noktalar (kenar sayısından önemli ölçüde daha az). Bu, yukarıdaki üçgen eşitsizliği olan TSP için basit 2-yaklaşım algoritmasının daha hızlı çalışmasını sağlar.

Genel olarak, herhangi biri için c > 0, nerede d Öklid uzayındaki boyutların sayısıdır, en fazla uzunluk turu bulan bir polinom-zaman algoritması vardır (1 + 1 /c) TSP'nin geometrik örnekleri için en uygun olanın katı

${displaystyle Oleft (n (log n) ^ {(O (c {sqrt {d}})) ^ {d-1}} ight),}$

zaman; buna denir polinom zaman yaklaşım şeması (PTAS).^[36] Sanjeev Arora ve Joseph S. B. Mitchell ödüllendirildi Gödel Ödülü 2010 yılında Öklid TSP için bir PTAS'yi eşzamanlı keşiflerinden dolayı.

Uygulamada, daha zayıf garantilere sahip daha basit buluşsal yöntemler kullanılmaya devam etmektedir.

Asimetrik

Çoğu durumda, TSP ağındaki iki düğüm arasındaki mesafe her iki yönde de aynıdır. Mesafenin olduğu durum Bir -e B mesafeye eşit değildir B -e Bir asimetrik TSP olarak adlandırılır. Asimetrik TSP'nin pratik bir uygulaması, cadde düzeyinde yönlendirme kullanan rota optimizasyonudur (tek yönlü sokaklar, ara yollar, otoyollar, vb. İle asimetrik yapılır).

Simetriğe dönüştürme

Asimetrik bir TSP grafiğini çözmek biraz karmaşık olabilir. Aşağıdaki, düğümler arasındaki tüm olası yol ağırlıklarını içeren 3 × 3 bir matristir Bir, B ve C. Bir seçenek, asimetrik bir boyut matrisi döndürmektir. N 2 boyutlu simetrik bir matriseN.^[37]

Asimetrik yol ağırlıkları

	Bir	B	C
Bir		1	2
B	6		3
C	5	4

Boyutu iki katına çıkarmak için, grafikteki düğümlerin her biri kopyalanır ve bir saniye oluşturulur hayalet düğüm, linked to the original node with a "ghost" edge of very low (possibly negative) weight, here denoted −w. (Alternatively, the ghost edges have weight 0, and weight w is added to all other edges.) The original 3×3 matrix shown above is visible in the bottom left and the transpose of the original in the top-right. Both copies of the matrix have had their diagonals replaced by the low-cost hop paths, represented by −w. In the new graph, no edge directly links original nodes and no edge directly links ghost nodes.

Symmetric path weights

	Bir	B	C	Bir ′	B ′	C ′
Bir				−w	6	5
B				1	−w	4
C				2	3	−w
Bir ′	−w	1	2
B ′	6	−w	3
C ′	5	4	−w

The weight −w of the "ghost" edges linking the ghost nodes to the corresponding original nodes must be low enough to ensure that all ghost edges must belong to any optimal symmetric TSP solution on the new graph (w=0 is not always low enough). As a consequence, in the optimal symmetric tour, each original node appears next to its ghost node (e.g. a possible path is ${displaystyle mathrm {A o A' o C o C' o B o B' o A} }$) and by merging the original and ghost nodes again we get an (optimal) solution of the original asymmetric problem (in our example, ${displaystyle mathrm {A o C o B o A} }$).

Analyst's problem

There is an analogous problem in geometrik ölçü teorisi which asks the following: under what conditions may a subset E nın-nin Öklid uzayı be contained in a rectifiable curve (that is, when is there a curve with finite length that visits every point in E)? Bu sorun olarak bilinir analyst's travelling salesman problem.

Path length for random sets of points in a square

Varsayalım ${displaystyle X_ {1}, ldots, X_ {n}}$ vardır ${displaystyle n}$ independent random variables with uniform distribution in the square ${displaystyle [0,1]^{2}}$ve izin ver ${displaystyle L_{n}^{ast }}$ be the shortest path length (i.e. TSP solution) for this set of points, according to the usual Öklid mesafesi. Biliniyor^[38] that, almost surely,

${displaystyle {frac {L_{n}^{*}}{sqrt {n}}}ightarrow eta qquad { ext{when }}n o infty ,}$

nerede ${displaystyle eta}$ is a positive constant that is not known explicitly. Dan beri ${displaystyle L_{n}^{*}leq 2{sqrt {n}}+2}$ (see below), it follows from bounded convergence theorem o ${displaystyle eta =lim _{n o infty }mathbb {E} [L_{n}^{*}]/{sqrt {n}}}$, hence lower and upper bounds on ${displaystyle eta}$ follow from bounds on ${displaystyle mathbb {E} [L_{n}^{*}]}$.

The almost sure limit ${displaystyle {frac {L_{n}^{*}}{sqrt {n}}}ightarrow eta }$ gibi ${displaystyle n o infty}$ may not exist if the independent locations ${displaystyle X_ {1}, ldots, X_ {n}}$ are replaced with observations from a stationary ergodic process with uniform marginals.^[39]

Üst sınır

• Birinde var ${displaystyle L^{*}leq 2{sqrt {n}}+2}$, ve bu nedenle ${displaystyle eta leq 2}$, by using a naive path which visits monotonically the points inside each of ${displaystyle {sqrt {n}}}$ slices of width ${displaystyle 1/{sqrt {n}}}$ meydanda.
• Az^[40] kanıtlanmış ${displaystyle L_{n}^{*}leq {sqrt {2n}}+1.75}$dolayısıyla ${displaystyle eta leq {sqrt {2}}}$, later improved by Karloff (1987): ${displaystyle eta leq 0.984{sqrt {2}}}$.
• Some study reported^[41] an upper bound that ${displaystyle eta leq 0.92dots }$.
• Some study reported^[42] an upper bound that ${displaystyle eta leq 0.73dots }$.

Alt sınır

• By observing that ${displaystyle mathbb {E} [L_{n}^{*}]}$ daha büyüktür ${displaystyle n}$ times the distance between ${displaystyle X_ {0}}$ and the closest point ${displaystyle X_{i}eq X_{0}}$, one gets (after a short computation)

${displaystyle mathbb {E} [L_{n}^{*}]geq { frac {1}{2}}{sqrt {n}}.}$

• A better lower bound is obtained^[38] by observing that ${displaystyle mathbb {E} [L_{n}^{*}]}$ daha büyüktür ${displaystyle { frac {1}{2}}n}$ times the sum of the distances between ${displaystyle X_ {0}}$ and the closest and second closest points ${displaystyle X_{i},X_{j}eq X_{0}}$hangi verir

${displaystyle mathbb {E} [L_{n}^{*}]geq left({ frac {1}{4}}+{ frac {3}{8}}ight){sqrt {n}}={ frac {5}{8}}{sqrt {n}},}$

• The currently^[41] best lower bound is

${displaystyle mathbb {E} [L_{n}^{*}]geq ({ frac {5}{8}}+{ frac {19}{5184}}){sqrt {n}},}$

• Held and Karp^[43] gave a polynomial-time algorithm that provides numerical lower bounds for ${displaystyle L_{n}^{*}}$, and thus for ${displaystyle eta (simeq L_{n}^{*}/{sqrt {n}})}$ which seem to be good up to more or less 1%.^[44] In particular, David S. Johnson^[45] obtained a lower bound by computer experiment:

${displaystyle L_{n}^{*}gtrsim 0.7080{sqrt {n}}+0.522,}$

where 0.522 comes from the points near square boundary which have fewer neighbours,and Christine L. Valenzuela and Antonia J. Jones^[46] obtained the following other numerical lower bound:

${displaystyle L_{n}^{*}gtrsim 0.7078{sqrt {n}}+0.551}$.

Hesaplama karmaşıklığı

The problem has been shown to be NP-zor (more precisely, it is complete for the karmaşıklık sınıfı FP^NP; görmek işlev sorunu ), ve karar problemi version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") dır-dir NP tamamlandı. bottleneck traveling salesman problem is also NP-hard. The problem remains NP-hard even for the case when the cities are in the plane with Euclidean distances, as well as in a number of other restrictive cases. Removing the condition of visiting each city "only once" does not remove the NP-hardness, since in the planar case there is an optimal tour that visits each city only once (otherwise, by the üçgen eşitsizliği, a shortcut that skips a repeated visit would not increase the tour length).

Complexity of approximation

In the general case, finding a shortest travelling salesman tour is NPO -tamamlayınız.^[47] If the distance measure is a metrik (and thus symmetric), the problem becomes APX -tamamlayınız^[48] ve the algorithm of Christofides and Serdyukov approximates it within 1.5.^[49][50][10] Bir 2020 ön baskı improves this bound to ${displaystyle 1.5-10^{-36}}$.^[51]The best known inapproximability bound is 123/122.^[52]

If the distances are restricted to 1 and 2 (but still are a metric) the approximation ratio becomes 8/7.^[53] In the asymmetric case with üçgen eşitsizliği, only logarithmic performance guarantees are known, the best current algorithm achieves performance ratio 0.814 log(n);^[54] it is an open question if a constant factor approximation exists.The best known inapproximability bound is 75/74.^[52]

The corresponding maximization problem of finding the En uzun travelling salesman tour is approximable within 63/38.^[55] If the distance function is symmetric, the longest tour can be approximated within 4/3 by a deterministic algorithm^[56] ve içinde ${displaystyle { frac {1}{25}}(33+varepsilon )}$ by a randomized algorithm.^[57]

Human and animal performance

The TSP, in particular the Öklid variant of the problem, has attracted the attention of researchers in kavramsal psikoloji. It has been observed that humans are able to produce near-optimal solutions quickly, in a close-to-linear fashion, with performance that ranges from 1% less efficient for graphs with 10-20 nodes, and 11% less efficient for graphs with 120 nodes.^[58][59] The apparent ease with which humans accurately generate near-optimal solutions to the problem has led researchers to hypothesize that humans use one or more heuristics, with the two most popular theories arguably being the convex-hull hypothesis and the crossing-avoidance heuristic.^[60][61][62] However, additional evidence suggests that human performance is quite varied, and individual differences as well as graph geometry appear to affect performance in the task.^[63][64][65] Nevertheless, results suggest that computer performance on the TSP may be improved by understanding and emulating the methods used by humans for these problems,^[66] and have also led to new insights into the mechanisms of human thought.^[67] İlk sayısı Journal of Problem Solving was devoted to the topic of human performance on TSP,^[68] and a 2011 review listed dozens of papers on the subject.^[67]

2011 yılında yapılan bir çalışma hayvan bilişi titled "Let the Pigeon Drive the Bus," named after the children's book Don't Let the Pigeon Drive the Bus!, examined spatial cognition in pigeons by studying their flight patterns between multiple feeders in a laboratory in relation to the travelling salesman problem. In the first experiment, pigeons were placed in the corner of a lab room and allowed to fly to nearby feeders containing peas. The researchers found that pigeons largely used proximity to determine which feeder they would select next. In the second experiment, the feeders were arranged in such a way that flying to the nearest feeder at every opportunity would be largely inefficient if the pigeons needed to visit every feeder. The results of the second experiment indicate that pigeons, while still favoring proximity-based solutions, "can plan several steps ahead along the route when the differences in travel costs between efficient and less efficient routes based on proximity become larger."^[69] These results are consistent with other experiments done with non-primates, which have proven that some non-primates were able to plan complex travel routes. This suggests non-primates may possess a relatively sophisticated spatial cognitive ability.

Natural computation

When presented with a spatial configuration of food sources, the hareketsiz Physarum polycephalum adapts its morphology to create an efficient path between the food sources which can also be viewed as an approximate solution to TSP.^[70] It's considered to present interesting possibilities and it has been studied in the area of doğal hesaplama.

Kıyaslamalar

For benchmarking of TSP algorithms, TSPLIB^[71] is a library of sample instances of the TSP and related problems is maintained, see the TSPLIB external reference. Many of them are lists of actual cities and layouts of actual printed circuits.

Popüler kültür

• Seyyar satıcı, by director Timothy Lanzone, is the story of four mathematicians hired by the U.S. government to solve the most elusive problem in computer-science history: P ve NP.^[72]

Ayrıca bakınız

• Kanadalı gezgin sorunu
• Kesin algoritma
• Rota inceleme sorunu (also known as "Chinese postman problem")
• Set TSP problem
• Königsberg'in Yedi Köprüsü
• Steiner gezici satıcı sorunu
• Metro Mücadelesi
• Tüp Mücadelesi
• Araç yönlendirme sorunu
• Grafik keşfi

Notlar

Referanslar

daha fazla okuma

• Adleman, Leonard (1994), "Molecular Computation of Solutions To Combinatorial Problems" (PDF), Bilim, 266 (5187): 1021–4, Bibcode:1994Sci...266.1021A, CiteSeerX  10.1.1.54.2565, doi:10.1126/science.7973651, PMID  7973651, dan arşivlendi orijinal (PDF) 6 Şubat 2005
• Babin, Gilbert; Deneault, Stéphanie; Laportey, Gilbert (2005), "Improvements to the Or-opt Heuristic for the Symmetric Traveling Salesman Problem", The Journal of the Operational Research Society, Cahiers du GERAD, Montreal: Group for Research in Decision Analysis, G-2005-02 (3): 402–407, CiteSeerX  10.1.1.89.9953, JSTOR  4622707
• Cook, William (2012). In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press. ISBN  9780691152707.
• Cook, William; Espinoza, Daniel; Goycoolea, Marcos (2007), "Computing with domino-parity inequalities for the TSP", INFORMS Bilgi İşlem Dergisi, 19 (3): 356–365, doi:10.1287/ijoc.1060.0204
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (31 Temmuz 2009). "35.2: The traveling-salesman problem". Algoritmalara Giriş (2. baskı). MIT Basın. pp. 1027–1033. ISBN  9780262033848.
• Dantzig, G. B.; Fulkerson, R.; Johnson, S. M. (1954), "Solution of a large-scale traveling salesman problem", Yöneylem Araştırması, 2 (4): 393–410, doi:10.1287 / opre.2.4.393, JSTOR  166695, S2CID  44960960
• Garey, Michael R .; Johnson, David S. (1979). "A2.3: ND22–24". Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman. s. 211–212. ISBN  9780716710448.
• Goldberg, D. E. (1989), "Genetic Algorithms in Search, Optimization & Machine Learning", Reading: Addison-Wesley, New York: Addison-Wesley, Bibcode:1989gaso.book.....G, ISBN  978-0-201-15767-3
• Gutin, G.; Yeo, A.; Zverovich, A. (15 March 2002). "Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP". Ayrık Uygulamalı Matematik. 117 (1–3): 81–86. doi:10.1016/S0166-218X(01)00195-0. ISSN  0166-218X.
• Gutin, G.; Punnen, A. P. (18 May 2007). Gezici Satıcı Problemi ve Çeşitleri. Springer ABD. ISBN  9780387444598.
• Johnson, D. S.; McGeoch, L. A. (1997), "The Traveling Salesman Problem: A Case Study in Local Optimization", in Aarts, E. H. L.; Lenstra, J. K. (eds.), Local Search in Combinatorial Optimisation (PDF), John Wiley and Sons Ltd., pp. 215–310
• Lawler, E. L .; Shmoys, D. B.; Kan, A. H. G. Rinnooy; Lenstra, J. K. (1985). The Traveling Salesman Problem. John Wiley & Sons, Incorporated. ISBN  9780471904137.
• MacGregor, J. N.; Ormerod, T. (1996), "Human performance on the traveling salesman problem" (PDF), Algı ve Psikofizik, 58 (4): 527–539, doi:10.3758/BF03213088, PMID  8934685, S2CID  38355042, dan arşivlendi orijinal (PDF) 29 Aralık 2009
• Mitchell, J. S. B. (1999), "Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems", Bilgi İşlem Üzerine SIAM Dergisi, 28 (4): 1298–1309, doi:10.1137/S0097539796309764
• Rao, S .; Smith, W. (1998), "Approximating geometrical graphs via 'spanners' and 'banyans'", Bildiriler, pp. 540–550, CiteSeerX  10.1.1.51.8676
• Rosenkrantz, Daniel J .; Stearns, Richard E .; Lewis, Philip M., II (1977). "Seyahat Eden Satıcı Sorunu İçin Çeşitli Buluşsal Yöntemlerin Analizi". Bilgi İşlem Üzerine SIAM Dergisi. SIAM (Endüstriyel ve Uygulamalı Matematik Topluluğu). 6 (5): 563–581. doi:10.1137/0206041. S2CID  14764079.
• Medvedev, Andrei; Lee, Michael; Butavicius, Marcus; Vickers, Douglas (1 Şubat 2001). "Görsel olarak sunulan Gezici Satıcı sorunları üzerindeki insan performansı". Psikolojik Araştırma. 65 (1): 34–45. doi:10.1007 / s004260000031. ISSN  1430-2772. PMID  11505612. S2CID  8986203.
• Walshaw, Chris (2000), Seyahat Eden Satıcı Sorununa Çok Düzeyli Bir Yaklaşım, CMS Press
• Walshaw, Chris (2001), Seyahat Eden Satıcı Problemi için Çok Seviyeli Lin-Kernighan-Helsgaun Algoritması, CMS Press

Dış bağlantılar

• Seyahat Eden Satıcı Sorunu -de Wayback Makinesi (17 Aralık 2013'te arşivlendi) Waterloo Üniversitesi
• TSPLIB -de Heidelberg Üniversitesi
• Seyahat Eden Satıcı Sorunu Jon McLoone tarafından Wolfram Gösteriler Projesi'nde
• TSP görselleştirme aracı