|
•Marius
|
 |
« : Septembrie 19, 2006, 18:27:14 » |
|
Cum se rezolva ?
Ce probleme stiti care se rezolva cu acest algoritm ?
Multumesc anticipat!
|
|
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
|
•wefgef
|
|
« Răspunde #1 : Septembrie 19, 2006, 20:39:43 » |
|
inmultesti cu -1 muchiile si faci flux maxim de cost minim.
|
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
|
•filipb
|
|
« Răspunde #2 : Septembrie 20, 2006, 11:48:11 » |
|
Eu zic ca problema de flux maxim si cost maxim e NP hard, pentru ca in final se reduce tot la gasirea unui drum de cost maxim de la sursa la destinatie. Inmultirea asta cu -1 pentru a afla un drum de cost maxim intre doua noduri cred ca nu functioneaza din urmatoarele motive: sa presupunem ca toate muchiile au cost pozitiv, graful contine cicluri ( daca nu, problema se rezolva cu complexitate liniara ) si este conex. Cand facem costurile negative sigur exista un ciclu de cost negativ in care se poate ajunge din nodul de start, si acest ciclu am putea sa il parcurgem la infinit obtinand un cost mai mic.
|
|
|
|
|
Memorat
|
|
|
|
|
•wefgef
|
|
« Răspunde #3 : Septembrie 20, 2006, 20:01:11 » |
|
da, asa e  |
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
|
•Marius
|
|
« Răspunde #4 : Septembrie 20, 2006, 21:46:53 » |
|
inmultesti cu -1 muchiile si faci flux maxim de cost minim.
Aceeasi idee am avut-o si eu. -1 amandoi  |
|
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
|
•Cosmin
|
|
« Răspunde #5 : Septembrie 20, 2006, 23:39:22 » |
|
Dar in schimb cuplaj maxim de cost maxim, cand muchiile au cost pozitiv, merge.
|
|
|
|
|
Memorat
|
|
|
|
•StTwister
Client obisnuit
Karma: 11
 Deconectat
Mesaje: 86
|
|
« Răspunde #6 : Ianuarie 13, 2007, 12:05:38 » |
|
Cam tarziu vine si raspunsul meu... Ideea mea e ca in loc sa inmultesti costurile cu -1 sa le scazi dintr-o constanta mare (INFINIT), adik c [j] = INF - c[j]
Astfel se inverseaza relatia de ordine dintre costuri, si raman si pozitive in acelasi timp, adica nu exista cicluri de cost negativ. Si se face fluxu de cost minim pe noua retea.
Nu am testat, dar cred ca ar merge.
Astept contraexmple  |
|
|
|
|
Memorat
|
|
|
|
|
•astronomy
|
|
« Răspunde #7 : Ianuarie 13, 2007, 12:57:08 » |
|
Nu e corect, de exemplu ai un graf orientat cu 3 noduri si muchiile 1->2, 2->3, 1->3.
1 e sursa, 3 e destinatia, ai capacitatea 1 pe fiecare muchie si costurile 1->2: 5, 2->3: 6, 1->3: 9
Noile costuri vor fi INF-5, INF-6 si INF-9 iar tot timpul 2*INF-11 > INF-9 (pt INF destul de mare, mai mare decat 3), deci iti va gasi drumul 1->3 ca fiind de cost maxim.
|
|
|
|
|
Memorat
|
|
|
|
|
•pauldb
|
|
« Răspunde #8 : Ianuarie 17, 2007, 14:01:44 » |
|
Dar in schimb cuplaj maxim de cost maxim, cand muchiile au cost pozitiv, merge.
Si totusi cum se face cuplajul de cost maxim? |
|
|
|
|
Memorat
|
Am zis  |
|
|
|
•astronomy
|
|
« Răspunde #9 : Ianuarie 17, 2007, 15:38:00 » |
|
Consideri Vmax = cel mai care cost al unei muchii si pentru fiecare muchie faci transformarea cost[muchie] = Vmax-cost[muchie]. Acum costul minim o sa fie <valoare cuplaj>*Vmax-(suma costurilor muchiilor initiale din cuplaj) => suma costurilor muchiilor initiale din cuplaj e maxima.
|
|
|
|
« Ultima modificare: Ianuarie 17, 2007, 18:01:05 de către Airinei Adrian »
|
Memorat
|
|
|
|
|
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena