ETH Zürih araştırmacıları en hızlı akış algoritmasını geliştirdi

 (ethz.ch)
1 puan yazan GN⁺ 2024-06-30 | 1 yorum | WhatsApp'ta paylaş
  • ETH Zurich'ten Rasmus Kyng'in araştırma ekibi, ağlarda maksimum akışı bulup taşıma maliyetini en aza indiren problemi neredeyse matematiksel sınır hızında hesaplayan bir algoritma geliştirdi
  • Yeni algoritma, ağ verisini okuma süresiyle neredeyse aynı ölçekte yanıt veren neredeyse doğrusal zamanlı bir yaklaşım ve demiryolu, karayolu, su yolu ve internet gibi ağ hesaplamalarına uygulanabiliyor
  • Geçmişte bağlantı sayısı m olduğunda hız 2000 yılına kadar m^1.5, 2004'te ise m^1.33 düzeyindeydi; Kyng'in yaklaşımı ise veriyi okuduktan sonraki ek hesaplama süresini ihmal edilebilir bir seviyeye indiriyor
  • Araştırma ekibi, statik ve yönlü ağların ötesine geçerek bağlantıların eklendiği artımlı grafikler ve silindiği azalan grafikler üzerinde de en kısa yolu ve minimum maliyetli maksimum akışı neredeyse doğrusal zamanda hesapladı
  • Gotthard Base Tunnel'in kapanıp kısmen yeniden açılması ya da A13 otoyolundaki heyelan gibi gerçek ağ değişimlerinde en uygun rotayı hızla yeniden hesaplamanın temelini oluşturuyor

Ağ akışı problemini neredeyse sınır hızında hesaplamak

  • Rasmus Kyng'in araştırma ekibinin ağ akışı algoritması, ağda mümkün olan en büyük akışı bulurken taşıma maliyetini en aza indirme problemini ele alıyor
  • Copenhagen'dan Milan'a mümkün olduğunca çok yükü en hızlı ve en ucuz şekilde taşıyacak rotayı bulma durumu bunun tipik bir örneği
  • Demiryolu, karayolu, su yolu ve internet gibi bağlantı ve kapasite içeren ağlarda en uygun düşük maliyetli akış hesaplanabiliyor
  • Hesaplama hızı, bilgisayarın ağ verisini okuma süresiyle neredeyse aynı seviyeye indirildi

Neden “en hızlı” algoritma?

  • Önceden en uygun akışı hesaplama süresi, ağ verisini işleme süresinden çok daha uzundu
  • Ağ büyüyüp karmaşıklaştıkça gereken hesaplama süresi problem boyutundan daha hızlı artıyordu
  • Kyng'in yaklaşımı, hesaplama süresi ile ağ boyutunun aynı oranda artmasını sağlıyor
    • Ağdaki bağlantı sayısı m ise veriyi bir kez okumak bile m zaman alıyor
    • 2000 yılına kadar m^1.5'ten daha hızlı çalışan bir algoritma yoktu
    • 2004'te problemi çözmek için gereken hesaplama miktarı m^1.33 seviyesine indi
    • Kyng algoritması, veri okunduktan sonra çözüme ulaşmak için gereken ek hesaplama süresini ihmal edilebilir düzeye indiriyor

Neredeyse doğrusal zamanlı algoritmanın değerlendirilmesi ve genişletilmesi

  • Kyng'in araştırma ekibi bu kavramın matematiksel ispatını içeren makaleyi iki yıl önce yayımladı
  • Bu kadar neredeyse optimum hızlı algoritmalar neredeyse doğrusal zamanlı algoritmalar olarak adlandırılıyor
  • Daniel A. Spielman bu algoritmayı at arabasını geçen bir Porsche'a benzetti
  • İlgili makale, 2022 IEEE Annual Symposium on Foundations of Computer Science, FOCS'ta Best Paper Award aldı
  • Communications of the ACM de bu çalışmayı ele aldı ve Quanta editörleri Kyng algoritmasını 2022'nin bilgisayar bilimindeki en önemli 10 keşfinden biri seçti

