tmac
Vizitator
|
|
« : Aprilie 06, 2006, 16:47:29 » |
|
cum se face ... ?
|
|
|
Memorat
|
|
|
|
ditzone
Vizitator
|
|
« Răspunde #1 : Aprilie 06, 2006, 16:50:58 » |
|
Asemanator fluxului normal, doar ca ai grija la fiecare pas drumul de la sursa la destinatie sa aibe cost minim. In loc de o simpla parcurgere in latime sau adancime faci un bellman ford..
|
|
|
Memorat
|
|
|
|
u-92
Vizitator
|
|
« Răspunde #2 : Aprilie 06, 2006, 17:00:34 » |
|
cand gasesti un flux admisibil il faci si de cost minim. o sa ai cost(i,j) = costul pe arcul (i->j) iar cost(j,i) = -cost(i,j) Acum poti sa demonstrezi ca atata timp cat exista un ciclu negativ in graful asta poti obtine un cost mai bun adaugand pe fiecare muchie din ciclu o cantintate de flux egala cu minimul fluxului de pe toate muchiile din ciclu.
|
|
|
Memorat
|
|
|
|
tmac
Vizitator
|
|
« Răspunde #3 : Aprilie 06, 2006, 21:29:09 » |
|
am inteles. ms mult !
|
|
|
Memorat
|
|
|
|
tmac
Vizitator
|
|
« Răspunde #4 : Aprilie 07, 2006, 11:21:15 » |
|
nu pot sa fac dijsktra in loc de bellman ford ? parcurgerea in latime gaseste un cel mai scurt drum relativ la nr de muchii, dijsktra gaseste un cel mai scurt drum relativ la costurile pe muchii. sau fac bellman ford acela cu coada sa optimizez si un flux maxim si un cost minim ?
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #5 : Aprilie 07, 2006, 11:40:12 » |
|
nu poti sa faci dijkstra pentru ca pe muchiile de intoarcere vei avea cost negativ.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
tmac
Vizitator
|
|
« Răspunde #6 : Aprilie 07, 2006, 14:42:52 » |
|
se pare ca nu stiu exact formularea problemei . Poatemi spune cineva exact formularea ...
|
|
|
Memorat
|
|
|
|
•Marius
|
|
« Răspunde #7 : Iulie 26, 2006, 19:31:59 » |
|
cand gasesti un flux admisibil il faci si de cost minim. o sa ai cost(i,j) = costul pe arcul (i->j) iar cost(j,i) = -cost(i,j) Acum poti sa demonstrezi ca atata timp cat exista un ciclu negativ in graful asta poti obtine un cost mai bun adaugand pe fiecare muchie din ciclu o cantintate de flux egala cu minimul fluxului de pe toate muchiile din ciclu.
Acel drum de cost minim se bazeaza pe muchiile capacitate - flux, adica capacitate reziduala ? De ce cost(j, i) = - cost(i, j) ? De pe acel drum minim aleg muchia cu capacitatea reziduala minima si adun la fluxul muchiilor ? Exista undeva in lume niste demonstratii pentru cele zise mai sus, sa contrazica intuitia ?
|
|
« Ultima modificare: Iulie 26, 2006, 20:02:45 de către Marius »
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•cristy
|
|
« Răspunde #8 : Iulie 26, 2006, 20:38:59 » |
|
uita-te in Cormen
|
|
|
Memorat
|
... lipsa de inspiratie ...
|
|
|
•Marius
|
|
« Răspunde #9 : Iulie 26, 2006, 20:46:21 » |
|
Introducere in Algoritmi imi raspunde la intrebarile de mai sus despre flux maxim de COST MINIM ? Nu zic ca nu e, dar eu nu am gasit...
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•byndrsn
Client obisnuit
Karma: 19
Deconectat
Mesaje: 72
|
|
« Răspunde #10 : Iulie 27, 2006, 03:59:19 » |
|
nu pot sa fac dijsktra in loc de bellman ford ? parcurgerea in latime gaseste un cel mai scurt drum relativ la nr de muchii, dijsktra gaseste un cel mai scurt drum relativ la costurile pe muchii.
. . poti sa folosesti Dijkstra daca nu ai cicluri de cost negativ, dar trebuie sa modifici greutatile pe muchii ca sa devina non-negative...
pentru a modifica greutatile muchiilor, tii un vector f[ v ] = potentialul varfului v greutatea (costul) fiecarei muchii e = u->v devine w[ e ] + f[ u ] - f[ v ], unde w[ e ] este adevaratul cost al muchiei... costul unui drum de la s la t se modifica cu o constanta (f[ s ] - f[ t ]), asa ca drumurile de cost minim in graful cu costurile modificate nu se modifica..
initial f[ v ] = costul minim de la s la v noul cost al unei muchii e >= 0, pentru orice muchie e = u->v (pentru ca alfel ai avea f[ v ] > f[ u ] + w[ e ], ceea ce contrazice faptul ca f[ v ] este costul minim)
tot ceea ce ramane de facut e sa modifici potentialele de fiecare data cand gasesti un augmenting path (trebuie sa le modifici inainte sa trimiti flux pe drumul gasit)...
sa zicem ca ai gasit un augmenting path p folosind Dijkstra, si d[ v ] = costul minim de la s la v (gasit de Dijkstra la pasul curent).. vrei sa modifici potentialele inainte sa trimiti flux pe drumul p astfel incat toate muchiile pe drumul p sa aiba noul cost 0 (astfel muchiile de intoarcere vor avea si ele noul cost 0)
asa ca faci update astfel: f[ v ] <- f[ v ] + d[ v ]
teoretic, implementarea naiva max flow + Bellman Ford e O(n^4), si max flow + Dijkstra + costuri modificate e O(n^3).. practic, nu stiu care e mai rapid...
|
|
« Ultima modificare: Iulie 27, 2006, 04:05:20 de către byndrsn »
|
Memorat
|
|
|
|
•azotlichid
|
|
« Răspunde #11 : Iulie 27, 2006, 11:44:11 » |
|
Inteligent Auzisem ca se poate folosi Dijkstra pt flux maxim de cost minim, totusi nu am cautat niciodata o imbunatatire fata de vechiul Bellman Ford Banuiesc ca ideea de modificare a greutatilor muchiilor are niste aplicatii foarte interesante si in alte probleme...
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #12 : Iulie 27, 2006, 15:24:17 » |
|
Cica nu ajuta sensibil ca timp sa folosesti Dijkstra in loc de Bellman Ford.
|
|
|
Memorat
|
|
|
|
•azotlichid
|
|
« Răspunde #13 : Iulie 28, 2006, 10:22:10 » |
|
Asta in practica Dar teoria ascunde inca multe idei elegante
|
|
|
Memorat
|
|
|
|
•Marius
|
|
« Răspunde #14 : August 05, 2006, 16:30:50 » |
|
Ce complexitate are algoritmul Ungar ?
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
VladS
Vizitator
|
|
« Răspunde #15 : August 05, 2006, 19:22:35 » |
|
O( N ^ 3 )
|
|
|
Memorat
|
|
|
|
|