Am o casa pe doua planuri cu scara si usi si cu mai multe incaperi. Are cineva prin vre-o carte curs....un algoritm de pathfinding? Adica dintr-un punct al casei sa ajung in alt punct (alta camera alt nivel)?
Grafuri.....
CITAT (edy_3dz @ 18th July 2009, 00:28) 
Grafuri.....
Da...intre timp mi-am dat seama si am avansat in algoritmul problemei. Faza e ca nu am cursurile de grafuri la mine si nu gasesc un algoritm de drum minim intre 2 noduri ale unui graf orientat
Nu stiu daca merge un Djikstra avand in vedere ca eu nu am cost pe arce.
Un model de Floyd pe o matrice de adiacenta imi da si mie cineva :-)???
CITAT (silviana85 @ 18th July 2009, 08:17)
Da...intre timp mi-am dat seama si am avansat in algoritmul problemei. Faza e ca nu am cursurile de grafuri la mine si nu gasesc un algoritm de drum minim intre 2 noduri ale unui graf orientat
Nu stiu daca merge un Djikstra avand in vedere ca eu nu am cost pe arce.
Un model de Floyd pe o matrice de adiacenta imi da si mie cineva :-)???
Nu stiu daca merge un Djikstra avand in vedere ca eu nu am cost pe arce.
Un model de Floyd pe o matrice de adiacenta imi da si mie cineva :-)???
Am gasit
Ai facut cu Djikstra si ai pus cost 1 pe arce? 
CITAT (figo1988 @ 18th July 2009, 20:10)
Ai facut cu Djikstra si ai pus cost 1 pe arce?
Cu Floyd...dar nu imi iese
void Floyd(int graful[10][10],int m,int A[20][20], int Drum[20][20])
{
for (int i=0;i<m;i++)
for (int j=0;j<m;j++)
A[i][j]=graful[i][j];
for (int i=0;i<m;i++)
for(int j=0;j<m;j++)
{ Drum[i][j]=0 ;}
for (int k=0; k<m; k++)
for (int i=0; i<m; i++)
for (int j=0; j<m; j++)
if ( A[i][k] + A[k][j] < A[i][j] )
{
A[i][j] = A[i][k] + A[k][j];
Drum [i][j]=k;
}
}
void Traseu(int i, int j, int Drum[20][20])
{ int k;
if (Drum[i][j]!=0)
{
k=Drum[i][j];
Traseu(i,k,Drum);
cout<<k+1;
Traseu(k,j,Drum);
}
}
Nu afiseaza ce trebuie.....
Floyd determina distantele minime intre oricare 2 noduri din graf (puncte din casa in cazul tau). Cum se aplica floyd aici? Daca tu esti in camera X si vrei sa ajungi in camera y, implementezi algoritmul lui Dijkstra si pui toate muchiile de cost 1. nu are rost sa folosesti floyd warshall pt asa ceva. iar pt a determina drumul efectiv, pastrezi un vector de predecesori de dimensiunea grafului. De fiecare data cand gasesti un drum mai scurt de la x la y prin v (de exemplu), pui ca predecesor al lui y (in vector) pe v.
Defapt tie iti trebuie un algoritm lee. Faci un vector de matrici si ii dai bataie (asta in speranta in care stii algoritmul)
Daca s-a incumetat la Floyd, trebuie sa stie si Lee, presupun
incearca A*
A* ar fi mers doar daca era vorba de drumuri in plan ( adica ar merge si in cazul asta insa mai eficient ar fi un Dijkstra ). Oricum problema principala este modul cum transformi toata suprafata din casa intr-un graf.
CITAT (trident @ 11th September 2009, 19:09)
A* ar fi mers doar daca era vorba de drumuri in plan ( adica ar merge si in cazul asta insa mai eficient ar fi un Dijkstra ). Oricum problema principala este modul cum transformi toata suprafata din casa intr-un graf.
Logic...problema am rezolvat-o de mult. Daca e cineva interesat sa-mi spuna
dar nu crezi ca e mai corect sa spui tu din oficiu iar cel care cauta va gasi direct informatia si nu v-a trebiu sa astepte dupa tine care poate esti in concediu?
as prefera sa nu dai mura in gura ci doar sugestii, tips & co. daca omul vrea sa invete, aici vine si invata. daca nu, sa isi caute alt site.
educarea lenesilor cu "da-mi un pm si-ti zic" la capitolul programare e o mare tampenie. este unul din motivele pt care e plina industria de "prosti". ii dai o chestie banala pe care nu o stie, si in loc sa caute, sa se documenteze iti tranteste un "nu stiu", sau "lucrez la el" dar defapt asteapta raspunsul de pe forum.
as prefera sa nu dai mura in gura ci doar sugestii, tips & co. daca omul vrea sa invete, aici vine si invata. daca nu, sa isi caute alt site.
educarea lenesilor cu "da-mi un pm si-ti zic" la capitolul programare e o mare tampenie. este unul din motivele pt care e plina industria de "prosti". ii dai o chestie banala pe care nu o stie, si in loc sa caute, sa se documenteze iti tranteste un "nu stiu", sau "lucrez la el" dar defapt asteapta raspunsul de pe forum.
CITAT (ciuly @ 12th September 2009, 19:34)
dar nu crezi ca e mai corect sa spui tu din oficiu iar cel care cauta va gasi direct informatia si nu v-a trebiu sa astepte dupa tine care poate esti in concediu?
as prefera sa nu dai mura in gura ci doar sugestii, tips & co. daca omul vrea sa invete, aici vine si invata. daca nu, sa isi caute alt site.
educarea lenesilor cu "da-mi un pm si-ti zic" la capitolul programare e o mare tampenie. este unul din motivele pt care e plina industria de "prosti". ii dai o chestie banala pe care nu o stie, si in loc sa caute, sa se documenteze iti tranteste un "nu stiu", sau "lucrez la el" dar defapt asteapta raspunsul de pe forum.
as prefera sa nu dai mura in gura ci doar sugestii, tips & co. daca omul vrea sa invete, aici vine si invata. daca nu, sa isi caute alt site.
educarea lenesilor cu "da-mi un pm si-ti zic" la capitolul programare e o mare tampenie. este unul din motivele pt care e plina industria de "prosti". ii dai o chestie banala pe care nu o stie, si in loc sa caute, sa se documenteze iti tranteste un "nu stiu", sau "lucrez la el" dar defapt asteapta raspunsul de pe forum.
Ok Ok: am folosit Floyd-Warshall.
Legatura dintre camere(usile) sunte arcele unui graf....am lucrat cu coordonatele coltului inferior dreapta al fiecarei camere.
Pentru a determina cel mai scurt drum intre 2 noduri ale unui graf este sa folosesti algoritmul lui lee, e foarte si simplu si eficient
http://en.wikipedia.org/wiki/Lee_algorithm
http://en.wikipedia.org/wiki/Lee_algorithm
O fi eficient pentru un graf mic. Pentru grafuri mari , folosesti "jucarii" mari, precum djkistra...
In curand... autoevolution.ro
Teste, stiri, ghiduri, jurnale, forum si multe altele!
Teste, stiri, ghiduri, jurnale, forum si multe altele!
Aceasta este o versiune simplificatã a paginii originale. Pentru a vizita versiunea originala click aici.