Furkan Altunsoy6 ay önce
En klasik algoritmik problemlerden biri, iki nokta arasındaki en kısa yolu hesaplamakla ilgilidir. Sorunun daha karmaşık bir çeşidi, yolun değişen bir ağdan geçtiği zamandır - bu ister bir yol ağı ister internet olsun. Araştırmacılar 40 yıldır bu soruna en uygun çözümü sağlayan bir algoritma arıyorlar. Şimdi, Kopenhag Üniversitesi'nden bilgisayar bilimcisi Christian Wulff-Nilsen ve iki araştırma meslektaşı bir tarif buldular.
Yeni bir yere giderken, çoğumuz ister bir arabanın GPS'sini kullanarak ister toplu taşıma ve telefonlarındaki harita uygulamalarını kullanarak en iyi rotayı bulmamıza yardımcı olması için onu bilgisayar algoritmalarına bırakıyoruz. Yine de, önerilen bir yolun gerçeklikle tam olarak örtüşmediği zamanlar vardır. Bunun nedeni, yol ağlarının, toplu taşıma ağlarının ve diğer ağların statik olmamasıdır. En iyi rota aniden en yavaş olanı olabilir, örneğin yol çalışması veya kaza nedeniyle bir kuyruk oluştuğundan.
İnsanlar muhtemelen bu tür durumlarda yönlendirme önerilerinin arkasındaki karmaşık matematik hakkında düşünmezler. Kullanılan yazılım, dinamik bir ağdaki en kısa yol olan klasik algoritmik " en kısa yol " probleminin bir çeşidini çözmeye çalışıyor. Araştırmacılar 40 yıldır bu matematiksel bilmeceyi en iyi şekilde çözebilecek bir algoritma bulmak için çalışıyorlar. Şimdi, Kopenhag Üniversitesi Bilgisayar Bilimleri Bölümünden Christian Wulff-Nilsen, iki meslektaşı ile birlikte somunu kırmayı başardı.
" Şimdiye kadarki diğer tüm algoritmalardan daha iyi olduğunu ve geleceğe 1000 yıl baksak bile en iyiye en yakın şey olacağını şimdi matematiksel kanıtına sahip olduğumuz bir algoritma geliştirdik ," diyor. Doçent Wulff-Nilsen. Sonuçlar prestijli FOCS 2020 konferansında sunuldu.
Optimal olarak, bu bağlamda, belirli bir ağdaki en iyi rotayı hesaplamak için olabildiğince az zaman ve mümkün olduğunca az bilgisayar belleği harcayan bir algoritmayı ifade eder. Bu sadece karayolu ve ulaşım ağları için değil, aynı zamanda internet veya diğer ağ türleri için de geçerlidir.
Grafikler olarak ağlar
Araştırmacılar bir ağı dinamik grafik olarak adlandırıyorlar. Bu bağlamda, bir grafik, örneğin, kavşakları temsil eden, örneğin kenarlar, yollar ve düğümlerden oluşan bir ağın soyut bir temsilidir. Bir grafik dinamik olduğunda, zamanla değişebileceği anlamına gelir. Yeni algoritma, silinmiş kenarlardan oluşan değişiklikleri ele alır - örneğin, bir yolun bir bölümünün eşdeğerine yol çalışması nedeniyle aniden erişilemez hale gelirse.
"Bir ağı soyut bir grafik olarak görmenin en büyük avantajı, herhangi bir ağı temsil etmek için kullanılabilmesidir. Mümkün olduğu kadar kısa bir yoldan veri göndermek istediğiniz internet, bir insan beyni veya Facebook'ta arkadaşlık ilişkileri ağı. Bu, grafik algoritmalarını çok çeşitli bağlamlarda uygulanabilir hale getiriyor, "diye açıklıyor Christian Wulff-Nilsen.
Geleneksel algoritmalar, bir grafiğin statik olduğunu varsayar ve bu gerçek dünyada nadiren doğrudur. Bu tür algoritmalar dinamik bir ağda kullanıldığında, grafikte her küçük değişiklik oluştuğunda yeniden çalıştırılmaları gerekir - bu da zaman kaybına neden olur.
Daha fazla veri, daha iyi algoritmalar gerektirir
Daha iyi algoritmalar bulmak sadece seyahat ederken faydalı değildir. Christian Wulff-Nilsen'in belirttiği gibi, verilerin üretildiği hemen hemen her alanda gereklidir:
"Veri hacimlerinin muazzam bir hızla büyüdüğü ve donanım geliştirmenin buna ayak uyduramadığı bir zamanda yaşıyoruz. Ürettiğimiz tüm verileri yönetmek için, daha az çalışma süresi gerektiren daha akıllı yazılımlar geliştirmemiz gerekiyor. Bu yüzden daha akıllı algoritmalara ihtiyacımız var "diyor.
Bu algoritmayı veya arkasındaki bazı teknikleri pratikte kullanmanın mümkün olacağını umuyor, ancak bunun teorik kanıt olduğunu ve önce deney gerektirdiğini vurguluyor.
"Yoğun Ağırlıklı Dijital Grafiklerde Optimal Azalımlı SSSP" araştırma makalesi prestijli FOCS 2020 konferansında sunuldu.
Kaynak:
Love
1
Cool
0
Geeky
0
Lol
0
Meh
0
Omg
0
Thnk
0
Angry
0