A kutatók megcáfolják az online algoritmusokkal kapcsolatos széles körben elterjedt hiedelmet | Quanta Magazin

Az életben néha minden kívánt információ nélkül kell döntéseket hoznunk; ez igaz az informatikára is. Ez az online algoritmusok birodalma – amelyek nevük ellenére nem feltétlenül érintik az internetet. Ehelyett olyan problémamegoldó stratégiákról van szó, amelyek úgy reagálnak az adatokra, ahogy azok megérkeznek, anélkül, hogy tudnák, mi jöhet ezután. Az a képesség, hogy megbirkózik a bizonytalansággal, hasznossá teszi ezeket az algoritmusokat valós rejtvények megoldásában, például a laptop memóriájának kezelésében vagy annak kiválasztásában, hogy mely hirdetések jelenjenek meg az interneten böngésző emberek számára.

A kutatók e problémák általánosított változatait tanulmányozzák, hogy új módszereket keressenek a megoldásukra. A leghíresebbek közé tartozik a „k-szerverprobléma”, amely leírja azt a kényes feladatot, hogy ügynökök flottáját küldjék el, hogy egyenként teljesítsék a beérkező kéréseket. Lehetnek javítótechnikusok vagy tűzoltók, vagy akár kóbor fagylaltárusok is.

„Ezt a problémát nagyon egyszerű meghatározni” – mondta Marcin Bieńkowski, a lengyelországi Wrocławi Egyetem algoritmuskutatója. De „bizonyára nehéznek bizonyul”. Amióta a kutatók elkezdték támadni a k-szerverprobléma az 1980-as évek végén, azon tűnődtek, hogy az online algoritmusok pontosan mennyire tudják kezelni a feladatot.

Az évtizedek során a kutatók kezdték azt hinni, hogy létezik egy bizonyos szintű algoritmikus teljesítmény, amelyet mindig elérhet k-szerver probléma. Tehát nem számít, hogy a probléma melyik verziójával foglalkozik, lesz egy algoritmus, amely eléri ezt a célt. De egy tavaly novemberben először online közzétett cikkben három informatikus kimutatta, hogy ez nem mindig érhető el. Egyes esetekben minden algoritmus nem működik.

„Örülök, hogy elmondhatom, hogy ez nagy meglepetés volt számomra” – mondta Anupam Gupta, aki algoritmusokat tanul a Carnegie Mellon Egyetemen, és nem vett részt a dolgozatban. A munka „mélyebb betekintést nyújt e terület központi problémájába”.

Először az informatikusok vázolta ezt a problémát 1988-ban. Hogy megértsük, képzeljünk el egy céget, amely vízvezeték-szerelőket alkalmaz. Amint beérkeznek a hívások, a cégnek el kell döntenie, hogy melyik vízvezeték-szerelő melyik helyre megy. A vállalat célja – és egy algoritmus célja a k-szerver probléma – az összes vízvezeték-szerelő által megtett távolság minimalizálása.

A trükkös rész az, hogy a cég nem tudja előre, honnan érkeznek a hívások. Ha igen, akkor egy „offline algoritmusra” támaszkodhatna, amely ismeri a jövőt. Konkrétan olyan ideális elosztási stratégiát alkalmazhat, amely a legkevesebb teljes utazással rendelkező megoldást találja bármely hívássorozatra. Egyetlen online algoritmus sem tudja legyőzni, vagy akár megbízhatóan sem tud megfelelni.

A kutatók azonban a lehető legközelebb akarnak kerülni. Egy online algoritmus teljesítményét úgy mérik, hogy összehasonlítják az egyes stratégiákban megtett távolságot, és kiszámítják az úgynevezett versenyképességi arányt. Az algoritmustervezők olyan online stratégiákat próbálnak kidolgozni, amelyek megközelítik az offline ideálist, és ezt az arányt 1-re csökkentik.

Képzeljük el, hogy a vízvezeték-szerelő cégünknek csak két vízvezeték-szerelője van, és csak egyetlen, hosszú utcát szolgál ki. A hívások egyenként jönnek. A mohó algoritmusként ismert ésszerű első megközelítés az lenne, ha minden bejövő hívás helyéhez legközelebb lévő vízvezeték-szerelőt küldik el. De itt van egy forgatókönyv, ahol ez az algoritmus nehézségekbe ütközik: Képzeld el, hogy az egyik vízvezeték-szerelő az utca nyugati végén, a másik a keleti végén indul, és az összes hívás két szomszédos házból érkezik a nyugati végén. Ebben az esetben az egyik vízvezeték-szerelő soha nem mozdul, míg a másik a két háznál gyűjti a mérföldeket. Utólag visszagondolva a legjobb stratégia az lett volna, ha mindkét vízvezeték-szerelőt a problémás területre költöztetik – de sajnos nem tudhatta volna, hogy ez hol lesz.

Bieńkowski szerint ennek ellenére is lehet jobbat csinálni, mint a mohó algoritmus. A "dupla lefedettség” algoritmus mindkét vízvezeték-szerelőt azonos sebességgel mozgatja a közéjük eső hívások felé, amíg az egyikük el nem éri azt. Ez a módszer alacsonyabb versenyképességi arányt ér el, mint a mohó algoritmus.

