Titlul: Cautare drum minim matrice Scris de: Doru Gucea din Noiembrie 02, 2012, 21:11:51 Salut !
Am urmatoare problema: 2 matrici (n x n) de intregi. Prima matrice are ca elemente doar 0 si 1, sa o numim matricea de resurse. A doua matrice are valori intregi random, sa o numim matricea de preturi. Trebuie sa gasesc pentru fiecare element din matricea de resurse drumul minim catre resursa complementara. Ce inseamna drum minim: pe scurt pretul resursei complementare(daca am 0=> resursa complementara va fi 1 si invers) + lungimea drumului pana acolo. Ce algoritm as putea folosi? O(n4) -> brute force e prea mult. BFS din fiecare element pana la un pas la care nu mai are rost sa continui explorarea, iarasi nu se obtin timpi prea buni. Floyd-Warshall(O(n3)) ar fi ok insa nu stiu cum sa il adaptez. Orice hint e de ajutor. Multumesc! Titlul: Răspuns: Cautare drum minim matrice Scris de: Doru Gucea din Noiembrie 03, 2012, 11:22:16 Nu am fost indeajuns de clar cu enuntul problemei, trebuie sa reformulez ?
Titlul: Răspuns: Cautare drum minim matrice Scris de: Boaca Cosmin din Noiembrie 03, 2012, 17:09:18 Faci confuzie . Floyd Warshall e O(n ^ 3) unde n e numarul de noduri, la tine ar fi O(n ^ 6), pentru ca numarul de noduri este n ^ 2, unde n e dimensiunea matricii . Din celula i,j poti trece in oricare din cei 8 vecini ? Poti merge si prin celule complementare cu aceea de start sau doar prin cele asemenea ?
Titlul: Răspuns: Cautare drum minim matrice Scris de: Andrei Grigorean din Noiembrie 03, 2012, 17:18:56 Draguta problema, de unde e?
Titlul: Răspuns: Cautare drum minim matrice Scris de: Doru Gucea din Noiembrie 03, 2012, 17:31:59 @darkseeker: Multumesc pt. complexitate, asa este. Poti trece in oricare din cei 4 vecini (N, S, V, E) nu 8 pentru ca e vorba de distanta Manhattan, si de asemenea nu are importanta celulele din cale(daca sunt 0 sau 1).
@wefgef: E un bonus de la o tema de la materia numita Algoritmi paraleli si distribuiti. Pe mine ma intereseaza sa optimizez varianta seriala in primul rand. Deja am implementat varianta O(n^4) pe care am paralelizat-o si am obtinut rezultate foarte bune. Titlul: Răspuns: Cautare drum minim matrice Scris de: Andrei Grigorean din Noiembrie 03, 2012, 17:35:28 Merge in O(N^2 log N) cu Dijkstra.
Titlul: Răspuns: Cautare drum minim matrice Scris de: Doru Gucea din Noiembrie 03, 2012, 17:49:28 Dijkstra are complexitate de O(n^2 log n) daca ar trebui sa calculez distanta minima de la o celula la toate celelate. Problema este ca eu trebuie sa aplic Dijkstra pentru toate cele n^2 celule, deci o complexitate mult mai mare. Sau gresesc ?
Titlul: Răspuns: Cautare drum minim matrice Scris de: Mihai Calancea din Noiembrie 03, 2012, 18:44:56 Nu trebuie sa l faci de n^2 ori. Il faci numai o data, dar iei ca surse toate elementele de tip 0.
|