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 ?

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

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

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!

L-am implementat. Multumesc mult pentru explicatii.

Foarte tare. Cum mai putin de O(n^2) nu se poate, e perfect. Multumesc  

L.E. Am incercat sa o implementez in O(n^2) insa nu cred ca se poate fara cautare binara. Poti sa dai mai multe detalii in legatura cu iteratorul pe care il incrementez?

Salutare,

Sa presupunem ca avem N betisoare. Cum construiesc un algoritm mai eficient decat O(N^3)  care determina daca printre cele N betisoare exista o combinatie de trei betisoare care formeaza un triunghi dreptunghic ?
Lungimea betisoarelor se presupune cunoscuta.

Multumesc

De asta aveam nevoie. Va multumesc si ma inclin 

Problema urmatoare mi-a mancat toata seara asa ca nemaiavand idei m-am gandit ca poate cineva cu suflet ( a se citi minte) ma va ajuta.

Problema:

“Stefan obisnuieste sa -si surprinda  prietenii cu exercitiile de memorie pe care le
face. “Stefan umbla  mereu la el cu un pachet de cartonase care sunt albe pe o
parte si negre pe cealalt . Ultima dat  le-a cerut prietenilor lui s  Ã®nsire toate
100 de cartonase (numerotate de la 1 la 100) în ordine, cu fata alba  Ã®n sus.
S“tefan este legat la ochi si pe rând, câte unul dintre prietenii lui întoarce toate
cartonasele de la i la j. Lui S“tefan i se spun doar valorile lui i si j de la fiecare
întoarcere. Din când în când, prietenii îl testeaz  pe “Stefan întrebându-l ce
culoare are fata de sus a cartonasului k. S“tefan le raspunde mereu corect.

Cerinte:

Proiectati o structura  de date eficienta  care sa  suporte pentru n cartonase cele
2 operatii:
 intoarce(i,j)
 culoare(k)
Analizati complexitatea celor 2 operatii ale structurii de date propuse pentru
cazul cel mai defavorabil. Scrieti un program C care sa  implementeze structura
de date propus  si sa o testeze.

Dupa ce m-am scremut indeajuns de mult(poate mult prea mult) am ajuns la urmatoare concluzie :

Complexitatea minima obtinuta de mine este O(n), insa mi se pare banal de simplu si de aceea sunt convins ca se poate mai eficient.

Apreciez orice ajutor, orice idee, fie ea si gresita.  
Fara cod sau alte minunatii, doar idei.

My first comment

Ce face linia

Cod:

for (; A[0] > 1 && !A[A[0]]; A[0]--); ?

?

Ce inseamna A[A[0]] ?
Ms !

Later Edit : Mi-am dat seama.