|
Titlul: Algoritmul lui Kuhn Scris de: Alexandru Simion din Aprilie 23, 2007, 10:44:57 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?
Titlul: Răspuns: Algoritmul lui Kuhn Scris de: Mircea Pasoi din Aprilie 23, 2007, 14:37:11 Baga mare. Nu cred ca sunt necesare modificari asupra textului.
Titlul: Răspuns: Algoritmul lui Kuhn Scris de: Cosmin Negruseri din Aprilie 23, 2007, 18:30:21 Voi ati inteles ceva din articol?
Titlul: Răspuns: Algoritmul lui Kuhn Scris de: Alexandru Simion din Aprilie 23, 2007, 19:25:59 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 ];"... Titlul: Răspuns: Algoritmul lui Kuhn Scris de: Mircea Pasoi din Aprilie 23, 2007, 19:38:06 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. Titlul: Răspuns: Algoritmul lui Kuhn Scris de: Alexandru Simion din Aprilie 23, 2007, 20:16:06 Aham, am corectat. Am pus si un link in pagina cu articole. Sper ca e totul ok. :peacefingers:
Titlul: Răspuns: Algoritmul lui Kuhn Scris de: Tiberiu-Lucian Florea din Aprilie 23, 2007, 21:06:41 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 ! Titlul: Răspuns: Algoritmul lui Kuhn Scris de: Andrei Homorodean din Aprilie 24, 2007, 19:02:38 Totusi, ce face "<?=" mai exact?
Titlul: Răspuns: Algoritmul lui Kuhn Scris de: Tiberiu-Lucian Florea din Aprilie 24, 2007, 21:55:17 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. |