Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Algoritmul lui Kuhn  (Citit de 15469 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
sims_gl
Client obisnuit
**

Karma: 35
Deconectat Deconectat

Mesaje: 53



Vezi Profilul
« : 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?
Memorat

"I want to know god's thoughts... the rest are details." Einstein
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #1 : Aprilie 23, 2007, 14:37:11 »

Baga mare. Nu cred ca sunt necesare modificari asupra textului.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #2 : Aprilie 23, 2007, 18:30:21 »

Voi ati inteles ceva din articol?
Memorat
sims_gl
Client obisnuit
**

Karma: 35
Deconectat Deconectat

Mesaje: 53



Vezi Profilul
« Răspunde #3 : 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  Smile

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 ];"...
Memorat

"I want to know god's thoughts... the rest are details." Einstein
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #4 : 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  Smile

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.
Memorat
sims_gl
Client obisnuit
**

Karma: 35
Deconectat Deconectat

Mesaje: 53



Vezi Profilul
« Răspunde #5 : Aprilie 23, 2007, 20:16:06 »

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

"I want to know god's thoughts... the rest are details." Einstein
greco
Nu mai tace
*****

Karma: 144
Deconectat Deconectat

Mesaje: 434



Vezi Profilul
« Răspunde #6 : 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 ?  Smile

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 !
Memorat

Jump in the cockpit and start up the engines
Remove all the wheelblocks there's no time to waste
Gathering speed as we head down the runway
Gotta get airborne before it's too late.
peanutz
Nu mai tace
*****

Karma: 10
Deconectat Deconectat

Mesaje: 296



Vezi Profilul
« Răspunde #7 : Aprilie 24, 2007, 19:02:38 »

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

....staind....
greco
Nu mai tace
*****

Karma: 144
Deconectat Deconectat

Mesaje: 434



Vezi Profilul
« Răspunde #8 : 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.
Memorat

Jump in the cockpit and start up the engines
Remove all the wheelblocks there's no time to waste
Gathering speed as we head down the runway
Gotta get airborne before it's too late.
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines