Manoj Gupta, en kısa yol algoritmalarında 1996'dan kalma engeli aştı

Indian Institute of Technology Gandhinagar'dan Manoj Gupta, çok büyük ağlardaki mesafeleri hesaplama süresini artırmadan daha isabetli tahmin eden bir algoritma geliştirdi. Çalışma, bilgisayar biliminde 1996'dan beri aşılamayan bir sınırlamayı ortadan kaldırıyor.

APSP problemi ve eski sınır

Yöntemin anahtarı, birbirine yakın noktalar arasındaki en kısa yolların daha doğru yaklaşık değerlerini elde edebilmesi. Bilgisayarlar bu işi her gün yapıyor; navigasyon uygulamaları, ulaşım sistemleri ve internet altyapısı buna dayanıyor. Ancak büyük bir ağdaki her nokta çifti arasındaki mesafeler hesaplanacağı zaman iş çok zorlaşıyor. Bilgisayar bilimi bu soruna APSP (All-Pairs Shortest Paths) diyor. Ağ; şehirleri, bilgisayarları, tren istasyonlarını, hatta nöronları temsil eden noktaların birbirine bağlanmasıyla düşünülebilir.

Yoğun ve büyük bir ağda tüm en kısa yolları kesin biçimde bulmak çok büyük hesaplama gücü gerektirir. Bu yüzden araştırmacılar her yolu incelemeden güvenilir sonuç veren yöntemler arıyor. 1996'da Dor, Halperin ve Zwick, tahminin gerçek en kısa mesafenin iki katını aşmayacağını garanti eden bir algoritma geliştirdi; buna 2 katlı yaklaşım deniyor. Fakat bu garanti esas olarak birbirinden uzak noktalar için geçerliydi. Kısa bağlantılarda hata büyüyebiliyordu: gerçek rota iki bağlantıdan oluşurken tahmin beş çıkabiliyor, bu da izin verilen iki kat sınırını aşıyordu.

Çok ölçekli örnekleme

Gupta, mesafe tahmininde kullanılan noktaların seçilme biçimini iyileştirdi. Önceki yaklaşım, küçük bir temsilci köşe kümesine dayanıyordu. Yeni algoritma ise çok ölçekli örnekleme kullanıyor; yani ağın yapısını tek bir nokta seti yerine birkaç farklı düzeyde inceliyor. Böylece daha önce gözden kaçabilen kısa bağlantılar da hesaba katılıyor.

En önemli nokta, doğruluktaki artışın algoritmanın genel hesaplama karmaşıklığını yükseltmemesi. Yani daha güvenilir sonuçlar, ek bir süre maliyeti olmadan elde ediliyor.

Bu gelişme telekomünikasyon, ulaşım, sosyal medya ve yapay zekâ sistemleri gibi geniş ağları analiz eden alanlarda işe yarayabilir. Ağ öğeleri arasındaki mesafeleri hızlı ve güvenilir biçimde tahmin etmek, bağımlılıkların analizini ve sistemlerin optimizasyonunu kolaylaştırıyor.