Cautare drum minim matrice

[•Doru_AC]

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!

[•Doru_AC]

Nu am fost indeajuns de clar cu enuntul problemei, trebuie sa reformulez ?

[•darkseeker]

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 ?

[•wefgef]

Draguta problema, de unde e?

[•Doru_AC]

@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.

[•wefgef]

Merge in O(N^2 log N) cu Dijkstra.

[•Doru_AC]

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 ?

[•klamathix]

Nu trebuie sa l faci de n^2 ori. Il faci numai o data, dar iei ca surse toate elementele de tip 0.