•costi_.-.
Strain
Karma: 2
 Deconectat
Mesaje: 30
|
 |
« : Martie 17, 2012, 20:05:19 » |
|
Salut.Sunt intr-un impas. "Dandu-se o matrice cu nxn numere intregi, sa se calculeze drumul de suma minima/maxima de la coordonatele :1,1 la n,n ." Cam asta ar fi enuntul generic pentru astfel de probleme  . Problema sunt directiile de deplasare : sus, jos ,stanga, dreapta . Deci , poti ajunge la un element din orice directe.Aici ma incurc  .Nu-mi dau seama care este relatia de recurenta.Help ? |
|
|
|
|
Memorat
|
|
|
|
|
•wefgef
|
|
« Răspunde #1 : Martie 17, 2012, 22:39:10 » |
|
In forma in care ai expus-o tu, aceasta problema nu admite rezolvare polinomiala.
|
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
|
•Prostu
|
|
« Răspunde #2 : Martie 18, 2012, 01:40:46 » |
|
In forma in care ai expus-o tu, aceasta problema nu admite rezolvare polinomiala.
Nu a spus ca drumul trebuie sa fie simplu, deci cred ca Bellman-Ford ar trebui sa fie ok. |
|
|
|
|
Memorat
|
|
|
|
|
•wefgef
|
|
« Răspunde #3 : Martie 18, 2012, 04:21:12 » |
|
In forma in care ai expus-o tu, aceasta problema nu admite rezolvare polinomiala.
Nu a spus ca drumul trebuie sa fie simplu, deci cred ca Bellman-Ford ar trebui sa fie ok. Mai gandeste-te. |
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
|
•gcosmin
|
|
« Răspunde #4 : Martie 18, 2012, 06:07:38 » |
|
In forma in care ai expus-o tu, aceasta problema nu admite rezolvare polinomiala.
Nu a spus ca drumul trebuie sa fie simplu, deci cred ca Bellman-Ford ar trebui sa fie ok. Mai gandeste-te. Sigur nu mai trebuie sa te gandesti tu Wefgef? Prostu zice ca daca drumu nu e simplu atunci merge Bellman-Ford. |
|
|
|
« Ultima modificare: Martie 18, 2012, 06:13:28 de către Gheorghe Cosmin »
|
Memorat
|
|
|
|
|
•maritim
|
|
« Răspunde #5 : Martie 18, 2012, 11:30:08 » |
|
Salut.Sunt intr-un impas.
"Dandu-se o matrice cu nxn numere intregi, sa se calculeze drumul de suma minima/maxima de la coordonatele :1,1 la n,n ."
Cam asta ar fi enuntul generic pentru astfel de probleme .
Problema sunt directiile de deplasare : sus, jos ,stanga, dreapta . Deci , poti ajunge la un element din orice directe.Aici ma incurc .Nu-mi dau seama care este relatia de recurenta.Help ? Nu este chiar o relatie de recurenta. Este un algoritm de grafuri translatat pe matrice, numit BellmanFord. Aceasta problema este asemanatoare cu Taxe2 de la OJI 2003. P.S. : Algoritmul functioneaza atata timp cat matricea contine doar numere pozitive, sau numere negative care sa nu aiba in jurul lor numere pozitive mai mici in modul ca cele negative. |
|
|
|
« Ultima modificare: Martie 18, 2012, 11:40:00 de către Lambru Andrei Cristian »
|
Memorat
|
|
|
|
|
•Prostu
|
|
« Răspunde #6 : Martie 18, 2012, 12:03:23 » |
|
P.S. : Algoritmul functioneaza atata timp cat matricea contine doar numere pozitive, sau numere negative care sa nu aiba in jurul lor numere pozitive mai mici in modul ca cele negative.
Putin cam specific pentru cum a fost data problema. In primul rand afirmatia ta este adevarata in cazul problemei de minim si in al doilea rand algoritmul Bellman-Ford detecteaza acest caz pentru ca ceea ce tu descrii este un ciclu de cost negativ, care conduce la un cost infinit. |
|
|
|
|
Memorat
|
|
|
|
|
•wefgef
|
|
« Răspunde #7 : Martie 18, 2012, 12:23:05 » |
|
In forma in care ai expus-o tu, aceasta problema nu admite rezolvare polinomiala.
Nu a spus ca drumul trebuie sa fie simplu, deci cred ca Bellman-Ford ar trebui sa fie ok. Mai gandeste-te. Sigur nu mai trebuie sa te gandesti tu Wefgef? Prostu zice ca daca drumu nu e simplu atunci merge Bellman-Ford. Daca drumul nu e simplu costul e infinit/-infinit. |
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
|
•Prostu
|
|
« Răspunde #8 : Martie 18, 2012, 12:30:25 » |
|
In forma in care ai expus-o tu, aceasta problema nu admite rezolvare polinomiala.
Nu a spus ca drumul trebuie sa fie simplu, deci cred ca Bellman-Ford ar trebui sa fie ok. Mai gandeste-te. Sigur nu mai trebuie sa te gandesti tu Wefgef? Prostu zice ca daca drumu nu e simplu atunci merge Bellman-Ford. Daca drumul nu e simplu costul e infinit/-infinit. Intr-o matrice umpluta cu 0, costul minim este 0 si costul maxim este 0. Intr-o matrice umpluta cu 1, costul minim este 2n si costul maxim este infinit. Intr-o matrice umpluta cu -1, costul minim este -infinit si costul maxim este -2n. |
|
|
|
|
Memorat
|
|
|
|
|
•maritim
|
|
« Răspunde #9 : Martie 18, 2012, 12:49:24 » |
|
Putin cam specific pentru cum a fost data problema. In primul rand afirmatia ta este adevarata in cazul problemei de minim si in al doilea rand algoritmul Bellman-Ford detecteaza acest caz pentru ca ceea ce tu descrii este un ciclu de cost negativ, care conduce la un cost infinit. Stiu, nu am vrut sa intru in detalii deoarece presupun ca cel care a pus intrebarea nu are cunostinte de grafuri. Intradevar, afirmatia mea este valida doar pentru cazul in care se calculeaza minimul. Pentru a se calcula maximul : A[ i ][ j ] = - A[ i ][ j ] si se normalizeaza putin pentru a nu mai avea valori negative. In acest mod nu mai trebuie sa ne facem griji nici de valorile negative initiale. Dupa ce am facut Bellman-Ford pentru drum minim, normalizam la loc aceasta valoare. De asemenea si problema ciclului infinit se poate rezolva cu algoritmul Bellman-Ford! |
|
|
|
|
Memorat
|
|
|
|
•costi_.-.
Strain
Karma: 2
Deconectat
Mesaje: 30
|
|
« Răspunde #10 : Martie 18, 2012, 15:11:51 » |
|
@maritim Am cunostinte despre grafuri si stiu despre algoritmul BellmanFord.Daca matricea ar avea numai elemente pozitive, Dijkstra se descurca mai bine .Asadar, directiile impun algoritmul de rezolvare.
Daca acestea erau mai restrictive , se poate folosi PD, nu ? Dar algoritmii grafurilor?
|
|
|
|
|
Memorat
|
|
|
|
|
•klamathix
|
|
« Răspunde #11 : Martie 18, 2012, 15:18:31 » |
|
Trebuie sa privesti chestiunea putin mai abstract. Tu nu stiai sa rezolvi problema cu programare dinamica fiinca starile dinamicii sunt ciclice (Calculul casutei A depinde de calculul casutei B, dar si invers). La versiunea clasica "jos si dreapta" nu aveai impedimentul asta. Ideea in sine e tot de programare dinamica, doar ca gasesti un mod sa tratezi ciclicitatea. Dijkstra si Bellman-Ford, daca stai sa te gandesti, sunt bazati de fapt pe principiul programarii dinamice(pentru a calcula drumul minim pana la un anumit nod, ai nevoie de drumurile minime pana la toate nodurile intermediare).
La faza cu ciclurile, Dijkstra se foloseste de faptul ca tot timpul gasesti un nod care sigur nu va mai fi actualizat (cel cu costul minim) si astfel toti vecinii depind de el, dar el nu mai depinde de nimeni. Bellman-Ford-ul reexpandeaza nodurile cand este nevoie, iar daca exista solutie, numarul de reexpandari este finit.
|
|
|
|
« Ultima modificare: Martie 18, 2012, 15:26:20 de către Mihai Calancea »
|
Memorat
|
|
|
|
•costi_.-.
Strain
Karma: 2
Deconectat
Mesaje: 30
|
|
« Răspunde #12 : Martie 19, 2012, 18:30:23 » |
|
Ok, am inteles |
|
|
|
|
Memorat
|
|
|
|
|
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena