Hayatta bazen istediğimiz tüm bilgiler olmadan kararlar vermek zorunda kalırız; bu bilgisayar bilimleri için de geçerlidir. Bu, adlarına rağmen mutlaka interneti kapsamayan çevrimiçi algoritmaların alanıdır. Bunun yerine bunlar, daha sonra ne olabileceğine dair herhangi bir bilgi olmadan, verilere ulaştıkça yanıt veren problem çözme stratejileridir. Belirsizlikle başa çıkabilme yeteneği, bu algoritmaları, bir dizüstü bilgisayarın belleğini yönetmek veya internette gezinen kişilere hangi reklamların gösterileceğini seçmek gibi gerçek dünyadaki bilmeceler için yararlı kılar.

Araştırmacılar, bu sorunların üstesinden gelmek için yeni yöntemler araştırmak amacıyla bu sorunların genelleştirilmiş versiyonlarını inceliyorlar. Bunlardan en ünlüsü “k-sunucu sorunu”, birer birer gelen istekleri yerine getirmek için bir ajan filosu göndermenin zorlu görevini anlatıyor. Tamir teknisyenleri, itfaiyeciler ve hatta gezici dondurma satıcıları bile olabilirler.

"Bu sorunu tanımlamak gerçekten çok basit" dedi Marcin BieńkowskiPolonya'daki Wrocław Üniversitesi'nde algoritma araştırmacısı. Ancak bunun "tuhaf derecede zor olduğu ortaya çıktı." Araştırmacılar saldırmaya başladığından beri k1980'lerin sonundaki sunucu sorunu nedeniyle, çevrimiçi algoritmaların bu görevi tam olarak ne kadar iyi yerine getirebileceğini merak ettiler.

Onlarca yıl boyunca araştırmacılar, her zaman elde edebileceğiniz belirli bir algoritmik performans düzeyi olduğuna inanmaya başladı. k-sunucu sorunu. Yani problemin hangi versiyonuyla uğraşırsanız uğraşın, bu hedefe ulaşan bir algoritma olacaktır. Ancak ilk kez geçtiğimiz Kasım ayında internette yayınlanan bir makalede üç bilgisayar bilimcisi gösterdi bu her zaman başarılamaz. Bazı durumlarda her algoritma yetersiz kalabilir.

"Bunun benim için büyük bir sürpriz olduğunu söylemekten mutluyum" dedi Anupam GuptaCarnegie Mellon Üniversitesi'nde algoritmalar üzerine çalışan ve makaleye dahil olmayan. Çalışma "bu alandaki merkezi soruna daha derin bir bakış açısı" sunuyor.

Bilgisayar bilimcileri ilk sırada bu sorunu özetledim Bunu anlamak için tesisatçı çalıştıran bir şirket hayal edelim. Aramalar geldikçe şirketin hangi tesisatçının hangi lokasyona gideceğine karar vermesi gerekiyor. Şirketin hedefi ve bir algoritmanın hedefi k-sunucu problemi - tüm tesisatçıların kat ettiği toplam mesafeyi en aza indirmektir.

İşin zor kısmı, şirketin çağrıların nereden geleceğini önceden bilmemesidir. Eğer öyleyse, geleceği bilen bir "çevrimdışı algoritmaya" güvenebilirdi. Özellikle, herhangi bir arama dizisi için en az toplam seyahat ile çözüm bulan ideal bir dağıtım stratejisi kullanabilir. Hiçbir çevrimiçi algoritma onu yenemez, hatta güvenilir bir şekilde eşleştiremez.

Ancak araştırmacılar mümkün olduğunca yaklaşmak istiyor. Çevrimiçi bir algoritmanın performansını, her stratejideki seyahat mesafesini karşılaştırarak ve rekabet oranı olarak bilinen şeyi hesaplayarak ölçerler. Algoritma tasarımcıları, bu oranı 1'e indirerek çevrimdışı ideale yaklaşan çevrimiçi stratejiler oluşturmaya çalışıyor.

Tesisat şirketimizin yalnızca iki tesisatçısı olduğunu ve yalnızca tek, uzun bir caddeye hizmet verdiğini düşünelim. Çağrılar birer birer geliyor. Açgözlü algoritma olarak bilinen makul bir ilk yaklaşım, gelen her çağrının konumuna en yakın tesisatçıyı yönlendirmek olacaktır. Ancak bu algoritmanın zorlandığı bir senaryo var: Bir tesisatçının sokağın batı ucunda, diğerinin doğu ucunda başladığını ve tüm çağrıların batı ucundaki iki komşu evden geldiğini düşünün. Bu durumda, bir tesisatçı hiç hareket etmezken diğeri bu iki eve kilometrelerce yol katediyor. Geriye dönüp bakıldığında, en iyi strateji her iki tesisatçıyı da sorunlu bölgeye taşımak olurdu - ama ne yazık ki bunun nerede olacağını bilemezdiniz.

Öyle bile olsa Bieńkowski, açgözlü algoritmadan daha iyisini yapmanın mümkün olduğunu söyledi. “çift ​​kapsamaAlgoritma, her iki tesisatçıyı da aralarında kalan herhangi bir çağrıya, içlerinden biri ulaşana kadar aynı hızda hareket ettirir. Bu yöntem, açgözlü algoritmaya göre daha düşük bir rekabet oranına ulaşır.

