Wired’in haberine göre,
“Bu harika bir algoritma” dedi Erik DemaineMassachusetts Teknoloji Enstitüsü'nde bilgisayar bilimcisi. “Çok hızlı, basit ve uygulaması kolay.”
Bu prosedürü uygulamaya koymak için, notlarınızı düzenlemek için bir sistem (bilgisayar bilimi dilinde bir veri yapısı) üzerinde karar vermeniz gerekir. Bu küçük bir teknik ayrıntı gibi görünebilir, ancak bir girişi düzenlemeniz veya kaldırmanız gerektiğinde notlarınızı aramak için harcadığınız zaman, algoritmanın genel çalışma süresi üzerinde büyük bir etkiye sahip olabilir.
Dijkstra'nın makalesinde iyileştirmeye yer bırakan basit bir veri yapısı kullanıldı. Sonraki yıllarda araştırmacılar, bazı öğelerin diğerlerine göre daha kolay bulunabildiği, sevgiyle “yığınlar” olarak adlandırılan daha iyi öğeler geliştirdiler. Dijkstra'nın algoritmasının yalnızca kalan en yakın köşeye ait girişi kaldırması gerektiği gerçeğinden yararlanıyorlar. “Bir yığın temel olarak bunu çok hızlı bir şekilde yapmanızı sağlayan bir veri yapısıdır” dedi Vaclav RozhoňBulgaristan'ın Sofya kentindeki Bilgisayar Bilimi, Yapay Zeka ve Teknoloji Enstitüsü'nde (INSAIT) araştırmacı.
1984 yılında iki bilgisayar bilimcisi bir akıllı yığın tasarımı Bu, Dijkstra'nın algoritmasının, tek kaynaklı en kısa yol problemini çözmek için gereken sürede teorik bir sınıra veya “alt sınıra” ulaşmasını sağladı. Belirli bir anlamda, Dijkstra'nın algoritmasının bu versiyonu mümkün olan en iyisidir. Bu, yaklaşık 40 yıldır sorunun standart versiyonuna ilişkin son sözdü. Ancak birkaç araştırmacı “en iyi” olmanın ne anlama geldiğine daha yakından baktığında işler değişti.
En İyi Davranış
Araştırmacılar genellikle algoritmaları en kötü senaryolarda nasıl başarılı olduklarını inceleyerek karşılaştırırlar. Dünyanın en kafa karıştırıcı sokak ızgarasını hayal edin, ardından özellikle kafa karıştırıcı bazı trafik düzenlerini ekleyin. Bu ekstrem koşullarda en hızlı rotaları bulmakta ısrarcıysanız, Dijkstra'nın algoritmasının 1984 versiyonu kesinlikle rakipsizdir.
Ama umarız şehrinizde dünyanın en kötü sokak ağı yoktur. O halde şunu sorabilirsiniz: Her yol ağında rakipsiz bir algoritma var mı? Bu soruyu yanıtlamanın ilk adımı, her ağın en kötü durum trafik modellerine sahip olduğu yönünde ihtiyatlı bir varsayımda bulunmaktır. Daha sonra algoritmanızın, mümkün olan en kötü ağırlıkları varsayarak, mümkün olan herhangi bir grafik düzeni boyunca en hızlı yolları bulmasını istiyorsunuz. Araştırmacılar bu duruma “evrensel optimalite” adını veriyor. Eğer grafikteki bir noktadan diğerine gitmek gibi daha basit bir problem için evrensel olarak optimal bir algoritmaya sahip olsaydınız, bu, dünyanın her şehrinde trafiğin yoğun olduğu saatlerin üstesinden gelmenize yardımcı olabilirdi.
