Nathan Klein ne zaman iki yıl önce yüksek lisansa başlayan danışmanları mütevazı bir plan önerdiler: teorik bilgisayar bilimlerindeki en ünlü, uzun süredir devam eden problemlerden biri üzerinde birlikte çalışmak.
Şimdi, Temmuz ayında çevrimiçi olarak yayınlanan bir makalede, Klein ve Washington Üniversitesi’ndeki danışmanları Anna Karlin ve Shayan Oveis Gharan, nihayet bilgisayar bilimcilerinin yaklaşık yarım yüzyıldır takip ettikleri bir hedefe ulaştılar: yaklaşık çözümler bulmanın daha iyi bir yolu gezgin satıcı problemi.
Bir şehirler topluluğu arasında en kısa (veya en ucuz) gidiş-dönüş yolunu arayan bu optimizasyon problemi, DNA dizilemesinden araç paylaşım lojistiğine kadar uzanan uygulamalara sahiptir. On yıllar boyunca, bilgisayar bilimindeki en temel ilerlemelerin çoğuna ilham vermiş ve doğrusal programlama gibi tekniklerin gücünü aydınlatmaya yardımcı olmuştur.
Gezgin satış elemanı problemi, hesaplama karmaşıklığında önde gelen bir uzman olan Christos Papadimitriou’nun çok sevdiği gibi, “sorun değil, bir bağımlılıktır”.
Çoğu bilgisayar bilimci, tüm olası şehir kombinasyonları için en iyi çözümleri verimli bir şekilde bulabilecek bir algoritma olmadığına inanıyor. Ancak 1976’da, Nicos Christofides yaklaşık çözümleri verimli bir şekilde bulan bir algoritma geliştirdi. O zamanlar bilgisayar bilimcileri, birinin yakında Christofides’in basit algoritmasını geliştirmesini ve gerçek çözüme yaklaşmasını bekliyorlardı. Ancak beklenen gelişme olmadı.
Stanford Üniversitesi’nden Amin Saberi, “Birçok insan bu sonucu iyileştirmek için sayısız saatler harcadı” dedi.
Şimdi Karlin, Klein ve Oveis Gharan, on yıl önce geliştirilen bir algoritmanın Christofides’in yüzde 50 faktörünü yendiğini kanıtladılar, ancak yüzde birin trilyonda birinin yalnızca 0,2 milyarda bir trilyonda birini çıkarabildiler. Yine de bu ufacık gelişme hem teorik hem de psikolojik bir engeli aşıyor. Araştırmacılar, daha fazla iyileştirme için taşkın kapaklarını açacağını umuyorlar.
1980’lerden beri gezgin satış elemanı sorunu üzerinde çalışan Cornell Üniversitesi’nden David Williamson, “Bu, tüm kariyerim boyunca istediğim bir sonuç” dedi.
Gezici satış elemanı problemi, teorik bilgisayar bilimcilerinin verimli hesaplamanın sınırlarını test etmek için tekrar tekrar başvurdukları bir avuç temel problemden biridir. Williamson, yeni sonucun “verimli hesaplamanın sınırlarının aslında düşündüğümüzden daha iyi olduğunu göstermeye yönelik ilk adım” olduğunu söyledi.
Her zaman en kısa yolculuğu bulan muhtemelen etkili bir yöntem olmasa da, neredeyse aynı derecede iyi bir şey bulmak mümkündür: tüm şehirleri birbirine bağlayan en kısa ağaç, yani kapalı döngüleri olmayan bir bağlantı (veya “kenar”) ağı. Christofides’in algoritması, bu ağacı bir gidiş-dönüş turunun omurgası olarak kullanır ve onu bir gidiş-dönüş turuna dönüştürmek için ekstra kenarlar ekler.
Her gidiş-dönüş rotasının, her varışın ardından bir kalkış izlediğinden, her şehre çift sayıda kenar olması gerekir. Bunun tersinin de doğru olduğu ortaya çıktı – bir ağdaki her şehir çift sayıda bağlantıya sahipse, ağın kenarları bir gidiş-dönüş izlemelidir.
Tüm şehirleri birbirine bağlayan en kısa ağaç bu düzgünlük özelliğinden yoksundur, çünkü bir dalın sonundaki herhangi bir şehrin başka bir şehirle sadece bir bağlantısı vardır. Böylece, en kısa ağacı bir gidiş-dönüş turuna dönüştürmek için, Christofides (geçen yıl ölen) tek sayıda kenarı olan şehir çiftlerini birbirine bağlamanın en iyi yolunu buldu. Ardından, ortaya çıkan gidiş-dönüş yolculuğunun asla mümkün olan en iyi gidiş-dönüşten yüzde 50’den daha uzun olmayacağını kanıtladı.
