Algoritmul lui Kuhn

[•sims_gl]

M-as apuca eu sa transcriu articolul despre "Algoritmul lui Kuhn", daca nu are deja altcineva de gand sa faca asta. Trebuie facut si altceva decat copiat si formatat textul?

[•domino]

Baga mare. Nu cred ca sunt necesare modificari asupra textului.

[•Cosmin]

Voi ati inteles ceva din articol?

[•sims_gl]

Hmm, am terminat, cred (ma mai uit dupa greseli de tipografie)... Deocamdata doar l-am transcris, acum o sa il si citesc sa vad daca pricep ceva 

Am o nelamurire: in codul sursa prezentat, la linia 11 era scris in articol "min <?= G[ i ][ j ] + vr[ i ] - vc[ j ];"  Am presupus ca trebuia "min = G[ i ][ j ] + vr[ i ] - vc[ j ];"...

[•domino]

Hmm, am terminat, cred (ma mai uit dupa greseli de tipografie)... Deocamdata doar l-am transcris, acum o sa il si citesc sa vad daca pricep ceva 

Am o nelamurire: in codul sursa prezentat, la linia 11 era scris in articol "min <?= G[ i ][ j ] + vr[ i ] - vc[ j ];"  Am presupus ca trebuia "min = G[ i ][ j ] + vr[ i ] - vc[ j ];"...

E corect cu <?= , e o extensie de gcc acest operator.

[•sims_gl]

Aham, am corectat. Am pus si un link in pagina cu articole. Sper ca e totul ok. 

[•greco]

Buna treaba Sims, multumesc (multumim) ! Ai urmarit tot ce scria acolo ? E OK ? Daca gasiti greseli logice, sau daca aveti alte idei de optimizare sariti cu ele... complexitatea in momentul de fata este O(N^4) daca imi aduc bine aminte, insa se comporta mai bine in practica, in functie si de costurile din matrice. Pe vremuri, am luat AC cu algoritmul ungar (posibil chiar cu sursa asta) pe Timus (ceva cu trash din primul volum) si nu-mi intra in timp cu flux, dar pe atunci nu stiam sa implementez foarte eficient un flux si nici nu se prea stiau smenuri gen Dinic. In momentul de fata cred ca un flux implementat la sange il cam rupe, desi pe grafuri complete... cine stie ? 

In orice caz, cred ca se poate implementa si in O(N^3) "curat", doar ca n-am mai dedicat foarte mult timp in acest sens. Intreaga idee a articolului a pornit de la un articol din Ginfo, care prezenta o metoda super simpla de a rezolva aceeasi problema in O(N^3), avand o singura belea: nu mergea. A mai fost curs de algoritm ungar si la lot acum cativa ani, si tin minte ca sursa aia pe unele teste mergea (foarte prost, mai prost ca sursa asta cu optimizarea), pe altele cicla (chiar cu n=20). Sper sa nu avem asemenea surprize si in acest caz, pentru ca problema e relativ delicata si iti dai seama mai greu daca e totul in regula...

Si, pana la urma

Voi ati inteles ceva din articol?

Recunosc ca e destul de incurcat, dar nu stiu cum s-ar putea expune mai usor, eu unul ma chinuisem multa vreme pe atunci sa-i dau de cap. Orice idei sunt binevenite !

[•peanutz]

Totusi, ce face "<?=" mai exact?

[•greco]

Asta s-ar putea sa fie o mica problema. Operatorii <?, >?, <?=, >?= nu sunt un standard C++, ci o extensie gcc, devenind chiar invechiti si nerecomandati din versiunea 4 a compilatorului.

a <? b returneaza minimul dintre a si b, a <?= b atribuie lui a aceasta valoare. Scurteaza codul si sunt comozi doar ca dupa cum spuneam... nu sunt standard.