|
Titlul: Flux maxim de cost minim Scris de: tmac din Aprilie 06, 2006, 16:47:29 cum se face ... ?
Titlul: Raspuns: Flux maxim de cost minim Scris de: ditzone din 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..
Titlul: Raspuns: Flux maxim de cost minim Scris de: u-92 din 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. Titlul: Raspuns: Flux maxim de cost minim Scris de: tmac din Aprilie 06, 2006, 21:29:09 am inteles. ms mult ! :D
Titlul: Raspuns: Flux maxim de cost minim Scris de: tmac din 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 ?
Titlul: Raspuns: Flux maxim de cost minim Scris de: Andrei Grigorean din Aprilie 07, 2006, 11:40:12 nu poti sa faci dijkstra pentru ca pe muchiile de intoarcere vei avea cost negativ.
Titlul: Raspuns: Flux maxim de cost minim Scris de: tmac din Aprilie 07, 2006, 14:42:52 se pare ca nu stiu exact formularea problemei :(. Poatemi spune cineva exact formularea ...
Titlul: Raspuns: Flux maxim de cost minim Scris de: Marius Stroe din 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 ? :-) Titlul: Raspuns: Flux maxim de cost minim Scris de: Rus Cristian din Iulie 26, 2006, 20:38:59 uita-te in Cormen
Titlul: Raspuns: Flux maxim de cost minim Scris de: Marius Stroe din 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... :? Titlul: Raspuns: Flux maxim de cost minim Scris de: Alina Ene din 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... Titlul: Re: Flux maxim de cost minim Scris de: Adrian Vladu din Iulie 27, 2006, 11:44:11 Inteligent =D> Auzisem ca se poate folosi Dijkstra pt flux maxim de cost minim, totusi nu am cautat niciodata o imbunatatire fata de vechiul Bellman Ford :oops: Banuiesc ca ideea de modificare a greutatilor muchiilor are niste aplicatii foarte interesante si in alte probleme...
Titlul: Raspuns: Flux maxim de cost minim Scris de: Cosmin Negruseri din Iulie 27, 2006, 15:24:17 Cica nu ajuta sensibil ca timp sa folosesti Dijkstra in loc de Bellman Ford.
Titlul: Re: Flux maxim de cost minim Scris de: Adrian Vladu din Iulie 28, 2006, 10:22:10 Asta in practica :P Dar teoria ascunde inca multe idei elegante :idea:
Titlul: Raspuns: Flux maxim de cost minim Scris de: Marius Stroe din August 05, 2006, 16:30:50 Ce complexitate are algoritmul Ungar ? ???
Titlul: Raspuns: Flux maxim de cost minim Scris de: VladS din August 05, 2006, 19:22:35 O( N ^ 3 )
|