Statik ağlardan değişen ağlara

  • İlk algoritma, bağlantı yönlerinin sabit olduğu sabit ve statik ağlara odaklanıyordu
    • Yönlü bağlantılar, şehir yol ağlarındaki tek yönlü yollar gibi bir yapıya sahip
  • Araştırma ekibi daha sonra zaman içinde kademeli olarak değişen ağlarda da en uygun akışı hesaplayan algoritmalar geliştirdi
  • Simon Meierhans, Vancouver'da düzenlenen Annual ACM Symposium on Theory of Computing, STOC'ta yeni neredeyse doğrusal zamanlı algoritmayı sundu
    • Bu algoritma, yeni bağlantıların eklendiği ağlardaki minimum maliyetli maksimum akış problemini çözüyor
  • Ekim ayında IEEE Symposium on Foundations of Computer Science, FOCS'a kabul edilen ikinci makalede ise bağlantı silmelerini de işleyen bir algoritma geliştirildi
  • İki algoritma da bağlantı eklenen veya silinen ağlarda en kısa yolu belirliyor

Gerçek ağ değişimlerine örnekler

  • İsviçre'deki Gotthard Base Tunnel, 2023 yazından sonra tamamen kapatıldı ve ardından kısmen yeniden açıldı
  • Gotthard Road Tunnel için başlıca alternatif güzergâh olan A13 otoyolunun bir bölümü yakın zamanda heyelan nedeniyle tahrip oldu
  • Böyle değişiklikler olduğunda bilgisayarlar, çevrimiçi harita servisleri ve rota planlayıcılar Milan ile Copenhagen arasındaki en düşük maliyetli ve en kısa bağlantıyı yeniden hesaplamak zorunda kalıyor
  • Kyng'in yeni algoritması, bağlantı ekleme ya da silme bulunan ağlarda da en uygun rotayı neredeyse doğrusal zamanda hesaplıyor
  • Dolambaçlı yollar veya yeni güzergâhlar oluşup bağlantılar eklendiğinde de ek hesaplama süresi ihmal edilebilir düzeyde kalıyor

Mevcut iki strateji ve yeni birleştirme yöntemi

  • Ağ akışı hesabı, en uygun akışı ve minimum maliyetli rotayı bulmak için ağı birçok kez analiz etmeyi gerektiriyor
  • Her yinelemede hangi bağlantıların açık ya da kapalı olduğu, kapasite sınırına ulaşıp tıkandığı gibi değişiklikler inceleniyor
  • Kyng'den önce bilgisayar bilimciler çoğunlukla iki stratejiden birini kullanıyordu
    • Demiryolu ağı modeli: her yinelemede trafik akışının değiştiği ağın bir bölümünün tamamı hesaplanıyor
    • Elektrik şebekesi modeli: her yinelemede tüm ağ hesaplanıyor, ancak her bölümdeki değişen akış için istatistiksel ortalama değerler kullanılarak işlem hızlandırılıyor
  • Kyng'in araştırma ekibi iki stratejinin avantajlarını birleştirerek yeni bir karma yaklaşım oluşturdu
  • Maximilian Probst Gutenberg, çok sayıda küçük, verimli ve düşük maliyetli hesaplama adımını birleştirmenin birkaç büyük adımdan çok daha hızlı olduğunu düşünüyor

Akış algoritmalarının tarihsel bağlamı

  • Ağ akışı problemi, 1950'lerde algoritmalarla sistematik biçimde çözülen ilk problemlerden biriydi
  • Akış algoritmaları, kuramsal bilgisayar biliminin bağımsız bir araştırma alanı olarak yerleşmesinde önemli rol oynadı
  • Lester R. Ford Jr. ile Delbert R. Fulkerson'un iyi bilinen algoritması da bu dönemde ortaya çıktı
  • Ford-Fulkerson algoritması, her yolun kapasitesini aşmadan ağ üzerinden mümkün olduğunca çok yük taşımayı amaçlayan maksimum akış problemini verimli biçimde çözüyor
  • Sonraki çalışmalar, maksimum akış problemi, minimum maliyet problemi ve çeşitli ağ akışı problemlerinin genel minimum maliyet akışı probleminin özel durumları olduğunu gösterdi

