Yeni algoritma en kısa yolu rekor sürede buluyor

Algoritma araştırmasında tarihi adım

Pekin'deki Tsinghua Üniversitesi'nde doçent olarak görev yapan Ran Duan liderliğinde gerçekleştirilen çalışma, modern grafik teorisinin temelini oluşturan en kısa yol problemine yönelik yeni bir çözüm ortaya koymuştur. Yaklaşık yetmiş yıl boyunca aynı klasik yaklaşıma güvenen araştırmacılar, bu görevi çözmek için daha hızlı bir yöntem geliştirmiştir. Yeni algoritma, milyonlarca bağlantı içerebilen ağlarda uzun süredir hakim olan Dijkstra algoritmasını performans açısından geride bırakmaktadır. Bu buluş, birkaç önde gelen üniversite arasındaki işbirliğinin sonucu olup, yol bulma konusunda neyin mümkün olduğuna dair uzun süredir tutulan inançlara meydan okumaktadır.

En kısa yol algoritmasının günlük hayattaki önemi

En kısa yol algoritmaları, modern dünyanın birçok kritik sisteminin merkezinde yer almaktadır. Navigasyon uygulamalarında kullanıcılara en verimli rotayı göstermekten, internet yönlendirmesinde veri paketlerinin en hızlı şekilde iletilmesine kadar geniş bir yelpazede uygulanmaktadır. Elektrik şebekelerinin optimizasyonundan, belirli oyunlarda hamle planlamasına kadar pek çok alanda bu algoritmaların işleyişi hayati önem taşımaktadır. Kopenhag Üniversitesi'nde bilgisayar bilimci olarak çalışan Mikkel Thorup, bu problemin "dünyadaki herkesin ilişki kurabileceği güzel bir problem" olduğunu vurgulamıştır. Tüm bu sistemler, sayısal maliyetlere sahip çizgilerle bağlanmış noktalardan oluşan bir ağ olan grafik olarak modellenebilmektedir.

Bir iyi rota bulmak yeterince zor olsa da, birçok sistem bir başlangıç noktasından ağdaki diğer her düğüme olan mesafelere ihtiyaç duymaktadır. Bilgisayar bilimcileri buna "tek kaynaklı en kısa yollar" adını vermektedir; bu, bir düğümden diğer her düğüme olan mesafeleri hesaplama problemini ifade etmektedir. Bu tür hesaplamalar, özellikle büyük ağlarda işlem gücü açısından oldukça yoğun bir iş olup, algoritmanın verimliliği doğrudan sistem performansını etkilemektedir.

Dijkstra algoritmasının yetmiş yıllık hükümranlığı

1959 yılında Edsger Dijkstra tarafından yayınlanan yöntem, en yakın sınır düğümünü tekrar tekrar genişleterek en kısa yolları oluşturmaktadır. Modern uygulamalar, öğeleri sayısal bir mesafeye göre sıralı tutan bir araç olan "öncelik kuyruğu" adlı bir veri yapısı kullanarak bu algoritmanın verimliliğini artırmıştır. Kuyruk her seferinde bir sonraki düğümü seçtiğinde, birçok öğeden oluşan bir listeyi sıralı düzende tutmaya benzer bir iş gerçekleştirilmektedir. Son teorik sonuçlar, bir algoritmanın düğümleri mesafeye göre tamamen sıralanmış olarak çıkarması gerekiyorsa, Dijkstra'nın yaklaşımının esasen mümkün olduğunca hızlı olduğunu göstermektedir.

Yol bulma ve sıralama arasındaki bu bağlantı, "sıralama engeli" olarak bilinen bir sınırlama yaratmıştır. Bu engel, hiçbir algoritmanın genel seyrek grafiklerde sıralama süresini geçemeyeceği inancının oluşmasına neden olmuştur. Yaklaşık kırk yıl boyunca, çoğu uzman herhangi bir ek hızlanmanın yeni bir algoritmik fikir yerine yalnızca yeni donanım hileleri gerektireceğini varsaymıştır. Büyük seyrek grafikler için, klasik analizler Dijkstra algoritmasının yaklaşık m işlem artı n çarpı log n ile orantılı ekstra bir faktör aldığını göstermektedir. Bu log n faktörü, sınırı öncelik kuyruğunun içinde etkili bir şekilde sıralı tutma ihtiyacından kaynaklanmaktadır.