Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Flux cu numar minim de muchii  (Citit de 4727 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
amadaeus
Client obisnuit
**

Karma: 28
Deconectat Deconectat

Mesaje: 93



Vezi Profilul
« : Aprilie 25, 2008, 22:14:32 »

Fiind data o retea de transport, se pune problema gasirii fluxului maxim de la S la T, iar dintre toate variantele, aceea care foloseste un numar cat mai mic de muchii pentru transport. Ma gandeam de ceva timp daca algoritmul Edmonds-Karp, alegand de fiecare data drumul de ameliorare cu numarul minim de muchii, garanteaza in final o solutie corecta a problemei Confused
Memorat

"one of these days I'm going to cut you into little pieces..."
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #1 : Aprilie 25, 2008, 22:25:32 »

Aduni la fiecare muchie valoarea |E| + 1, unde |E| e cardinalul multimii muchiilor. Taietura minima va contine un numar minim de muchii.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
amadaeus
Client obisnuit
**

Karma: 28
Deconectat Deconectat

Mesaje: 93



Vezi Profilul
« Răspunde #2 : Aprilie 25, 2008, 22:39:01 »

Taietura minima contine un numar minim de muchii si daca toate muchiile au capacitate 1 Smile Problema e cum circula fluxul de la S pana la muchiile din taietura, si de la muchiile din taietura la T. Dintre toate taieturile minime, ar trebui aleasa aceea care optimizeaza "traficul" in sensul numarului de muchii folosite in afara ei.
Memorat

"one of these days I'm going to cut you into little pieces..."
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #3 : Aprilie 25, 2008, 22:51:05 »

Eu ma refeream la ideea prezentata aici  http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2 in al patrulea desen.

Defapt, desenul arata o contradictie. Textul de deasupra si de sub el trebuie citit.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #4 : Aprilie 25, 2008, 22:57:50 »

Citat
Aduni la fiecare muchie valoarea |E| + 1, unde |E| e cardinalul multimii muchiilor. Taietura minima va contine un numar minim de muchii.

 Din articolul de mai sus eu am inteles ca iei fiecare si inmultesti cu |E| si apoi aduni 1.

In plus el se refera ca vrea sa trimita fluxul in asa fel incat numarul de muchii x y, cu f[ x] [y]>0 sa fie minim. (unde f[ x ][y]  este fluxul trimis pe muchia x y).
Memorat
byndrsn
Client obisnuit
**

Karma: 19
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #5 : Aprilie 25, 2008, 23:12:14 »

Capacitatile sunt arbitrare sau doar 0/1?
Memorat
amadaeus
Client obisnuit
**

Karma: 28
Deconectat Deconectat

Mesaje: 93



Vezi Profilul
« Răspunde #6 : Aprilie 25, 2008, 23:16:12 »

Defapt, desenul arata o contradictie. Textul de deasupra si de sub el trebuie citit.

Desenul mi se pare in concordanta cu ce scrie in articol: arata ca daca inmultesti toate capacitatile cu o valoare T si aduni 1, taietura minima din graful original nu este neaparat taietura minima in graful nou obtinut.

Eu am inteles articolul la fel ca Tiberiu, ar trebui sa inmultesti fiecare muchie cu |E| (de fapt e destul sa inmultesti cu numarul maxim de muchii ce pot aparea intr-o taietura minima a grafului original) si apoi sa aduni 1, ca sa te asiguri de minimalitatea numarului de muchii din taietura.
Citat
Notice what happens if we multiply each edge capacity with a constant T [...] to generalize, we take T = 10, one more than the number of edges in the original network, and one more than the number of edges that could possibly be in a minimum-cut.

@Alina: Eu ma gandeam cu capacitati arbitrare, dar as fi curios si de o analiza pe cazul particular 0/1
Memorat

"one of these days I'm going to cut you into little pieces..."
byndrsn
Client obisnuit
**

Karma: 19
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #7 : Aprilie 25, 2008, 23:30:21 »

@Lucian: Cred ca in cazul in care capacitatile sunt 0/1, numarul de muchii folosite e intotdeauna acelasi numarul de muchii folosit de algoritmul propus de tine (i.e., la fiecare pas gasesti un augmenting path folosind BFS) este egal cu numarul minim de muchii in orice flux maxim. Am crezut pentru un moment ca muchiile au capacitati 0 sau 1 pentru ca ai spus ca taietura minima are un numar minim de muchii. Mi-am dat seama apoi ce vroiai sa spui Smile

@Marius: nu merge intotdeaua sa adaugi |E| + 1 (cel putin, nu-mi dau seama cum o sa construiesti un flux maxim in vechea retzea folosind un flux maxim in noua retzea)
« Ultima modificare: Aprilie 25, 2008, 23:53:02 de către Alina Ene » Memorat
amadaeus
Client obisnuit
**

Karma: 28
Deconectat Deconectat

Mesaje: 93



Vezi Profilul
« Răspunde #8 : Aprilie 25, 2008, 23:42:05 »

In cazul in care capacitatile sunt 0/1, numarul de muchii folosite e intotdeauna acelasi (o unitate de flux satureaza muchia).

Nu orice flux maxim intr-o retea de capacitati 0/1 foloseste acelasi numar de muchii (din nou, conteaza numarul de muchii saturate de pe taietura, in rest poti transporta oricum fluxul). Un exemplu ar fi reteaua V={1,2,3,4}, E={(1,2),(2,3),(3,4),(1,3)}, S=1, T=4. Fluxul maxim este 1 si poate fi trimis pe drumul P1={(1,2),(2,3),(3,4)} sau P2={(1,3),(3,4)}.

Ramane de vazut (de fapt asta era problema mea initiala) daca, in cazul in care fiecare cautare a drumului de ameliorare foloseste un BFS (deci drumul cu numar minim de muchii), atunci se garanteaza minimul global de muchii la incheierea algoritmului...
Memorat

"one of these days I'm going to cut you into little pieces..."
byndrsn
Client obisnuit
**

Karma: 19
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #9 : Aprilie 25, 2008, 23:46:28 »

Scuze, ar fi trebuit sa postez mai explicit. Ma refeream la cazul in care la fiecare pas gasesti un augmenting path folosind BFS. Nu stiu daca merge in general, dar cred ca poti sa demonstrezi ca merge in cazul in care capacitatile sunt 0 sau 1.
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #10 : Aprilie 26, 2008, 08:55:30 »

Citat
Aduni la fiecare muchie valoarea |E| + 1, unde |E| e cardinalul multimii muchiilor. Taietura minima va contine un numar minim de muchii.

 Din articolul de mai sus eu am inteles ca iei fiecare si inmultesti cu |E| si apoi aduni 1.

In plus el se refera ca vrea sa trimita fluxul in asa fel incat numarul de muchii x y, cu f[ x] [y]>0 sa fie minim. (unde f[ x ][y]  este fluxul trimis pe muchia x y).

Am gresit, imi cer scuze. Articolul a fost citit de mine acum ceva mai mult timp. Oricum, e o sursa buna, desi nu e chiar despre ce vroia Lucian sa afle.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #11 : Aprilie 26, 2008, 09:15:01 »

Scuze, ar fi trebuit sa postez mai explicit. Ma refeream la cazul in care la fiecare pas gasesti un augmenting path folosind BFS. Nu stiu daca merge in general, dar cred ca poti sa demonstrezi ca merge in cazul in care capacitatile sunt 0 sau 1.

Daca capacitatile sunt 0/1 atunci merge cu BFS din cauza ca ar fi un flux maxim de cost minim intrun graf care are pe toate muchiile cost 1.

O idee ptr problema generala ar fi sa pui initial toate muchiile cu cost 1, si sa gasesti drumul de ameliorare cu belman-ford, iar atunci cand ai bagat flux pe o muchie sa ii faci costul 0, desi nu sunt sigur ca merge aceasta abordare.
Memorat
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #12 : Aprilie 26, 2008, 09:21:22 »

O idee ptr problema generala ar fi sa pui initial toate muchiile cu cost 1, si sa gasesti drumul de ameliorare cu belman-ford, iar atunci cand ai bagat flux pe o muchie sa ii faci costul 0, desi nu sunt sigur ca merge aceasta abordare.

Tu prin cost intelegi capacitate?

Nu merge sa lasam capacitatile asa cum erau, dar costul fiecarei muchii sa fie 1, iar apoi sa scoatem flux maxim de cost minim ? (sper sa nu fi inteles gresit in ce sens sa se foloseasca nr minim de muchii  Confused)
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #13 : Aprilie 26, 2008, 09:28:32 »

Nu. Prin cost inteleg cost. Capacitatile vor fi cele din input si mai asociez si cost muchiilor, si mai asociez si o functie de cost grafului astfel:

cost(x,y) = 1 , daca flux(x,y) == 0
                   0 , daca flux(x,y) != 0
Memorat
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« Răspunde #14 : Aprilie 26, 2008, 09:29:24 »

Nu merge sa lasam capacitatile asa cum erau, dar costul fiecarei muchii sa fie 1, iar apoi sa scoatem flux maxim de cost minim ? (sper sa nu fi inteles gresit in ce sens sa se foloseasca nr minim de muchii  Confused)

Nu, in flux maxim de cost minim, costul asociat unei muchii e pe unitate de flux, nu pe muchie. Daca trece flux 4 printr-o muchie cu cost 1 atunci costul adunat o sa fie 4.

@devilkind: ma indoiesc ca merge ce ai zis ca nu prea iei in calcul ce faci daca vine flux din directia opusa Smile
Memorat
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #15 : Aprilie 26, 2008, 09:36:13 »

Nu merge sa lasam capacitatile asa cum erau, dar costul fiecarei muchii sa fie 1, iar apoi sa scoatem flux maxim de cost minim ? (sper sa nu fi inteles gresit in ce sens sa se foloseasca nr minim de muchii  Confused)

Nu, in flux maxim de cost minim, costul asociat unei muchii e pe unitate de flux, nu pe muchie. Daca trece flux 4 printr-o muchie cu cost 1 atunci costul adunat o sa fie 4.

Da, ai dreptate, m-am grabit. Gandeam ca nu pui cost pe unitatea de flux, ci pe muchia parcursa, si in acest moment exact asta vrea problema.
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #16 : Aprilie 26, 2008, 09:38:57 »

Citat
@devilkind: ma indoiesc ca merge ce ai zis ca nu prea iei in calcul ce faci daca vine flux din directia opusa Smile
Da ai dreptate nu merge.
Memorat
amadaeus
Client obisnuit
**

Karma: 28
Deconectat Deconectat

Mesaje: 93



Vezi Profilul
« Răspunde #17 : Aprilie 26, 2008, 10:27:13 »

Daca capacitatile sunt 0/1 atunci merge cu BFS din cauza ca ar fi un flux maxim de cost minim intrun graf care are pe toate muchiile cost 1.
Pe cazul 0/1 merge flux maxim de cost minim, cu toate costurile 1, dar drumurile de ameliorare trebuie sa le cauti cu Bellman-Ford, nu cu BFS (faci cost -1 pe muchiile pe care trimiti flux inapoi).
Memorat

"one of these days I'm going to cut you into little pieces..."
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines