Algoritmul Floyd-Warshall pentru determinarea tuturor drumurilor de cost minim
6Avem o problema clasica de grafuri. Se da un graf orientat cu N noduri, memorat prin matricea ponderilor. Determinati pentru orice pereche de noduri x si y lungimea minima a drumului de la nodul x la nodul y, afisandu-se matricea drumurilor minime. Prin lungimea unui drum intelegem suma costurilor arcelor care-l alcatuiesc. Problema se gaseste pe infoarena.
Aceasta problema ar putea fi rezolvata prin algoritmi clasici pentru determinarea unui drum de cost minim intre doua noduri in complexitate O(n^3*logn) – cel mai optim. Totusi, algoritmul Floyd-Warshall (sau chiar Roy-Floyd) rezolva problema prin programare dinamica in complexitate n^3. Consideram toate varfurile intermediare k(k=1,2,…,n) si verificam pentru fiecare pereche de varfuri din graf x,y daca trecand prin k se optimizeaza costul de la x la y; in caz afirmativ, costul drumului de la x la y se modifica. Observam ca dupa pasul k in matricea costurilor, pe pozitia (x,y), se afla costul drumului de cost minim de la x la y care trece numai prin varfuri intermediare din multimea {1,2,….,k}.
Aplicarea algoritmului Floyd-Warshall
#include<cstdio> using namespace std; void read(),solve(),show(); int n,a[105][105]; int main() { read(); solve(); show(); return 0; } void read() { int j; freopen("royfloyd.in","r",stdin); freopen("royfloyd.out","w",stdout); scanf("%d",&n); for(int i = 0; i < n; i++) for(j = 0; j < n; j++) scanf("%d",&a[i][j]); } void solve() { int i,j; for(int k = 0; k < n; k++) for(i = 0; i < n; i++) for(j = 0; j < n; j++) //daca putem actualiza if(a[i][k] && a[k][j] && i != j && (a[i][j] > a[i][k] + a[k][j] || !a[i][j])) a[i][j] = a[i][k] + a[k][j]; } void show() { int j; //afisam matricea costurilor for(int i = 0; i < n; i++,printf("\n")) for(j = 0 ; j < n; j++) printf("%d ", a[i][j]); }
Algoritmul are o aplicabilitate in diverse probleme de informatica dar si in alte categorii ale domeniului de programare. Pentru a aprofunda si mai bine algoritmul am ales o problema ceva mai dificila ce se bucura de o solutie folosind algoritmul prezentat anterior.
Problema Coach
Sunteti antrenorul ciclistului Adirem Onamihs care, in ciuda numelui ciudat, este foarte talentat. In curant va avea loc un eveniment sportiv, un prilej foarte bun de a-l antrena pe ciclist. Pentru organizarea evenimentului s-au amenajat N intersectii si M drumuri bidirectionale intre aceste intersectii. Pentru fiecare drum se cunosc numarul de minute necesare pentru parcurgerea lui. La fiecare intersectie ciclistul care trece pe acolo este obligat sa serveasca o bautura energizanta si racoritoare. Bautura difera de la intersectie la intersectie si se cunosc deja numarul de calorii ale fiecarei bauturi.
Ca un mare antrenor, aveti un plan special pentru Adirem. Doriti ca durata traseului pe care il alege Adirem sa aiba exact T ore, insa nu vreti sa-i planuiti intregul traseu (Adirem trebuie sa isi antreneze si mintea, nu numai corpul). Ii veti preciza lui Adirem doar intersectia de unde isi incepe traseul si intersectia unde il termina. Adirem invata repede – el stie intotdeauna sa aleaga traseul optim (drumul cel mai scurt dintre cele doua intersectii). Atunci cum il puteti face sa mearga exact T ore? Dupa cateva portii de creatina, va vine ideea salvatoare: ii veti interzice trecerea prin anumite intersectii, sub pretextul ca valoarea calorica a bauturii servite in intersectia respectiva nu este benefica pentru antrenamentul lui. Astfel, ii veti preciza o limita inferioara si una superioara pentru numarul de calorii ale bauturilor pe care el are voie sa le bea. Adirem nu va trece decat prin intersectiile unde se serveste o bautura cu valoare calorica intre limitele date.
Cum numarul de intersectii este destul de mare, va trebui sa scrieti un program care sa calculeze cele patru variabile in antrenamentul lui Adirem: intersectia de start, intersectia de finish, valoarea calorica minima pe care poate sa o consume si valoarea calorica maxima, astfel incat drumul cel mai scurt dintre cele doua intersectii (care sa respecte restrictiile) sa dureze T minute.
Solutie Coach
Se observa aproape imediat nevoia stabilirii tuturor drumurilor minime. Particularitatea problemei o constituie faptul cum va fi afisata solutia – intre doua valori intermediare (in functie de valorile calorice ale bauturilor). Putem sa ne folosim de proprietatea algoritmului prezentata mai sus si sa deducem ca putem sorta nodurile dupa valoarea fiecaruia avand grija sa renumerotam nodurile. Vom fixa un nod de inceput „start” (si implicit un cost minim), dupa care aplicam algoritmul Floyd-Warshall pentru nodurile cu valoarea cel putin egala cu costul minim (avand grija sa luam doar nodurile de la s la N). Proprietatea pe care ne bazam este urmatoarea : la pasul k (s <= k <= N), avem C[i][j] este drumul minim de la i la j care poate trece prin nodurile cuprinse intre s si k. Implementand aceasta abordare a problemei vom avea complexitatea O(n^4) ce vine din algoritmul Floyd-Warshall + particularitatea noastra de a parcurge toate costurile sortate.
#include<cstdio> #include<iostream> #define INF 1<<25 using namespace std; int n[101],NN[101],RNN[101],ori[101][101],a[101][101],N,M,T,start,end,smax,smin; void read(),solve(); int main() { read(); solve(); return 0; } void read() { int i,j,c,aux; freopen("coach.in","r",stdin); freopen("coach.out","w",stdout); scanf("%d%d%d",&N,&M,&T); for(i=1;i<=N;i++) scanf("%d",&n[i]),RNN[i]=NN[i]=i; //sortam si renumeratom indicii simultan for(i=1;i<N;i++) for(j=i+1;j<=N;j++) if(n[i] > n[j]) { RNN[NN[i]]=j;RNN[NN[j]]=i; aux=n[i];n[i]=n[j];n[j]=aux; aux=NN[i];NN[i]=NN[j];NN[j]=aux; } //citim muchiile renumerotate ca se le asezam unde trebuie for(;M;M--) scanf("%d%d%d",&i,&j,&c),ori[RNN[j]][RNN[i]]=ori[RNN[i]][RNN[j]]=c; } void solve() { int s,i,j,k; for(s=1;s<=N;s++) //pentru fiecare s { //reset for(i=1;i<=N;i++) for(j=1;j<=N;j++) a[i][j]=(i >= s && j >= s && ori[i][j]) ? ori[i][j] : INF; //floyd-warshall for(k=s;k<=N;k++) { for(i=s;i<=N;i++) if(a[i][k]<=INF) for(j=s;j<=N;j++) if(a[i][j] > a[i][k] + a[k][j]) a[i][j]=a[i][k]+a[k][j]; //daca avem intre s si k T-ul cautat for(i=s;i<=k;i++) for(j=s;j<=k;j++) if(a[i][j]==T) { start = NN[i]; smin = n[s]; end = NN[j]; smax = n[k]; printf("%d %d %d %d\n",start, end, smin, smax); return; } } } }
Pentru a aprofunda mai bine acest algoritm va recomand si aceste doua probleme – Rfinv si Roy-Floyd ce sunt mai simplute.
Din cate imi amintesc se putea la coach si in O(n^3) daca se facea o observatie, mai dificila evident, ca nu conteaza ambele valori, ci numai una, si folosindu-ne de faptul ca nu trebuie sa facem pentru fiecare nod un roy-floyd, ci putem sorta nodurile dupa energia bauturii. Avand in vedere ca la fiecare pas din roy-floyd incercam sa adaugam nodul curent in lanturile minime dintre noduri, valoare maxima a energiei va creste la fiecare pas sau va ramane egala, pentru fiecare drum minim intre i si j(oricare ar fi i si j de la 1 la n). Astfel se formeaza solutia in O(n^3):
1)Sortam nodurile dupa valoarea energetica
2) Aplicam roy-floyd
3) La fiecare pas in roy-floyd, dupa ce micsoram lanturile, verificam daca avem un lant de lungime T(dureaza T minute) si daca da ne oprim.
4) Limita inferioara va fi 0 iar cea superioara va fi valoarea energetica a bauturii din orasul la care ne-am oprit in roy-floyd.
Eu cel putin asa am rezolvat, sper sa ajute pe cineva
Salut . Scuze daca sunt pe langa subiect. Asi avea o intrebare:
Dupa cum stiti , se pot extrage date dintr-un fisier XML cu ajutorul unui cod PHP care extrage anumite date specificate in codul PHP .. aici referindune la tag-urile de la care vrem sa extragem datele.
Se poate sa extragem doar anumite date ? De exemplu intr-un fisier XML care contine titlu de haine . Se poate sa extragem din fisierul XML doar datele care contin numele blugi spre exemplu .. sau tricou ?
Raspunsul la intrebarea ta e da. Doar ca nu ai nici o treaba cu acest subiect de aceea nu voi intra in detalii. Vrei mai multe raspunsuri, exista forumul worldit.
super tare problema :>
Buna ziua, folosesc pluginul WordPress Code Snippet pentru cod si as vrea sa stiu cum pot face sa fie codul mai mic sau textu, exact cum aveti pe acest blog . Ma intereseaza pentru un prieten .
E vorba de font-size din CSS. 🙂