•Doru_AC
Strain
Karma: 1
Deconectat
Mesaje: 10
|
|
« : 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!
|
|
|
Memorat
|
|
|
|
•Doru_AC
Strain
Karma: 1
Deconectat
Mesaje: 10
|
|
« Răspunde #1 : Noiembrie 03, 2012, 11:22:16 » |
|
Nu am fost indeajuns de clar cu enuntul problemei, trebuie sa reformulez ?
|
|
|
Memorat
|
|
|
|
•darkseeker
|
|
« Răspunde #2 : 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 ?
|
|
« Ultima modificare: Noiembrie 03, 2012, 17:21:32 de către Boaca Cosmin »
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #3 : Noiembrie 03, 2012, 17:18:56 » |
|
Draguta problema, de unde e?
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•Doru_AC
Strain
Karma: 1
Deconectat
Mesaje: 10
|
|
« Răspunde #4 : 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.
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #5 : Noiembrie 03, 2012, 17:35:28 » |
|
Merge in O(N^2 log N) cu Dijkstra.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•Doru_AC
Strain
Karma: 1
Deconectat
Mesaje: 10
|
|
« Răspunde #6 : 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 ?
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #7 : 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.
|
|
|
Memorat
|
|
|
|
|