Yapay zeka ajanları Dijkstra algoritmasını aşan yeni bir yol buldu
Öne çıkanlar
- 10 adet Claude Opus 5.5 ajanı 15 saatlik çalışma ve 733 mesajlaşma sonucunda C-HD algoritmasını geliştirdi.
- Geliştirilen algoritmanın doğruluğu ve zaman sınırları Lean doğrulama aracıyla matematiksel olarak kanıtlandı.
- C-HD algoritması belirli yoğunluk aralıklarında Dijkstra yöntemine kıyasla daha iyi bir asimptotik üst sınır sunuyor.
- Resmi yapıdaki sabit katsayıların büyüklüğü nedeniyle henüz ölçülebilir bir pratik hız artışı elde edilemedi.
Vals araştırmacıları, negatif olmayan gerçel ağırlıklı yönlü çizgelerde en kısa yol problemini çözen C-HD adlı yeni bir deterministik algoritma geliştirdi. Yaklaşık 15 saat süren ve 733 mesajlaşma içeren çalışma sürecinde 10 adet Claude Opus 5.5 ajanı görev yaptı. Geliştirilen algoritmanın hem doğruluğu hem de karmaşıklık sınırları matematiksel doğrulama aracı Lean ile resmen kanıtlandı.
Klasik Dijkstra algoritması uygun öncelik kuyruklarıyla O(m + n log n) süresinde çalışıyor. C-HD algoritması ise sınırlandırılmış yerel aramalar, yerel değişmezler ve kenar silme teknikleri kullanarak belirli yoğunluk aralıklarında O(n + m + m * log(2 + m/(n+1)) + m^(1/3) * (n*log(n+2))^(2/3)) çalışma zamanı sınırına ulaşıyor. Kenar sayısının düğüm sayısının logaritmasıyla orantılı olduğu m = n log n profili altında bu sınır O(n log n (log log n)^(2/3)) seviyesine geriliyor.
Elde edilen bu sonuç Dijkstra algoritmasına ve literatürdeki mevcut yöntemlere kıyasla daha iyi bir asimptotik üst sınır vadediyor. Ancak resmi kanıttaki sabit katsayılar çok büyük olduğundan henüz pratik bir hız artışı ölçülemedi. Küçük girdiler ve kapsam dışı yoğunluklar için Bellman-Ford algoritmasına başvuran C-HD sisteminin kaynak kodları ve Lean kanıtları GitHub üzerinden yayımlandı.
Bu özet yapay zekâ ile hazırlanmıştır; ayrıntılar ve doğrulama için orijinal kaynağa başvurun.