Önceki algoritmaların sınırları ve 2004 dönüm noktası

  • Kyng'in çalışmasından önceki birçok algoritma belirli tekil problemleri verimli çözebiliyordu, ancak yeterince hızlı değildi ve daha geniş minimum maliyet akışı problemine genişletilmeleri zordu
  • 1970'lerin öncü akış algoritmalarını geliştiren John Edward Hopcroft, Richard Manning Karp ve Robert Endre Tarjan'ın her biri Turing Award aldı
    • Karp ödülü 1985'te aldı
    • Hopcroft ve Tarjan ödülü 1986'da aldı
  • 2004'te Daniel Spielman, Shang-Hua Teng ve daha sonra Samuel Daitch, minimum maliyet akışı problemine de hızlı ve verimli çözüm sunan algoritmalar geliştirdi
  • Bu grup bakış açısını demiryolundan elektrik şebekesindeki güç akışına çevirdi
  • Elektrik şebekesinde akım, başka akımların aktığı bağlantılar üzerinden kısmen yeniden yönlendirilebiliyor
  • Kyng, Spielman'ın tüm ağ için güçlü algoritmik yaklaşımını aynen izlemek yerine, kısmi yol hesaplama fikrini Hopcroft ve Karp'ın önceki yaklaşımına uyguladı
  • Her yinelemede kısmi yolların hesaplanması, tüm akış hesabını hızlandırmada büyük rol oynadı

Yeni matematiksel araçlar ve veri yapıları

  • ETH Zurich araştırma ekibinin ilerlemesi yalnızca yeni algoritmalara değil, hesaplamayı hızlandıran matematiksel araçların tasarımına da dayanıyor
  • Araştırma ekibi, ağ verisini düzenleyen yeni veri yapıları geliştirdi
  • Bu veri yapıları, ağ bağlantılarındaki değişimleri çok hızlı belirlemeyi mümkün kılıyor
  • Değişimleri hızlı tespit etmek, algoritmik çözümün hızını artıran bir unsur olarak işliyor
  • Neredeyse doğrusal zamanlı algoritmalar ve yeni veri yapıları, daha önce verimli biçimde hesaplanamayan çok büyük problemlerin çözümü için temel hazırlıyor

İlgili makaleler ve kaynaklar

İlgili okumalar

