Gezgin satıcı problemi açıklaması

Bir satıcıya bir şehir listesi verin ve her birini bir kez ziyaret edip evine dönen en kısa yolculuğu sorun. Önerilen bir rotayı herkes kontrol edebilir, kötü bir rotayı herkes göz kararı iyileştirebilir; yine de her zaman en iyisini bulan hızlı bir yöntem kimse bilmiyor. Gezgin satıcı problemi zor bir problemin standart örneği hâline gelmiştir ve ona saldırmak için geliştirilen yöntemler bugün teslimatları planlıyor, devre kartlarını deliyor ve genomları birleştiriyor.

Kapalı bir turla birbirine bağlanmış şehirlerden oluşan bir harita; başlangıç şehri işaretli ve altında soluk renkte daha kısa bir tur var
Kapalı bir turla birbirine bağlanmış şehirlerden oluşan bir harita; başlangıç şehri işaretli ve altında soluk renkte daha kısa bir tur var

Problem

Bir tur her şehri tam olarak bir kez ziyaret eder ve başladığı yerde biter; uzunluğu yol boyunca kat edilen mesafelerin toplamıdır. Görev, en kısa turu bulmaktır. Buradaki sürümde mesafeler harita üzerindeki düz çizgilerdir; dolayısıyla A'dan C'ye gitmek hiçbir zaman B üzerinden gitmekten daha uzun değildir: bu, metrik gezgin satıcı problemidir. Bilmece 1930 civarında matematikçi Karl Menger tarafından tartışılmış, ad ise sonraki on yıllarda RAND Corporation'daki matematikçiler konuyu ele aldığında yaygınlaşmıştır.

Karl Menger, 1970’te. Gezgin satıcı problemini 1930 dolaylarında ele aldı.
Karl Menger, 1970’te. Gezgin satıcı problemini 1930 dolaylarında ele aldı.

Rotaların patlaması

Başlangıç şehrini sabitleyin. Bir sonraki şehir için n − 1 seçenek, ondan sonraki için n − 2 seçenek vardır ve bu böyle sürer; her tur da iki yönde dolaşılabilir, bu yüzden (n − 1)! / 2 tur vardır. 10 şehir için bu 181.440'tır, bir bilgisayar için kolaydır. 20 şehir için yaklaşık 6 × 10¹⁶'dır, 70 şehir için ise gözlemlenebilir evrendeki atom sayısını aşar. Daha hızlı bilgisayarlar pek yardımcı olmaz: her ek şehir işi yaklaşık n katına çıkarır.

NP-zor

Richard Karp 1972'de, bir çizgenin her köşeden geçen bir turu, yani bir Hamilton döngüsü olup olmadığı sorusunun, hepsi eşit derecede zor olan NP-tam problemler ailesine ait olduğunu gösterdi. Gezgin satıcı problemi bu soruyu içerir, dolayısıyla NP-zordur. Onun için hızlı bir yöntem, çizelgeleme, lojistik ve kriptografideki binlerce başka problem için de hızlı yöntemler sağlardı. Böyle bir yöntemin var olup olmadığı, Milenyum Ödülü Problemleri'nden biri olan P'ye karşı NP sorusudur.

Kesin bir yöntem: Held–Karp

1962'de Michael Held ile Richard Karp ve onlardan bağımsız olarak Richard Bellman dinamik programlamayı kullandı. Her S şehir kümesi ve S'deki her j şehri için, ev şehrinden başlayan, tam olarak S'deki şehirleri ziyaret eden ve j'de biten en kısa yolu hesaplayın. Her değer, j'siz S için bulunan değerlerden çıkar; böylece tablo küçük kümelerden büyüklere doğru doldurulur ve en kısa tur sonunda ortaya çıkar. n! yerine yaklaşık n² · 2ⁿ adım gerektirir; 30 şehir için bu, dakikalarla evrenin yaşı arasındaki farktır, ama yine de üstel olarak büyür.

Alfred Eisenstaedt’ın 1962’de fotoğrafladığı Richard Bellman. 1950’lerin başında RAND Corporation’da çalışırken dinamik programlamaya adını verdi.
Alfred Eisenstaedt’ın 1962’de fotoğrafladığı Richard Bellman. 1950’lerin başında RAND Corporation’da çalışırken dinamik programlamaya adını verdi.

Hızlı kurma kuralları

