Principiul comun
O retea de flux contine o sursa S, o destinatie T si arce cu capacitati nenegative. Fluxul pe fiecare arc nu poate depasi capacitatea, iar in nodurile intermediare fluxul intrat este egal cu cel iesit.
Fluxul maxim este cantitatea maxima trimisa de la S la T. Teorema flux maxim = capacitatea taieturii minime leaga problema transportului de problema separarii unei retele.
1. Aplicatii ale fluxului maxim in AI
| Nr. | Aplicatie | Ce reprezinta fluxul? | Ce se optimizeaza? |
|---|---|---|---|
| 1 | Segmentarea imaginilor | Flux intr-o retea construita din pixeli | Separarea obiectelor de fundal |
| 2 | Alocarea sarcinilor catre roboti | Sarcini atribuite robotilor | Numarul maxim de sarcini executabile |
| 3 | Alocarea resurselor pentru modele AI | Capacitate de procesare GPU | Numarul maxim de cereri AI procesate |
| 4 | Procesarea limbajului natural | Corespondente intre cuvinte sau concepte | Numarul maxim de asocieri compatibile |
| 5 | Sisteme multi-agent | Sarcini distribuite intre agenti | Numarul maxim de sarcini acoperite |
| 6 | Analiza retelelor sociale | Flux informational posibil intre comunitati | Capacitatea maxima de transmitere |
| 7 | Planificarea transportului cu vehicule autonome | Vehicule care traverseaza o retea rutiera | Numarul maxim de vehicule transportate |
| 8 | Sisteme de recomandare | Recomandari alocate utilizatorilor | Numarul maxim de recomandari compatibile |
Unele aplicatii folosesc direct fluxul maxim, iar altele se modeleaza prin cuplaj maxim sau prin taietura minima.
1. Segmentarea imaginilor: obiect sau fundal?
Problema. Pentru fiecare pixel trebuie sa decidem daca apartine obiectului sau fundalului. Conectam pixelii intre ei si la doua noduri speciale: S (obiect) si T (fundal).
De unde vin capacitatile? Arcele pixel-sursa si pixel-destinatie codifica penalizarea clasificarii acelui pixel intr-o clasa sau alta. Arcele dintre vecini penalizeaza separarea unor pixeli asemanatori (de exemplu, in functie de diferenta de culoare).
Ce calculam? Taietura minima S-T determina clasificarea binara cu cost minim pentru energia reprezentata de retea. Calculul fluxului maxim ofera valoarea acelei taieturi.
2. Alocarea sarcinilor catre roboti
Problema. Avem trei roboti si patru sarcini. Fiecare robot poate executa cel mult o sarcina; fiecare sarcina poate fi atribuita unui singur robot. Nu toti robotii sunt compatibili cu toate sarcinile.
| Robot | Sarcini posibile | Capacitate |
|---|---|---|
| R1 | A, B | 1 |
| R2 | B, C | 1 |
| R3 | A, C, D | 1 |
Modelare. S→robot are capacitatea 1, robot→sarcina exista doar daca robotul poate executa sarcina si are capacitatea 1, iar sarcina→T are capacitatea 1.
Rezultat. Fluxul maxim este 3, de exemplu R1→A, R2→B, R3→D. Sarcina C ramane neatribuita. Nu putem avea flux 4 deoarece doar trei arce de capacitate 1 pleaca din S.
3. Alocarea cererilor AI catre servere GPU
Problema. Un serviciu AI trebuie sa proceseze cereri pentru trei tipuri de modele. Unele servere au suficienta memorie pentru toate modelele, altele doar pentru unele. Dorim sa procesam cat mai multe cereri intr-un minut.
Cereri pe minut
Model M1: 7
Model M2: 6
Model M3: 5
Total: 18
Capacitati servere
GPU1: 5 cereri/min
GPU2: 8 cereri/min
GPU3: 4 cereri/min
Total: 17
Compatibilitati
M1 → GPU1, GPU2
M2 → GPU2, GPU3
M3 → GPU1, GPU3
Reteaua de flux
De unde vin valorile?
Capacitatile 7, 6, 5 de la sursa sunt numarul de cereri sosite pentru fiecare model intr-un minut. Capacitatile 5, 8, 4 catre destinatie sunt numarul maxim de cereri pe care fiecare server le poate procesa intr-un minut. Un arc model→GPU exista numai daca serverul este compatibil cu acel model; capacitatea 18 pe aceste arce nu restrictioneaza suplimentar repartizarea.
Calculul unei alocari optime
| Server | Model M1 | Model M2 | Model M3 | Total |
|---|---|---|---|---|
| GPU1 | 3 | 0 | 2 | 5 |
| GPU2 | 4 | 4 | 0 | 8 |
| GPU3 | 0 | 2 | 2 | 4 |
| Total procesat | 7 | 6 | 4 | 17 |
Rezultat: flux maxim = 17 cereri/minut. Aceasta alocare este realizabila si foloseste toate cele 17 unitati de capacitate GPU. Cum suma capacitatilor serverelor este 17, niciun flux nu poate fi mai mare. O cerere M3 ramane in asteptare.
Comparatie finala
| Aplicatie | Ce inseamna capacitatea? | Ce cautam? |
|---|---|---|
| Segmentare imagine | Penalizare de clasificare sau separare | Taietura minima |
| Alocare roboti | Numar de sarcini alocabile | Flux maxim / cuplaj maxim |
| Procesare GPU | Cereri pe minut | Flux maxim |
| Retea sociala | Intensitatea legaturii | Taietura minima intre A si F |
Ideea esentiala: acelasi algoritm matematic poate rezolva probleme foarte diferite, dar interpretarea capacitatilor trebuie construita separat pentru fiecare problema.
4. Separarea a doua comunitati intr-o retea sociala
Problema. Intr-o retea sociala vrem sa identificam legaturile care separa doi utilizatori reprezentativi, A si F, cu un cost total minim. Nodurile reprezinta utilizatori; capacitatea unui arc exprima forta unei legaturi (de exemplu, o masura a interactiunilor).
Vom considera un graf neorientat: fiecare muchie are o capacitate de separare, iar o taietura plateste acea capacitate o singura data. Pentru calculul fluxului se poate reprezenta fiecare muchie prin doua arce orientate opuse, cu aceeasi capacitate.
Ce inseamna numerele de pe muchii?
Valorile sunt intensitati ipotetice ale legaturilor, nu distante geometrice. De exemplu, legatura A-B are capacitatea 4, B-D are 2, iar C-E are 1. O legatura cu valoare mare este mai costisitor de taiat.
Cum obtinem raspunsul?
Alegem partitionarea {A, B, C} si {D, E, F}. Singurele muchii care trec intre cele doua grupuri sunt B-D (capacitate 2) si C-E (capacitate 1). Capacitatea taieturii este 2 + 1 = 3.
Este si o limita inferioara: exista doua trasee A→B→D→F si A→C→E→F care pot transporta fluxuri 2 si, respectiv, 1. Deci fluxul maxim este cel putin 3. Taietura arata ca nu poate depasi 3. Prin urmare flux maxim = taietura minima = 3.
Experiment: ce se intampla daca intarim legatura B-D?
Modifica valoarea legaturii B-D si observa cum se schimba taietura minima.
Calculul examineaza toate partitionarile posibile cu A in grupul sursei si F in grupul destinatiei.