1 yorum

 
GN⁺ 2024-06-30
Hacker News yorumları

  • Bu algoritma n -> inf sınırında asimptotik olarak neredeyse doğrusal
    Videonun sonunda, bu algoritmanın herhangi bir gerçek dünya uygulamasının mevcut algoritmaları geçmesinin zor olduğu söyleniyor
    https://cacm.acm.org/research/almost-linear-time-algorithms-...

    • O zaman bu da bir galaktik algoritma mı?
      https://en.wikipedia.org/wiki/Galactic_algorithm
    • Başta beklentiyi iyice yükselttikten sonra epey heves kırıcı
    • Başlığı görür görmez çok şüpheciydim
      Mümkün olan en hızlı hız ifadesi gerçekten iddialı bir sav
    • Böyle durumlarda bir başka ipucu da neredeyse mutlak optimum çözüme ihtiyaç duyulması
      Çoğu zaman zamanın yalnızca %1’ini harcayıp %99 kalite elde etmek çok daha pratik oluyor

  • İlginç biçimde, aynı kişi yalnızca teoriye yönelik algoritmaları pratikte iyi çalışır hale getirme üzerine de araştırma yapıyor [1]
    Ancak bu süreç de yaklaşık 20 yıl sürüyor gibi. [1], 2004’teki teorik atılım [2] üzerine inşa edilmiş; benim anladığım kadarıyla bu algoritmalar ancak 2024’te pratikte çalışmaya başlamış. Öyleyse pratik bir minimum maliyetli akış algoritmasını 2044’te bekleyebiliriz
    [1] https://arxiv.org/pdf/2303.00709
    [2] https://arxiv.org/abs/cs/0310051

  • Almost-Linear-Time Algorithm
    O(mn)’den O(m)’ye gitmek, hesaplamadan N’yi, yani düğüm sayısını çıkarmak anlamına geliyor; kulağa gerçek olamayacak kadar iyi gelmiyor mu?

    • Sabit katsayı o kadar büyük ki, pratik girdilerde asimptotik olarak daha kötü olan mevcut algoritmalardan daha yavaş olacaktır
      Yine de teorik olarak harika bir sonuç

  • Ham sayılara bakmak bile ne kadar yol kat ettiğimizi gösteriyor. 2000’lerden önce hiçbir algoritma m1.5’ten daha hızlı hesaplayamıyordu. Burada m, bilgisayarın hesaplaması gereken ağ bağlantısı sayısını ifade eder ve ağ verisini bir kez okumak bile m zaman alır. 2004’te bu problemi çözmek için gereken hesaplama hızı m1.33’e düştü. Kyng’in algoritmasıyla, ağ verisini okuduktan sonra çözüme ulaşmak için gereken “ek” hesaplama süresi artık ihmal edilebilir düzeyde.
    Orijinal metin Kyng’in atılımını bu kadar önemli tuttuğu m metriği açısından açıklamamış; nedenini merak ediyorum

  • Karmaşıklığı metrik olarak kullanma konusunda tamamen yolu kaybetmişiz gibi hissettiğim zamanlar oluyor
    Karmaşıklık metriklerini giderek çılgın düzeyde optimize eden ama gerçekte faydalı olmayan algoritmaların sayısı artıyor

    • Bu olgu onlarca yıldır var
      Kolay kazanımların hepsi tükendikten sonra algoritma araştırmaları da son derece uzmanlaşmış bir başka alan haline geldi; çok yakın bir alanda çalışan bir araştırmacı değilseniz çoğu makale zaman ayırmaya pek değmez

  • İlgili yazılar: https://news.ycombinator.com/item?id=31149038 (40 yorum)
    https://news.ycombinator.com/item?id=31675015 (72 yorum)

  • Makale ya da kod nerede?

  • Burada kafamı karıştıran bir nokta var: o(n), O(n)’den daha güçlü bir önerme gibi görünüyor
    Çünkü her o(n) algoritması O(n)’dir ama tersi doğru değildir. Ayrıca o(n) ne kadar küçük olursa olsun her n’ye uygulanıyor, O(n) ise yalnızca n -> inf durumunda geçerliyse, bu algoritmanın küçük n’lere de uygulanabilir olması gerekmez mi? O zaman yukarıda sözü edilen galaktik algoritmanın tersi olması gerekmez mi? Bir şeyi mi kaçırıyorum?

    • Küçük o gösterimi de hâlâ asimptotik bir önermedir; bu yüzden küçük n’lere uygulanması gerekmez
      f(n) = o(g(n)) tanımı kabaca lim (n -> infinity) f(n)/g(n) = 0’dır. Başka bir deyişle, yeterince büyük n için g’nin f’den daha hızlı büyüdüğü anlamına gelir
      Örneğin f(n) = 10n if n < 1000 else 1e1000 gibi bir fonksiyon o(n)’dir. n büyüdükçe 1e1000/n, 0’a gider. Bu, n = 1000’e kadar 101000’e üstel olarak artan, sonrasında ise sabit kalan parçalı bir fonksiyonun sözde Python ifadesidir
    • Algoritma karmaşıklığı 3↑↑64*n^0.999 ise bu algoritma o(n)’dir ama gönül rahatlığıyla galaktik algoritma diyebilirsiniz

  • Yanlış hatırlamıyorsam 3↑↑64 Graham sayısı

  • Kahrolası sabit katsayılar, insanın yumruğunu göğe sallayası geliyor

  • Özette yalnızca sürenin m^(1+o(1)) olduğu yazıyor
    Daha somut bir üst sınırın bir yerde verilip verilmediğini bilen var mı?

    • Buradaki o, küçük o; m sonsuza giderken “1’e bölünmüş değer”i 0’a giden terimi yakalar
      https://de.m.wikipedia.org/wiki/Landau-Symbole
    • Bu, istediğiniz kadar O(m)’ye yakın hale getirebilmek için sabitleri seçebileceğiniz anlamına gelir
      Başka bir deyişle, herhangi bir ɛ>1 için O(m^ɛ) zamanda çalışan bir algoritma elde etmenizi sağlayan bir algoritma şemasıdır
    • Somut üst sınır tam da bu
      Küçük o, n sonsuza giderken 0’a yaklaşan bir fonksiyondur ve asimptotik olarak ihmal edilebilir denir