Cercetătorii resping o credință larg răspândită despre algoritmii online | Revista Quanta

În viață, uneori trebuie să luăm decizii fără toate informațiile pe care ni le dorim; asta e valabil si in informatica. Acesta este tărâmul algoritmilor online – care, în ciuda numelui lor, nu implică neapărat internetul. În schimb, acestea sunt strategii de rezolvare a problemelor care răspund la datele pe măsură ce sosesc, fără nicio cunoaștere a ceea ce ar putea urma. Această capacitate de a face față incertitudinii face ca acești algoritmi să fie folositori pentru enigmele din lumea reală, cum ar fi gestionarea memoriei pe un laptop sau alegerea reclamelor pentru a afișa persoanelor care navighează pe web.

Cercetătorii studiază versiuni generalizate ale acestor probleme pentru a investiga noi metode de abordare a acestora. Printre cele mai faimoase este „k-problema serverului”, care descrie sarcina spinoasă de a trimite o flotă de agenți pentru a îndeplini cererile care vin pe rând. Ar putea fi tehnicieni de reparații sau pompieri sau chiar vânzători ambulanți de înghețată.

„Este foarte simplu să definești această problemă”, a spus Marcin Bieńkowski, un cercetător în algoritmi la Universitatea din Wrocław din Polonia. Dar „se dovedește a fi bizar de dificil”. De când cercetătorii au început să atace k-cu problema serverului la sfârșitul anilor 1980, ei s-au întrebat exact cât de bine se pot descurca algoritmii online.

De-a lungul deceniilor, cercetătorii au început să creadă că există un anumit nivel de performanță algoritmică pe care îl puteți obține întotdeauna pentru k-problema cu serverul. Deci, indiferent de versiunea problemei cu care aveți de-a face, va exista un algoritm care atinge acest obiectiv. Dar într-o lucrare publicată pentru prima dată online în noiembrie anul trecut, trei informaticieni a arătat că acest lucru nu este întotdeauna realizabil. În unele cazuri, fiecare algoritm este scurt.

„Sunt bucuros să spun că a fost o mare surpriză pentru mine”, a spus Anupam Gupta, care studiază algoritmi la Universitatea Carnegie Mellon și nu a fost implicat în lucrare. Lucrarea oferă „o perspectivă mai profundă asupra problemei centrale din acest domeniu”.

Mai întâi informaticienii a subliniat această problemă în 1988. Pentru a ne înțelege, să ne imaginăm o companie care angajează instalatori. Pe măsură ce sosesc apelurile, compania trebuie să decidă ce instalator merge în ce locație. Scopul companiei — și scopul unui algoritm pentru k-problema serverului — este de a minimiza distanța totală parcursă de toți instalatorii.

Partea dificilă este că compania nu știe dinainte de unde vor veni apelurile. Dacă a făcut-o, atunci s-ar putea baza pe un „algoritm offline” care cunoaște viitorul. În special, ar putea folosi o strategie de dispecerare ideală care găsește o soluție cu cea mai mică călătorie totală pentru orice șir de apeluri. Niciun algoritm online nu îl poate învinge vreodată sau chiar poate să-l potrivească în mod fiabil.

Dar cercetătorii vor să se apropie cât mai mult posibil. Ei măsoară performanța unui algoritm online comparând distanța de călătorie în fiecare strategie, calculând ceea ce este cunoscut sub numele de raportul competitiv. Designerii de algoritmi încearcă să creeze strategii online care se apropie de idealul offline, reducând acest raport la 1.

Să ne imaginăm că compania noastră de instalații sanitare are doar doi instalatori și deservește doar o singură stradă lungă. Apelurile vin pe rând. O primă abordare rezonabilă, cunoscută sub numele de algoritmul lacom, ar fi să trimiți orice instalator este cel mai aproape de locația fiecărui apel primit. Dar iată un scenariu în care acest algoritm se luptă: imaginați-vă că un instalator începe la capătul de vest al străzii și celălalt la capătul de est și toate apelurile vin de la două case învecinate la capătul de vest. În acest caz, un instalator nu se mișcă niciodată, în timp ce celălalt acumulează kilometri la acele două case. Privind retrospectiv, cea mai bună strategie ar fi fost să mutați ambii instalatori în zona predispusă la probleme - dar, din păcate, nu ați fi putut ști unde va fi asta.

Chiar și așa, a spus Bieńkowski, este posibil să faci mai bine decât algoritmul lacom. „acoperire dublăAlgoritmul mută ambii instalatori în același ritm către orice apel care se încadrează între ei, până când unul dintre ei ajunge la el. Această metodă realizează un raport competitiv mai mic decât algoritmul lacom.

