Titlul: Distante! Scris de: CHERA Laurentiu din August 13, 2008, 20:17:03 Buna ziua!
Doresc sa stiu cum pot determina lungimea minima dintre doua puncte ale unei matrice tinand cont ca nu te poti deplasa pe diagonala matricei (bidimensionala). Ex matrice: 1 2 3 4 5 6 7 8 9 Distanta minima din coltul din stanga-sus pana in coltul din dreapta-jos este 21 : 1 -> 2 -> 3 ->6->9 Va multumesc ! :D Titlul: Răspuns: Distante! Scris de: Cosmin Negruseri din August 14, 2008, 06:58:38 Poti folosi orice algoritm de cautare de drumuri minime.
Titlul: Răspuns: Distante! Scris de: Savin Tiberiu din August 14, 2008, 08:40:36 pe ex tau distanta minima nu e 21?? 1 - 2 - 3 - 6 - 9
Titlul: Răspuns: Distante! Scris de: Maria Stanciu din August 14, 2008, 09:43:40 Ba da :).
Poti folosi algoritmul lui lee. Daca nu stii cu ce se mananca ai aici un articol: http://www.ginfo.ro/revista/15_2/focus1.pdf Spor. Titlul: Răspuns: Distante! Scris de: Savin Tiberiu din August 14, 2008, 11:52:05 nu poti folosi lee deoarece ai costuri. Poti folosi algoritmul lui Djikstra in schimb.
Titlul: Răspuns: Distante! Scris de: CHERA Laurentiu din August 14, 2008, 12:13:10 Va multumesc pentru ajutor!
Intradevar, distanata minima este 1 -> 2 -> 3 -> 6 -> 9 ! :P Imi cer scuze pentru greseala facuta :roll: Titlul: Răspuns: Distante! Scris de: Sima Cotizo din August 15, 2008, 14:52:34 nu poti folosi lee deoarece ai costuri. Poti folosi algoritmul lui Djikstra in schimb. popular tot "lee" ii zice :D Titlul: Răspuns: Distante! Scris de: Marius Stroe din August 15, 2008, 15:28:19 nu poti folosi lee deoarece ai costuri. Poti folosi algoritmul lui Djikstra in schimb. În cazul în care ai cost pe noduri poţi folosi o coadă simplă. Şi cred că se numeşte Lee, deşi văd că nu e mare diferenţă de Bellman Ford cu coadă. Nu prea e pe SGU problema... :) Titlul: Răspuns: Distante! Scris de: Maria Stanciu din August 15, 2008, 16:32:27 Nu conteaza asa mult cum se numeste :).
Algoritmul este interesant pentru un incepator. Laurentiu ai reusit sa rezolvi problema? Titlul: Răspuns: Distante! Scris de: CHERA Laurentiu din August 16, 2008, 00:53:56 Da, am reusit sa rezolv problema! :)
Va multumesc pentru ajutorul acordat, si pentru ca v-ati implicat! :D Titlul: Răspuns: Distante! Scris de: Marius Stroe din August 16, 2008, 14:43:06 În primul rând felicitări. În al doilea rând, ai grijă unde postezi data viitoare. :)
Iată ce ai pe prima pagină din Index: Informatica Informatica, algoritmi, structuri de date, matematica... stii tu ;) Titlul: Răspuns: Distante! Scris de: CHERA Laurentiu din August 17, 2008, 15:12:30 Am reusit urmatoarea implementare :D :
Matrice : 10 3 1 2 5 1 3 1 0 8 1 10 = suma de bani avuta initial; n = 3; Programul afiseaza suma maxima de bani ramasa angajatului dupa ce traverseaza firma de la un birou la altul (1 - stanga sus; la 1-dreapta jos); Cod: /*Taxe*/ Titlul: Răspuns: Distante! Scris de: Marius Stroe din August 17, 2008, 20:43:19 E corect algoritmul. Dacă iterai while()ul de N2 ori obţineai acelaşi rezultat. Algoritmul se numeşte Bellman Ford. Dar dacă iterezi cât timp mai poţi relaxa, atunci ai o optimizare. :) Complexitatea lui e O(N4).
Cu algoritmul lui Dijkstra de drumuri minime, poţi obţine complexitatea O(N2 logN2). Mult mai eficient. Titlul: Răspuns: Distante! Scris de: Ionescu Vlad din August 18, 2008, 15:49:34 Problema nu merge si cu memoizare?
Fie f(i, j) costul minim pentru a ajunge de la punctul de plecare (x, y) pana in (i, j). f(i, j) = cost[ i ][ j ] + min(f(i+1, j), f(i, j+1), f(i-1, j), f(i, j-1)). f(x, y) se initializeaza cu cost[ x ][ y ] si eventual mai trebuie avut grija sa nu se apeleze recursiv pentru zone inaccesibile (i, j < 0 etc) Pare corect. Complexitatea nu ar fi patratica daca se aplica memoizare? Titlul: Răspuns: Distante! Scris de: CHERA Laurentiu din August 18, 2008, 16:00:52 Metoda pe care ai prezentat-o nu are o eroare? De exemplu:
In matricea, 1 2 5 1 3 1 0 8 1 , algoritmul cand va ajunge in nodul (1,0), nu o sa aleaga intre 3 si 0 pe 0 :roll:, nodul (2,0) al matricei. In cazul in care va alege nodul (2,0) programul va afisa un rezultat eronat, deoarece drumul minim este : 1->1->3->1->1 si nu 1->1->0->8->1 :) ! Titlul: Răspuns: Distante! Scris de: Ionescu Vlad din August 18, 2008, 17:34:09 Tu ai ales minimul dintre valori ale matricii costurilor. Eu am zis ca se alege minimul dintre apeluri recursive.
Uite un program care l-am scris rapid, nu stiu daca e 100% corect, dar pe exemplul tau da corect: 7. Cod: int n, m; |