Algoritmul lui Lee

[•dornescuvlad]

poate cineva sa posteze alg lui lee va rog? eventual  cu niste explicatii?multumesc
am inteles algoritmul de parcurgere in latime,mai departe nu stiu ce sa fac.n-am rabdare pana imi explica profesorul,vreau sa stiu acum

[•alexandru92]

S-a vorbit de multe ori pe forum despre "lee". Acesta este primul topic gasit http://infoarena.ro/forum/index.php?topic=4035.0 .

[•dornescuvlad]

omule nu cunosc decat limbajul clasic c++.daca puteam descifra,fii sigur ca nu mai intrebam

[•Mishu91]

Încearcă să înțelegi algoritmul, nu o sursă. Descrierea de acolo e destul de bună, clarifică in mare algoritmul.

[•alexandru92]

omule nu cunosc decat limbajul clasic c++.daca puteam descifra,fii sigur ca nu mai intrebam

Nu exista limbajul clasica c++. Exista c++ si c. Cand zici c++ ma gandesc la STL si OOP, ma rog si multe alte chesti, tu poate cunosti "c" ( adica daca inlocuiesti cin/cout cu scanf/printf ar fi un program in c ).
Oricum, cum am zis s-a vorbit de mai multe ori pe forum, cauta! Acela a fost primul topic gasit
ps: lee e un simplu bfs ... daca tot ai zis ca l-ai inteles

[•sima_cotizo]

tu poate cunosti "c" ( adica daca inlocuiesti cin/cout cu scanf/printf ar fi un program in c ).

Ai STL acolo. Daca esti asa binevoitor, incearca sa ii explici si fara STL.

@Vlad: totusi, Alexandru are dreptate. Lee-ul este un BFS in limbaj popular la noi.

[•dornescuvlad]

poate cineva sa posteze alg lui lee va rog? eventual  cu niste explicatii?multumesc
am inteles algoritmul de parcurgere in latime,mai departe nu stiu ce sa fac.n-am rabdare pana imi explica profesorul,vreau sa stiu acum

mah pana la urma tu ce vrei. nu cumva ai nevoie de algoritmul pentru problema labirintului cu matrice??

da asta am vrut

[•alexandru92]

O sa scriu "lee-ul" in pseudocod a.i toti o sa-l inteleaga.
Structuri de date folosite:
L - retine lista de adiacenta a grafului
x - nodul de start
y, u - un nod din graf
Q - o coada de tip intreg
begin, end -  pozitia de inceput si sfarsit a cozi
dis - un vector , initial contine doar 0,  retin distanta de la nodul x la orice alt nod, daca se poate

Cod:

begin=end=1;
Q[begin]=x;
pentru begin=1 pana la end executa
    y=Q[begin];
    pentru u <- L[y] executa //pentru u aparatinand lui L[y] executa
          daca 0 == dist[u] atunci
                dist[u]=dist[y]+1;
           sfarsit_daca;
    sfarsit_pentru;
sfarsit_pentru;

Sper sa intelegi ...

[•alexandru92]

il gaseshti in cartile pentru grupele de performantza.
si nu NU E CU GRAFURI BFS SAU ALTA ABUREALA E DOAR LEE

Lee e un simplu BFS, desigur el poate fi adaptat

[•wefgef]

Incercati sa nu va abateti de la topic, puteti sa va purtati disputele in privat.

Legat de

si nu NU E CU GRAFURI BFS SAU ALTA ABUREALA E DOAR LEE

Nu e bine sa sustii sus si tare o chestiune, mai ales cand nu stapensti subiectul, si pe deasupra nici nu ai dreptate.

[•dornescuvlad]

deci cum e pana la urma?

[•sima_cotizo]

Pai pana la urma, cel mai bun raspuns din topic este asta. Daca nu intelegi ce se intampla pe acolo, in loc de "nod in graf" gandeste-te la "celula in matrice" si ar trebui sa fie mai clar...

[•alexandru92]

deci cum e pana la urma?

Deci pana la urma, lee este un simplu bfs pentru gasirea celui mai scrut drum de la nodul x la nodul y. Cand vine vorba de gasirea unui drum intre 2 puncte poti sa-l folosestie . Desigur, cand vine vorba de date de intrare foarte mari, sau probleme serioase ( o sa vezi mai tarziu ) iti recomand sa treci peste jucaria asta si sa folosesti Dijikstra, Bellman-Ford , A*, ...etc

[•yonatan]

deci cum e pana la urma?

Deci pana la urma, lee este un simplu bfs pentru gasirea celui mai scrut drum de la nodul x la nodul y. Cand vine vorba de gasirea unui drum intre 2 puncte poti sa-l folosestie . Desigur, cand vine vorba de date de intrare foarte mari, sau probleme serioase ( o sa vezi mai tarziu ) iti recomand sa treci peste jucaria asta si sa folosesti Dijikstra, Bellman-Ford , A*, ...etc

vrei sa zici ca la problema labirintului merge un dijkstra modificat sau la ce te referi ca lui ii trebuie pentru labirint nu pentru grafuri

[•alexandru92]

vrei sa zici ca la problema labirintului merge un dijkstra modificat sau la ce te referi ca lui ii trebuie pentru labirint nu pentru grafuri

Eu ma refeream, cand vine vorba de probleme serioare ca  pathfinding intr-o casa, sau altele .