Deși această problemă abstractă nu este relevantă pentru companiile de instalații sanitare reale, „the k-Problema serverului în sine este într-adevăr întrebarea definitorie” în calculul online, a spus Yuval Rabani, un informatician la Universitatea Ebraică din Ierusalim, care a fost coautor al lucrării recente. În parte, asta se datorează faptului că instrumentele și tehnicile dezvoltate în timpul lucrului la k-Problema serverului găsesc adesea aplicații în altă parte în studiul algoritmilor online, și chiar în afara acestuia.

„Aceasta face parte din magia lucrului la algoritmi”, a spus el.

Când studiază aceste probleme, oamenilor de știință le place să le imagineze ca pe niște jocuri împotriva unui adversar. Adversarul alege o secvență diabolică de solicitări pentru a face algoritmul online să funcționeze cât mai rău posibil în comparație cu omologul său offline. Pentru a jefui adversarul de o parte din puterea sa, cercetătorii folosesc algoritmi care includ decizii aleatorii.

Această strategie este destul de eficientă, iar cercetătorii au bănuit încă de la începutul anilor 1990 că poți găsi întotdeauna un algoritm randomizat care atinge un anumit obiectiv de performanță: un raport competitiv proporțional cu log. k, În cazul în care k este numărul de agenți. Aceasta se numește randomizat k-conjectura serverului, iar cercetatorii au aratat ca este adevarat pentru unele spatii, sau colectii specifice de puncte (echivalentul caselor care ar putea apela la instalatori). Dar nu a fost dovedit pentru toate cazurile.

La fel ca majoritatea cercetătorilor, Rabani și coautorii săi - Sébastien Bubeck al Microsoft Research și Christian Coester de la Universitatea din Oxford — sa gândit că presupunerea era adevărată. „Nu aveam de ce să mă îndoiesc”, a spus Coester.

Dar asta a început să se schimbe pe măsură ce au lucrat la o altă problemă online. Avea conexiuni cu k-problema de server, iar limita inferioară cunoscută a raportului competitiv a fost neașteptat de mare. I-a făcut să se gândească, poate, la un obiectiv la fel de jos k pentru k-problema serverului a fost prea optimista.

Rabani a spus că Coester a fost cel care a sugerat primul că a fost randomizat k-conjectura serverului ar putea fi falsă. „De îndată ce a spus-o, totul a avut sens.”

Pentru a infirma presupunerea, autorii au jucat rolul adversarului, creând o furtună perfectă care ar împiedica orice algoritm online să atingă un raport competitiv de log k. Strategia lor a avut două părți: au construit o familie de spații complexe, asemănătoare fractale și au proiectat o distribuție de secvențe de solicitare care ar fi dificilă pentru orice posibil algoritm. La prima mișcare a algoritmului, structura spațiului a însemnat că trebuie să aleagă între două căi identice, dintre care una ar necesita în cele din urmă călătorii suplimentare în funcție de solicitări. Apoi, autorii au folosit o metodă numită recursie pentru a construi spații care au multiplicat aceste puncte de decizie, forțând algoritmul într-o grămadă de opțiuni proaste și crescând costurile.

Alegerile i-au adus aminte lui Rabani de poezia lui Robert Frost „Drumul neluat,” în care un călător contemplă două potențiale căi printr-un pădure galben. „Aplicăm recursiv poemul”, a glumit el. „Și atunci lucrurile merg foarte prost.”

Autorii au arătat că, în spațiile pe care le-au construit, un algoritm randomizat nu poate atinge niciodată un raport competitiv mai bun decât (log k)², împingând un obiectiv universal de log k pentru totdeauna la îndemână. Ei infirmaseră presupunerea.

Această lucrare, care a câștigat un Premiul pentru cea mai bună hârtie de la 2023 Simpozion despre teoria calculului, marchează o piatră de hotar „solid teoretică”, a spus Gupta. Acest tip de rezultat ajută la indicarea tipului de performanță la care putem spera de la algoritmii noștri. În practică, totuși, designerii de algoritmi adesea nu planifică în jurul scenariilor cele mai defavorabile, cu un adversar atotputernic și ignoranță completă a viitorului. Atunci când algoritmii sunt dezlănțuiți pentru probleme din lumea reală, ei depășesc adesea așteptările teoretice.

Lucrarea, care a dovedit, de asemenea, limite pentru algoritmii randomizati utilizați pentru alte probleme, ar putea avea, de asemenea, implicații pentru lucrările viitoare în domeniu. Rezultatul „subliniază în mod clar puterea” tehnicii folosite de autori, a spus Gupta.

Poate că acele descoperiri viitoare vor sfida așteptările cercetătorilor, așa cum a făcut aceasta, a spus Rabani. „Acesta este unul dintre cazurile în care se simte foarte bine să greșești.”

Cuante efectuează o serie de sondaje pentru a servi mai bine publicul nostru. Ia-ne sondaj cititor de informatică și vei fi înscris pentru a câștiga gratuit Cuante mărfuri.