30 Yıllık Matematiksel Kilit Kırıldı: 1996 Tarihli Algoritma İmkansız Denen Hıza Nasıl Ulaştı?
Yeni bir algoritma, 1996’dan beri bilgisayar30 Yıllık Matematiksel bilimcilerini zorlayan bir sorunu çözerek devasa ağlardaki yakın noktalar arası mesafe tahminlerini iyileştiriyor.
Navigasyon uygulamaları genellikle bir otelden havaalanına giden en hızlı yolu bulmak gibi, tek seferde tek bir rota hesaplar. Bilgisayar bilimcileri ise bu zorluğun çok daha büyük bir boyutuyla, yani bir ağdaki her bir olası konum çifti arasındaki en kısa mesafeyi hesaplama sorunuyla karşı karşıyadır.
“Tüm Çiftler Arası En Kısa Yollar” (All-Pairs Shortest Paths – APSP) problemi olarak bilinen bu görev, yol haritalarının çok ötesinde uygulama alanlarına sahiptir. Bir çizge (graf); veri bağlantılarıyla birbirine bağlı bilgisayarları, demiryolu hatlarıyla birleşen istasyonları, hücre içinde etkileşime giren proteinleri veya beyinde iletişim kuran nöronları temsil edebilir. Bu yapıdaki noktalara “düğüm” (vertex), bunlar arasındaki bağlantılara ise “kenar” (edge) adı verilir.
Devasa Ağlar Bilgisayarları Neden Zorlar?
Ağ büyüdükçe kesin hesaplamalar yapmak yüksek maliyetli (işlem gücü açısından külfetli) hale gelir. Yoğun çizgelerde geleneksel yöntemler “kübik zaman” gerektirebilir. Dolayısıyla düğüm sayısının iki katına çıkması, yaklaşık sekiz kat daha fazla işlem yükü doğurabilir. Elde edilen sonuç kümesi de devasa boyutlardadır; çünkü *n* sayıda düğüme sahip bir ağ, mesafelerinin raporlanması gerekebilecek *n*² adet sıralı çift içerir.
Bu ölçeklenme sorunu, araştırmacıları yaklaşık sonuç veren algoritmalar (yaklaşım algoritmaları) geliştirmeye yöneltmiştir. Bu yöntemler, hız konusunda büyük kazanımlar elde etmek adına hassasiyetten bir miktar ödün verir; böylece tam olarak kesin olmayan ancak matematiksel olarak tanımlanmış bir aralıkta kalan sonuçlar üretirler.
1996 yılında Dor, Halperin ve Zwick; neredeyse en uygun (optimal) sürede bir “2-yaklaşımı” (2-approximation) sunan etkili bir yöntem ortaya koydular. Bu yöntemin ürettiği tahmin, gerçek en kısa mesafenin iki katını aşmıyordu. Örneğin, iki konum arasındaki gerçek mesafe 10 kilometre (6,2 mil) ise, hesaplanan mesafe 10 ila 20 kilometre (6,2 ila 12,4 mil) aralığında kalıyordu.
Kör Noktası Olan Hızlı Bir Kestirme Yol
DHZ algoritması, her bir rotayı bütünüyle incelemekten kaçınır. Bunun yerine, “örneklenmiş düğümler” (sampled vertices) olarak bilinen ve temsili nitelikteki noktalardan oluşan nispeten küçük bir küme seçer; ağın diğer kısımlarındaki mesafeleri tahmin etmek için bu noktaları birer referans noktası olarak kullanır.
Bu strateji, iki düğüm birbirinden uzak olduğunda iyi sonuç verir. New York ile Los Angeles arasındaki bir yolculuğa benzer uzunluktaki bir rotada, en kısa yolun yakınında en az bir örneklenmiş düğümün bulunma ihtimali yüksektir. Bu referans noktasından geçmek rotaya yalnızca küçük bir sapma ekleyebilir; böylece tahmin, vaat edilen “iki katı” sınırının içinde kalır.
Kısa rotalar ise daha zorludur. Örneğin, Los Angeles banliyölerindeki iki mahalle, sadece iki kenardan (bağlantıdan) oluşan bir yolla birbirine bağlanabilir; ancak bu mahallelerin hiçbiri bir örneklenmiş düğümün yakınında yer almayabilir. Uzaktaki bir referans noktası üzerinden yapılacak bir yolculuk, gerçek mesafenin iki katından daha fazla olan “beş kenarlık” bir tahmin ortaya çıkarabilir.
Dolayısıyla algoritma, yeterince uzak düğüm çiftleri için hızlı ve güvenilirdi; ancak sunduğu garanti, birbirine yakın düğümler için aynı etkinlikte geçerli değildi. Bu sınır, neredeyse 25 yıl boyunca geliştirilmeye direndi.
Çizgeyi (Grafı) Farklı Ölçeklerde Örneklemek
Indian Institute of Technology Gandhinagar’da doçent olan Manoj Gupta, 66. Yıllık Bilgisayar Bilimlerinin Temelleri Sempozyumu’nda (FOCS 2025) yeni bir çözüm sundu.
Gupta’nın algoritması, tek bir örneklenmiş düğüm katmanına bel bağlamak yerine, örnekleri çeşitli ölçeklere yayar. Her katman, çizge yapısının farklı bir düzeyini yakalar; böylece en kısa yol nispeten kısa olduğunda bile uygun bir referans noktasının bulunma olasılığı artar.
Bu çok ölçekli tasarım, “iki katı” (2-approximation) tahmin garantisinin geçerli olduğu mesafe eşiğini aşağı çeker. Pratik açıdan bakıldığında algoritma, genel zaman karmaşıklığını en azından aynı seviyede tutarken, önceki yaklaşımlara kıyasla birbirine çok daha yakın düğüm çiftleri için güvenilir tahminler sunabilir.
Tahmin değerinin gerçek mesafenin iki katına ulaşmasına hâlâ izin verilmektedir. Ancak sağlanan iyileştirme, bu garantinin geçerli olduğu düğüm çifti aralığını büyük ölçüde genişletir ve hızdan ödün vermeden birbirine yakın noktaları da kapsama alanına dahil eder.
Bağlantılı Sistemler İçin Daha Güçlü Temeller
Büyük grafikler, internet yönlendirmesi, ulaşım planlaması, sosyal platformlar, biyolojik araştırmalar ve bağlantılı veriler arasındaki ilişkileri işleyen yapay zeka sistemlerinin temelini oluşturur. Bu tür ortamlarda kesin mesafeler her zaman gerekli değildir. Kesin doğruluk garantisiyle hızlı bir tahmin, hesaplanması çok uzun süren mükemmel bir cevaptan çok daha faydalı olabilir.
Sonuç, ticari navigasyon yazılımlarının hazır bir alternatifi olmaktan ziyade teorik bir ilerleme olarak kalmaktadır. Yine de, daha güçlü teorik sınırlar, çok sayıda bağlantı içeren ağlardan güvenilir bilgileri çıkarmanın daha verimli yollarını ortaya çıkararak gelecekteki algoritmaları şekillendirebilir.
Graf teorisindeki ilerleme genellikle uzun süredir yerleşik sınırlara yapılan küçük iyileştirmelerle gelir. 1996’dan beri büyük ölçüde geçerli olan bir garantinin genişletilmesi, modern teknoloji ve bilime örülmüş muazzam ağlar genelinde hızlı, ölçeklenebilir mesafe hesaplamalarına doğru anlamlı bir adım temsil etmektedir.
Kaynak: https://scitechdaily.com/