|
Titlul: Drum de suma minima/maxima in matrice [PD] Scris de: Costinnel din 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 :ok:. 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 ? Titlul: Răspuns: Drum de suma minima/maxima in matrice [PD] Scris de: Andrei Grigorean din Martie 17, 2012, 22:39:10 In forma in care ai expus-o tu, aceasta problema nu admite rezolvare polinomiala.
Titlul: Răspuns: Drum de suma minima/maxima in matrice [PD] Scris de: Stefan-Alexandru Filip din 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. Titlul: Răspuns: Drum de suma minima/maxima in matrice [PD] Scris de: Andrei Grigorean din 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. Titlul: Răspuns: Drum de suma minima/maxima in matrice [PD] Scris de: Gheorghe Cosmin din 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. Titlul: Răspuns: Drum de suma minima/maxima in matrice [PD] Scris de: Cristian Lambru din Martie 18, 2012, 11:30:08 Citat 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 (http://infoarena.ro/problema/bellmanford). Aceasta problema este asemanatoare cu Taxe2 (http://infoarena.ro/problema/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. Titlul: Răspuns: Drum de suma minima/maxima in matrice [PD] Scris de: Stefan-Alexandru Filip din 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. Titlul: Răspuns: Drum de suma minima/maxima in matrice [PD] Scris de: Andrei Grigorean din 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. Titlul: Răspuns: Drum de suma minima/maxima in matrice [PD] Scris de: Stefan-Alexandru Filip din 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. Titlul: Răspuns: Drum de suma minima/maxima in matrice [PD] Scris de: Cristian Lambru din Martie 18, 2012, 12:49:24 Citat 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! Titlul: Răspuns: Drum de suma minima/maxima in matrice [PD] Scris de: Costinnel din 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? Titlul: Răspuns: Drum de suma minima/maxima in matrice [PD] Scris de: Mihai Calancea din 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. Titlul: Răspuns: Drum de suma minima/maxima in matrice [PD] Scris de: Costinnel din Martie 19, 2012, 18:30:23 Ok, am inteles :ok:
|