En yakın komşu her zaman henüz ziyaret edilmemiş en yakın şehre gider. Basit ve hızlıdır, ama sonunda uzun sapmalarla toplanması gereken birkaç şehri geride bırakma eğilimindedir; bu yüzden turları genellikle en iyisinden yaklaşık %25 daha uzundur. Ekleme yöntemleri ise kapalı bir döngü tutar ve kalan şehirleri birer birer en az maliyetli oldukları yere ekler. Nicos Christofides 1976'da, herhangi bir metrik haritada en iyinin en fazla 1,5 katı olması garanti edilen bir kurma yöntemi buldu; bu sınır kırk yılı aşkın bir süre neredeyse hiç geçilemedi.

Bir turu iyileştirmek: 2-opt

Yerel arama herhangi bir turdan başlar ve onu kısaltan küçük değişiklikler yapmayı sürdürür. Klasik hamle olan 2-opt iki kenarı kaldırır ve iki parçayı ters yönde yeniden bağlar; bu, aradaki parçayı ters çevirir. İki kenar ne zaman kesişse bu hamle onları ayırır ve uzunluktan kazandırır; bu yüzden 2-opt'un iyileştiremediği bir tur hiçbir zaman kendini kesmez. Rastgele haritalarda 2-opt turları genellikle en iyiden yaklaşık %5 daha uzundur. Üç kenarı değiştiren daha güçlü hamleler ya da Lin ve Kernighan'ın 1973 tarihli değişken derinlikli yöntemi daha da yaklaşır.

Benzetimli tavlama

Yerel arama, çok daha iyi bir tur var olsa bile, her tek hamlenin durumu kötüleştirdiği bir turda takılıp kalabilir. Bu probleme 1983'te Scott Kirkpatrick, Daniel Gelatt ve Mario Vecchi tarafından uygulanan benzetimli tavlama, metalurjiden ödünç alır: kötüleştiren bir hamleyi, başta yüksek olan ve yavaşça düşürülen bir sıcaklığa bağlı bir olasılıkla kabul eder. Başlangıçta tur serbestçe dolaşır; sonunda yalnızca iyileştirmeler kabul edilir. Soğutma yeterince yavaş olduğunda güvenilir biçimde çok iyi turlar bulur.

Keşfedin

200 şehre kadar rastgele, bir çember üzerinde, kümeler hâlinde, bir ızgara üzerinde ya da tıkladığınız herhangi bir yere yerleştirmek için gezgin satıcı demosunu açın. En yakın komşunun son şehirlerini nasıl geride bıraktığını izleyin, 2-opt'un her kesişmeyi nasıl çözdüğünü görün, benzetimli tavlamanın sıcaklığını soğurken takip edin ve Held–Karp'ın 12 şehre kadar en kısa turu kanıtlamasına izin verin. Tümünü karşılaştır, her yöntemi aynı harita üzerinde çalıştırır ve her turun bulunan en kısa turdan ne kadar uzun olduğunu gösterir.

Sık sorulan sorular

Gezgin satıcı problemi nerede kullanılır?

Bir şeyin birçok yeri verimli bir sırayla ziyaret etmesi gereken her yerde: teslimat ve toplama rotaları, bir devre kartı üzerinde bir matkabın ya da lazerin izlediği yol, bir teleskobun yıldızları gözlemleme sırası, bir depodaki toplama sıraları ve farklı mesafelerle, bir DNA dizisi birleştirilirken parçaların sırası.

Kesin olarak çözülmüş en büyük problem hangisidir?

1954'te George Dantzig, Ray Fulkerson ve Selmer Johnson, Amerika Birleşik Devletleri'ndeki 49 şehirden geçen en kısa turu kanıtladı. 2006'da David Applegate, Robert Bixby, Vašek Chvátal ve William Cook'un Concorde çözücüsü, yıllarca süren bilgisayar zamanının ardından bir çip tasarımından alınan 85.900 noktadan geçen en iyi turu kanıtladı.

En kısa tur her zaman kesişmesiz midir?

Evet, düz çizgi mesafeleri olan düz bir haritada. İki kenar kesişseydi, onları oluşturdukları dörtgenin iki kenarıyla değiştirmek turu kısaltırdı; bu yüzden kendini kesen bir tur en kısa olamaz.

Sezgisel yöntemler her seferinde aynı turu mu verir?

Burada kullanıldıkları biçimiyle en yakın komşu, en ucuz ekleme ve 2-opt deterministiktir: aynı şehirlerde aynı turu verirler. Benzetimli tavlama rastgele bir turdan başlar ve rastgele hamleler yapar; bu yüzden iki çalıştırma, genellikle neredeyse aynı uzunlukta olan farklı turlarla bitebilir.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Gezgin satıcı demosunu açın