Bu soyut sorun gerçek tesisat şirketleriyle ilgili olmasa da, " k-sunucu sorununun kendisi gerçekten çevrimiçi bilgi işlemde belirleyici sorudur" dedi. Yuval RabaniSon makalenin ortak yazarlarından biri olan Kudüs İbrani Üniversitesi'nden bir bilgisayar bilimcisi. Bunun nedeni kısmen, proje üzerinde çalışma sırasında geliştirilen araç ve tekniklerin k-sunucu sorunu sıklıkla çevrimiçi algoritmaların incelenmesinde başka yerlerde ve hatta bunun dışında da uygulamalar bulur.

"Bu, algoritmalar üzerinde çalışmanın büyüsünün bir parçası" dedi.

Bilim insanları bu sorunları incelerken bunları bir rakibe karşı oynanan oyunlar olarak hayal etmeyi seviyorlar. Düşman, çevrimiçi algoritmanın çevrimdışı algoritmaya kıyasla mümkün olduğunca kötü performans göstermesini sağlamak için şeytani bir istek dizisi seçer. Düşmanın gücünün bir kısmını çalmak için araştırmacılar aşağıdakileri içeren algoritmalar kullanıyor: rastgele kararlar.

Bu strateji oldukça etkilidir ve araştırmacılar 1990'ların başından bu yana her zaman belirli bir performans hedefine ulaşan rastgeleleştirilmiş bir algoritma bulabileceğinizden şüpheleniyorlar: log ile orantılı rekabetçi bir oran. k, Burada k acente sayısıdır. Buna randomize denir k-sunucu varsayımı ve araştırmacılar bunun bazı alanlar veya belirli nokta koleksiyonları (tesisatçı gerektirebilecek evlerin eşdeğeri) için doğru olduğunu gösterdi. Ancak her durumda kanıtlanmamıştır.

Çoğu araştırmacı gibi Rabani ve ortak yazarları da — Sebastien Bubeck Microsoft Araştırma ve Christian Coester Oxford Üniversitesi'nden - varsayımın doğru olduğunu düşündü. Coester, "Bundan şüphe etmek için hiçbir nedenim yoktu" dedi.

Ancak başka bir çevrimiçi sorun üzerinde çalıştıkça bu durum değişmeye başladı. ile bağlantıları vardı k-sunucu sorunu vardı ve rekabet oranının bilinen alt sınırı beklenmedik derecede yüksekti. Bu onların belki de kütük kadar düşük bir hedef olduğunu düşündürdü k için k-sunucu sorunu aşırı iyimserdi.

Rabani, randomize yöntemi ilk önerenin Coester olduğunu söyledi. k-sunucu varsayımı yanlış olabilir. "Bunu söylediği anda her şey mantıklı geldi."

Bu varsayımı çürütmek için yazarlar, herhangi bir çevrimiçi algoritmanın rekabetçi bir log oranına ulaşmasını engelleyecek mükemmel bir fırtına yaratarak rakibi oynadılar. k. Stratejileri iki bölümden oluşuyordu: Karmaşık, fraktal benzeri uzaylardan oluşan bir aile oluşturdular ve herhangi bir olası algoritma için zor olacak istek dizilerinin bir dağılımını tasarladılar. Algoritmanın ilk hamlesinde alanın yapısı, iki özdeş yol arasında seçim yapması gerektiği anlamına geliyordu; bu yollardan biri, isteklere bağlı olarak eninde sonunda fazladan seyahat gerektirecekti. Daha sonra yazarlar, bu karar noktalarını çoğaltan alanlar oluşturmak için özyineleme adı verilen bir yöntem kullandılar, bu da algoritmayı kötü seçenekler batağına sürükledi ve maliyeti artırdı.

Seçimler Rabani'ye Robert Frost'un şiirini hatırlattı:Alınmayan Yol,Bir gezginin sarı bir ormanın içinden geçen iki potansiyel yolu düşündüğü hikaye. "Sadece şiiri yinelemeli olarak uyguluyoruz" diye şaka yaptı. “Sonra işler gerçekten kötüye gidiyor.”

Yazarlar, inşa ettikleri alanlarda rastgeleleştirilmiş bir algoritmanın hiçbir zaman (log k)², evrensel bir kütük hedefini zorluyor k sonsuza dek ulaşılmaz. Bu varsayımı yalanlamışlardı.

Ödül kazanan bu çalışma En İyi Kağıt Ödülü at 2023 Hesaplama Teorisi SempozyumuGupta, bunun "sağlam teorik" bir dönüm noktasına işaret ettiğini söyledi. Bu tür bir sonuç, algoritmalarımızdan ne tür bir performans bekleyebileceğimizi göstermeye yardımcı olur. Ancak uygulamada, algoritma tasarımcıları genellikle her şeye gücü yeten bir düşmanla ve geleceğe dair tamamen bilgisizlikle en kötü senaryolara göre plan yapmıyorlar. Algoritmalar gerçek dünya sorunlarına uygulandığında genellikle teorik beklentileri aşarlar.

Diğer problemler için kullanılan rastgeleleştirilmiş algoritmalar için de kesintileri kanıtlayan makale, bu alanda gelecekte yapılacak çalışmalara da katkı sağlayabilir. Gupta, sonucun yazarların kullandığı tekniğin "gücünü açıkça vurguladığını" söyledi.

Rabani, belki de gelecekteki bulguların araştırmacıların beklentilerine meydan okuyacağını söyledi. “Bu, yanılmanın gerçekten iyi hissettirdiği durumlardan biri.”

Kuantum izleyicilerimize daha iyi hizmet verebilmek için bir dizi anket yürütüyor. Bizimkini al bilgisayar bilimi okuyucu anketi ve ücretsiz kazanmak için girileceksiniz Kuantum mal.