Ce se mai intâmplã in informatica teoreticã: un nou algoritm pentru fluxuri in reţele

[credit:  o ştire pe blogul lui Michael Mitzenmacher.]

Problema fluxului in reţele de transport este una clasicã in optimizarea combinatorialã, predatã in toatã lumea studenţilor de la informaticã in cursurile de algoritmicã.

Pentru puţinii dintre voi, bãnuiesc 🙂 , care n-au intâlnit-o pânã acum, iatã o scurtã recapitulare:

Ce ne este dat(ã) ? Pe scurt, o reţea de transport (un graf orientat cu douã noduri speciale, sursã şi destinaţie). Fiecare muchie are o capacitate, un numãr real mai mare sau egal cu zero, reprezentând cantitatea maximã dintr-un „fluid” pe care o putem transporta de-a lungul muchiei respective. Am spus „fluid” pentru cã e vorba de o cantitate care variazã in mod continuu (numãrul de oameni transportaţi de un tren, de exemplu, nu satisface proprietatea asta :))

center

Exemplu de reţea de transport/flux. Credit: Wikipedia. Primul numãr pe o muchie este (in caz cã nu ştiaţi :)) valoarea fluxului, cel de-al doilea reprezintã capacitatea muchiei. Un flux pozitiv, privit „in direcţia opusã a muchiei” are valoare negativã (valoarea opusã)

Ce se cere ? Sã gãsim o metodã de a transporta o cantitate maximã de fluid de la sursã la destinaţie.

Algoritmii cei mai cunoscuţi pentru problema fluxului maxim sunt algoritmul lui Ford-Fulkerson, (cu varianta de implementare Edmonds-Karp), respectiv algoritmi de tip „push-relabel”. Eu ii predam acum câţiva ani intr-un curs opţional in englezã la UVT (informaticã, anul 2).

Faptul cã algoritmii de mai sus sunt cei mai cunoscuţi nu ii face şi optimi. Numãrul de paşi ai celor doi algoritmi poate fi mãrginit superior de

  • o constantã inmulţitã cu VE^2 pentru algoritmul Ford-Fulkerson-Edmonds-Karp. V e numãrul de vârfuri ale reţelei de transport iar E e numãrul de muchii.
  • o constantã inmulţitã cu {\bf V^2}E, pentru algoritmul push-relabel, sau chiar cu V^3, când este implementat cu o euristicã suplimentarã. In general pentru reţele de transport V\leq E, prin urmare marginile de mai sus sunt din ce in ce mai bune.

Rezolvând o problemã care a stat deschisã mult timp, James Orlin a gãsit recent un algoritm cu complexitatea O(VE). Pentru a aprecia de ce meritã sã scrii despre un algoritm cu complexitatea asta pe blog :), poate meritã spus cã problema inchiderii tranzitive a unui graf orientat (sã determinãm „unde putem ajunge” pornind dintr-un nod arbitrar in graf) necesitã complexitatea asta. Din cauza asta progresul realizat de noul algoritm e unul semnificativ.

De ce sunt interesaţi cei care lucreazã in algoritmicã de algoritmi cu complexitãţi „optime”, mai ales cã de multe ori constantele ascunse in analizã ii face impractici ? Simplu: analiza unor astfel de algoritmi pune in luminã de multe ori care sunt „cele mai grele pãrţi ale unei probleme”, ghidând cercetarea spre rezolvarea acestor probleme. De multe ori abordarea acestor probleme cu metode diferite (de exemplu algoritmi probabilişti sau de aproximare) conduce pânã la urmã la algoritmi cu valoare practicã. Am vãzut schema asta repetându-se de mai multe ori, prin urmare nu e vorba de o simplã abordare „filosoficã” a complexitãţii algoritmilor 🙂

Despre algoritmul lui Orlin nu vã mai pot spune din pãcate acum prea multe, plec in curând la o conferinţã, prin urmare timpul meu este relativ limitat. Vreau doar sã remarc faptul cã noua metodã foloseşte drept ingredient unii algoritmi recenţi (cei mai buni cunoscuţi in prezent) pentru multiplicarea matricilor, o problemã despre care am amintit pe scurt aici. Vã puteţi insã face singuri o impresie urmãrind o prezentare video a autorului despre noul algoritm.

Anunțuri
Acest articol a fost publicat în informaticã teoreticã, popularizarea_ştiinţei, Uncategorized. Pune un semn de carte cu legătura permanentă.

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s