APSP algoritmasında 30 yıllık doğruluk sınırı aşıldı

Bir ağdaki tüm noktalar arasındaki en kısa yolları hesaplayan APSP algoritmalarında hız ile doğruluk arasında uzun süredir bilinen bir sınır vardı. Hindistan Teknoloji Enstitüsü Gandhinagar’da doçent olan Manoj Gupta’nın çalışması, 1996’dan beri aşılamayan bu sınırı değiştiriyor: Yeni yöntem, önceki yaklaşımın çalışma hızını korurken birbirine yakın düğümler için de en fazla iki kat hata garantisi veriyor.

APSP, İngilizce “All-Pairs Shortest Paths” ifadesinin kısaltması. Bir grafikteki her düğüm çifti arasındaki en kısa mesafeyi bulmayı amaçlıyor. Ulaşım, telekomünikasyon ve biyolojik ağlar gibi farklı alanlarda kullanılan ağ analizlerinin temel problemlerinden biri. Gupta’nın sonucu, FOCS 2025 sempozyumunda yayımlandı.

Yakın düğümler eski algoritmanın zayıf noktasıydı

Dor, Halperin ve Zwick’in 1996’da geliştirdiği yöntem, çok sayıda düğüm arasındaki uzaklıkları daha verimli tahmin etmek için ağdaki seçili noktalardan yararlanıyordu. “Yön noktaları” olarak kullanılan bu düğümler, uzun rotaların hızlı hesaplanmasına yardımcı oluyordu. Ancak yöntem, birbirine yakın iki düğüm arasındaki en kısa bağlantıyı her zaman bulamıyordu.

Gerçek rota kısa olduğunda algoritmanın seçtiği yön noktaları bu bağlantıdan uzakta kalabiliyordu. Böylece yöntem, gerçek mesafeden belirgin ölçüde uzun bir tahmin üretebiliyordu. Genel olarak sunulan iki katlık hata sınırı, yakın düğümler arasındaki mesafeler için aynı güvenceyi sağlamıyordu.

Gupta’nın çalışması, noktaların seçilme ve temsil edilme biçimini değiştirerek bu açığı kapatıyor. Tek bir ölçekte belirlenen yön noktalarına dayalı bir yapı yerine grafiği birden fazla ölçekte ele alan çok seviyeli bir yaklaşım kullanılıyor. Bu sayede hem ağın geniş bölümlerindeki uzun bağlantılar hem de yerel ölçekteki kısa rotalar hesaba katılabiliyor.

Hızdan ödün vermeden daha geniş bir güvence

Yöntemin öne çıkan yanı, yakın düğümler için daha iyi sonuç verirken hesaplama karmaşıklığını artırmaması. Başka bir deyişle, doğruluk garantisini genişletmek için eski yaklaşımdan daha yavaş çalışması gerekmiyor. Mesafe tahmininin gerçek değerin en fazla iki katı olacağı güvencesi, önceki yöntemin zorlandığı kısa mesafeleri de kapsıyor.

Yaklaşık algoritmalar, büyük grafiklerde kesin sonuç elde etmenin yüksek işlem gücü gerektirebilmesi nedeniyle kullanılıyor. Düğüm sayısı arttıkça tüm düğüm çiftlerinin mesafelerini hesaplama yükü de büyüyor. Tam APSP hesabının kübik zaman gerektirmesi, büyük veri kümelerinde verimli çözüm bulmayı zorlaştırıyor. Yaklaşık yöntemler ise belirli bir hata payını kabul ederek daha verimli hesaplama olanağı sunuyor.

Buradaki sonuç, navigasyon uygulamalarının hemen değişeceği anlamına gelmiyor. Çalışma teorik nitelikte; doğrudan bir harita hizmetine eklenmiş değil. Araştırma, büyük ağlarda kullanılabilecek algoritmaların matematiksel temelini geliştiriyor. Ulaşım ağlarındaki rotaların incelenmesi, telekomünikasyon altyapısındaki bağlantıların değerlendirilmesi ve protein etkileşimleri ya da sinir bağlantıları gibi biyolojik grafiklerin analizi, APSP’nin ilişkilendirildiği alanlar arasında.

Yaklaşık otuz yıldır açık kalan sınırın aşılması, köklü algoritmanın tümüyle değiştirilmesi gerektiğini göstermiyor. Gupta’nın yöntemi, önceki yaklaşımın hız avantajını korurken hata garantisinin geçerli olduğu mesafe türlerini genişletiyor. Bu da büyük ve karmaşık ağları daha yönetilebilir biçimde analiz etmeye yönelik teorik araştırmalara yeni bir seçenek sunuyor.

Çalışmanın pratik sistemlere ne zaman ve nasıl uyarlanacağı ise mevcut bilgilerden çıkarılamıyor. Yine de yakın düğümlerle ilgili doğruluk açığının giderilmesi, yaklaşık mesafe hesaplarının yalnızca uzun rotalarda değil, ağın yerel bağlantılarında da daha tutarlı sonuç vermesinin önünü açıyor. Bu yönüyle araştırma, performansı korurken algoritmanın hata sınırını daha geniş bir kullanım alanında güvenilir kılmayı hedefliyor.