Mart 29, 2024

PoderyGloria

Podery Gloria'da Türkiye'den ve dünyadan siyaset, iş dünyası

1950’lerden algoritmik bulmacaların mükemmel çözücüsü araştırmacı tarafından övüldü – ScienceDaily

Yarım yüzyıldan fazla bir süredir, dünyanın dört bir yanındaki araştırmacılar, “tek kaynaklı en kısa yol sorunu” olarak bilinen bir algoritma sorunuyla uğraşıyorlar. Problem temel olarak, negatif ağırlıklı bağlantılar olabileceğinden, bir düğüm ile ağdaki diğer tüm düğümler arasındaki en kısa yolu bulmanın en iyi yolunu bulan matematiksel bir tarifin nasıl tasarlanacağıdır.

Kulağa karmaşık mı geliyor? Muhtemelen. Ancak aslında bu tür bir hesaplama, yolumuzu bulmak için güvendiğimiz çok çeşitli uygulamalarda ve teknolojilerde zaten kullanılmaktadır – örneğin, Google Haritalar bize manzaralar ve şehirler arasında rehberlik eder.

Şimdi, Kopenhag Üniversitesi Bilgisayar Bilimleri Bölümü’nden araştırmacılar sorunu çözdüler. Tek kaynaklı en kısa yol problemionlarca yıldır araştırmacıları ve uzmanları şaşırtan bir gizem.

“Problemi neredeyse lineer zamanda, mümkün olan en hızlı şekilde çözen bir algoritma keşfettik. Bu, 1950’lerden beri üzerinde çalışılan ve tüm dünyada öğretilen temel bir algoritma problemidir. Gelmeye karar vermemizin sebeplerinden biri de buydu. Bir çözüm bulmak,” diye açıklıyor Doçent Christian Wolf-Nielsen, kendi başına çözülmemiş bir algoritma sorunu.

Direksiyon elektrikli araçlar için daha hızlı hesaplamalar

Geçen yıl, Wulff-Nilsen aynı alanda başka bir atılım yaparak zamanla değişen bir ağda en kısa yolun nasıl bulunacağını ele alan bir sonuç ortaya koydu. Son yapboza yaptığı çözüm bu çalışmaya dayanmaktadır.

Araştırmacı, tek bir kaynakla en kısa yol problemini çözmenin, yalnızca elektrikli arabaların A’dan B’ye en hızlı yolu anında hesaplamasına değil, aynı zamanda bunu mümkün olan en enerji verimli şekilde yapmasına yardımcı olan algoritmaların önünü açabileceğine inanıyor.

“Önceki algoritmaların sahip olmadığı bir boyut ekliyoruz. Bu boyut, negatif ağırlıklar dediğimiz şeye bakmamızı sağlıyor. Bunun pratik bir örneği, yol ağındaki tepelere atıfta bulunmak olabilir. Wolf-Nielsen yokuşlarda seyahat ederken şarj olan bir elektrikli arabayı açıklıyor.

READ  Apple yıldırım kablosunu terk ediyor

Tek kaynaklı en kısa yol problemi hakkında gerçekler

  • Noktası Tek kaynak en kısa yoldur Sorun, belirli bir başlangıç ​​düğümünden ağdaki diğer tüm düğümlere giden en kısa yolları bulmaktır.
  • Bir ağ, düğümler ve bunlar arasındaki kenarlar adı verilen bağlantılardan oluşan bir grafik olarak temsil edilir.
  • Bir yönün her kenarı için (örneğin, tek yönlü yolları temsil etmek için kullanılabilir), artı bu kenar boyunca seyahat etmenin maliyetini ifade eden bir ağırlık. Tüm kenar ağırlıkları negatif değilse, problem Dijkstra’nın klasik algoritması kullanılarak yaklaşık doğrusal zamanda çözülebilir.
  • Yeni sonuç, sorunu Dijkstra’nın algoritmasıyla yaklaşık aynı sürede çözüyor, ancak aynı zamanda negatif kenar ağırlıklarına da izin veriyor.

“Prensipte, algoritma, spekülatörler çeşitli para birimlerinin alım satımı üzerine spekülasyon yapıyorsa, merkez bankaları gibi aktörleri uyarmak için kullanılabilir. Bugün bunun çoğu bilgisayarlarda oluyor. Ancak algoritmamız çok hızlı olduğu için, güvenlik açıklarını istismar etmeden önce tespit etmek için kullanabilir,” diyor Christian Wolf-Nielsen.

Araştırmacı, elektrikli otomobiller için para birimi ve yol hesaplama sistemlerinin zaten var olduğunu doğruluyor. Ancak en kısa yol problemini tek bir kaynakla çözmek, araştırmacıların hız açısından yenilmesi neredeyse imkansız olan etkileyici bir algoritma oluşturmasına olanak sağladı. Aynı zamanda sadeliği, toplumun farklı ihtiyaçları için benimsenmesini kolaylaştırır.

Amerika Birleşik Devletleri’nde onurlandırıldı

Sorunu çözmek için yapılan çalışmalar dikkatlerden kaçmadı. Aslında, Christian Wolf Nielsen ve meslektaşları, dünyanın her yerinden onları tebrik etmek ve bunu nasıl başardıkları hakkında daha fazla bilgi edinmek isteyen kişilerle temasa geçti bile.

Aynı zamanda, keşiflerini detaylandıran araştırma makalesi, Denver, Colorado’daki FOCS (Bilgisayar Bilimi Vakfı) konferansında “En İyi Bildiri Ödülü” ile onurlandırıldı. STOC ile birlikte teorik bilgisayar bilimlerindeki en prestijli konferanstır. FOCS konferansı 31 Ekim – 3 Kasım 2022 tarihleri ​​arasında gerçekleşti.

READ  Apple, iCloud.com'u yepyeni bir tasarımla yeniden başlattı

Christian Wolf-Nielsen, “Dünyanın her yerinden insanlar en iyi sonuçları görmek için bu konferansa geliyor” diyor.

Araştırma, Bilgisayar Bilimleri Bölümü’nden Christian Wolff Nielsen, Max Planck Enstitüsü’nden Danubon Nanongkai ve Amerikalı meslektaşları Rutgers Üniversitesi’nden Aaron Bernstein işbirliğiyle yürütüldü.