Manoj Gupta'nın geliştirdiği yeni APSP algoritması, 1996'dan beri aşılamayan sınırı geçti. Yöntem hızını korurken yakın noktalarda da doğruluk garantisi sunuyor.
30 saniyede bu haberin özeti Manoj Gupta, ağdaki tüm düğüm çiftleri arasındaki en kısa yolları bulan APSP problemi için 1996'dan beri aşılamayan bir sınırı geçti.Yeni yöntem, eski algoritma kadar hızlı çalışırken yakın noktalarda da en fazla iki kat hata garantisini koruyor.Çalışma teorik; ulaşım, telekomünikasyon ve biyolojik ağ analizleri için matematiksel temeli güçlendiriyor.Google'da SDN'yi tercih edilen kaynak yap Hindistan Teknoloji Enstitüsü Gandinagar'da doçent olan Manoj Gupta, grafiklerde en kısa yolları bulan APSP algoritması için önemli bir iyileştirme sundu. APSP, yani All-Pairs Shortest Paths, bir ağdaki tüm düğüm çiftleri arasındaki en kısa yolları hesaplar. Çalışma FOCS 2025 sempozyumunda yayımlandı.
Sonuç, 1996'dan beri ilk kez bir sınırı kaydırıyor. Bu sınırın ötesinde 2-yaklaşım garantisi veriliyordu. Yani tahmin edilen mesafe, gerçek mesafenin en fazla iki katı olabiliyordu. Ancak artık bu garanti birbirine çok daha yakın düğümler için de geçerli.
Dor, Halperin ve Zwick (DHZ) o yıl verimli bir yöntem önermişti. Seçilen az sayıda "yön noktası" sayesinde uzun rotalar hızla tahmin ediliyordu. Örneğin Delhi ile Chennai arasındaki yolu bulmak için tüm seçenekleri taramak gerekmiyordu.
Yorum Yap