Bár ez az elvont probléma nem releváns a valódi vízvezeték-szerelő cégek számára, „a k-Maga a szerverprobléma a meghatározó kérdés” – mondta az online számítástechnikában Yuval Rabani, a Jeruzsálemi Héber Egyetem informatikusa, aki a legutóbbi tanulmány társszerzője. Részben ennek az az oka, hogy az eszközök és technikák a munka során fejlődtek ki k-Server probléma gyakran talál alkalmazást máshol az online algoritmusok tanulmányozásában, sőt azon kívül is.

„Ez része az algoritmusokon való munka varázsának” – mondta.

Amikor ezeket a problémákat tanulmányozzák, a tudósok úgy képzelik el őket, mint egy ellenfél elleni játékot. Az ellenfél a kérések ördögi sorozatát választja, hogy az online algoritmus a lehető legrosszabbul teljesítsen offline megfelelőjéhez képest. Az ellenfél hatalmának egy részét megfosztandó kutatók olyan algoritmusokat használnak, amelyek magukban foglalják véletlenszerű döntések.

Ez a stratégia meglehetősen hatékony, és a kutatók az 1990-es évek eleje óta azt gyanítják, hogy mindig lehet találni egy véletlenszerű algoritmust, amely elér egy adott teljesítménycélt: a logóval arányos versenyképességi arányt. k, Ahol k az ügynökök száma. Ezt véletlenszerűnek nevezik k-szerver sejtései, és a kutatók kimutatták, hogy ez bizonyos terekre vagy meghatározott pontgyűjteményekre igaz (a házak megfelelője, amelyek vízvezeték-szerelőket igényelhetnek). De ez nem minden esetben bizonyított.

A legtöbb kutatóhoz hasonlóan Rabani és szerzőtársai – Sébastien Bubeck a Microsoft Research és Christian Coester az Oxfordi Egyetemen – úgy vélte, a sejtés igaz. „Nem volt okom kételkedni benne” – mondta Coester.

De ez megváltozni kezdett, ahogy egy másik online problémán dolgoztak. Volt kapcsolata a k-szerver probléma, és a versenyképességi arány ismert alsó határa váratlanul magas volt. Arra késztette őket, hogy egy olyan alacsony célt érjenek el, mint a log k az k-A szerver probléma túlságosan optimista volt.

Rabani azt mondta, Coester volt az, aki először javasolta, hogy a véletlenszerűsítést k-A szerver sejtése hamis lehet. – Amint kimondta, mindennek volt értelme.

A feltételezés megcáfolására a szerzők az ellenfél szerepét játszották, és tökéletes vihart hoztak létre, amely megakadályozza, hogy bármely online algoritmus elérje a naplózás versenyképes arányát. k. Stratégiájuk két részből állt: Összeállítottak egy összetett, fraktálszerű terek családját, és megtervezték a kéréssorozatok olyan eloszlását, amely bármilyen lehetséges algoritmus számára nehéz lenne. Az algoritmus legelső lépésénél a tér szerkezete azt jelentette, hogy két azonos út közül kellett választania, amelyek közül az egyik végül többletutazást igényel a kérések alapján. Ezután a szerzők egy rekurziónak nevezett módszert alkalmaztak olyan terek létrehozására, amelyek megsokszorozták ezeket a döntési pontokat, rossz opciók halmazára kényszerítve az algoritmust, és megnövelték a költségeket.

A választások Rabanit Robert Frost versére emlékeztették.A meg nem tett út,”, amelyben egy utazó két lehetséges utat szemlél egy sárga fán keresztül. „Csak rekurzívan alkalmazzuk a verset” – viccelődött. – És akkor a dolgok nagyon rosszra fordulnak.

A szerzők kimutatták, hogy az általuk megszerkesztett terekben egy randomizált algoritmus soha nem tud jobb versenyképességi arányt elérni, mint (log k)², a log univerzális céljának elérése érdekében k örökre elérhetetlen. Megcáfolták a sejtést.

Ez a munka, amely megnyerte a A legjobb papír díja a 2023 Számítástechnikai Szimpózium, egy „szilárd elméleti” mérföldkövet jelent, mondta Gupta. Ez a fajta eredmény segít megmutatni, hogy milyen teljesítményt remélhetünk algoritmusainktól. A gyakorlatban azonban az algoritmustervezők gyakran nem a legrosszabb forgatókönyvek körül terveznek, mindenható ellenféllel és teljes tudatlansággal a jövővel kapcsolatban. Amikor az algoritmusokat valós problémákra szabadítják fel, azok gyakran meghaladják az elméleti elvárásokat.

A cikk, amely szintén bebizonyította, hogy az egyéb problémákhoz használt véletlenszerű algoritmusok határértékei vannak, szintén hatással lehet a területen végzett jövőbeni munkára. Az eredmény egyértelműen „kiemeli a szerzők által alkalmazott technika erejét”, mondta Gupta.

Lehet, hogy ezek a jövőbeni eredmények szembemennek a kutatók várakozásaival, ahogyan ez is tette, mondta Rabani. "Ez az egyik olyan eset, amikor nagyon jó érzés tévedni."

Quanta felméréssorozatot végez közönségünk jobb kiszolgálása érdekében. Vidd a miénket számítástechnikai olvasói felmérés és ingyenesen nyerhetsz Quanta áru.