infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Vlad Eugen Dornescu din Noiembrie 12, 2009, 15:35:02

Titlul: Algoritmul lui Lee
Scris de: Vlad Eugen Dornescu din Noiembrie 12, 2009, 15:35:02

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 :readthis:

Titlul: RÄƒspuns: Algoritmul lui Lee
Scris de: alexandru din Noiembrie 12, 2009, 19:30:18

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

Titlul: RÄƒspuns: Algoritmul lui Lee
Scris de: Vlad Eugen Dornescu din Noiembrie 12, 2009, 19:43:18

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

Titlul: RÄƒspuns: Algoritmul lui Lee
Scris de: Andrei Misarca din Noiembrie 12, 2009, 21:12:50

ÃŽncearcÄƒ sÄƒ Ã®nÈ›elegi algoritmul, nu o sursÄƒ. Descrierea de acolo e destul de bunÄƒ, clarificÄƒ in mare algoritmul.

Titlul: RÄƒspuns: Algoritmul lui Lee
Scris de: alexandru din Noiembrie 13, 2009, 18:34:46

Citat din mesajul lui: Dornescu Vlad-Eugen din Noiembrie 12, 2009, 19:43:18

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 :P ).
Oricum, cum am zis s-a vorbit de mai multe ori pe forum, cauta! Acela a fost primul topic gasit :P
ps: lee e un simplu bfs :P ... daca tot ai zis ca l-ai inteles

Titlul: RÄƒspuns: Algoritmul lui Lee
Scris de: Sima Cotizo din Noiembrie 13, 2009, 20:23:59

Citat din mesajul lui: alexandru din Noiembrie 13, 2009, 18:34:46

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

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.

Titlul: RÄƒspuns: Algoritmul lui Lee
Scris de: Vlad Eugen Dornescu din Noiembrie 14, 2009, 13:39:56

Citat din mesajul lui: Calin Dragos Ion din Noiembrie 14, 2009, 12:51:12

Citat din mesajul lui: Dornescu Vlad-Eugen din Noiembrie 12, 2009, 15:35:02

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

da asta am vrut

Titlul: RÄƒspuns: Algoritmul lui Lee
Scris de: alexandru din Noiembrie 14, 2009, 19:05:06

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

Titlul: RÄƒspuns: Algoritmul lui Lee
Scris de: alexandru din Noiembrie 14, 2009, 20:27:14

Citat din mesajul lui: Calin Dragos Ion din Noiembrie 14, 2009, 20:01:12

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

Titlul: RÄƒspuns: Algoritmul lui Lee
Scris de: Andrei Grigorean din Noiembrie 15, 2009, 00:14:17

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

Legat de

Citat

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.

Titlul: RÄƒspuns: Algoritmul lui Lee
Scris de: Vlad Eugen Dornescu din Noiembrie 15, 2009, 06:36:12

deci cum e pana la urma? :sad:

Titlul: RÄƒspuns: Algoritmul lui Lee
Scris de: Sima Cotizo din Noiembrie 15, 2009, 11:38:00

Pai pana la urma, cel mai bun raspuns din topic este asta (http://infoarena.ro/forum/index.php?topic=4254.msg36010#msg36010). 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...

Titlul: RÄƒspuns: Algoritmul lui Lee
Scris de: alexandru din Noiembrie 15, 2009, 11:44:40

Citat din mesajul lui: Dornescu Vlad-Eugen din Noiembrie 15, 2009, 06:36:12

deci cum e pana la urma? :sad:

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 ;)

Titlul: RÄƒspuns: Algoritmul lui Lee
Scris de: Cont de teste din Noiembrie 15, 2009, 14:30:49

Citat din mesajul lui: alexandru din Noiembrie 15, 2009, 11:44:40

Citat din mesajul lui: Dornescu Vlad-Eugen din Noiembrie 15, 2009, 06:36:12

deci cum e pana la urma? :sad:

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

Titlul: RÄƒspuns: Algoritmul lui Lee
Scris de: alexandru din Noiembrie 15, 2009, 16:12:23

Citat din mesajul lui: proistosescu george din Noiembrie 15, 2009, 14:30:49

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 :P.