BFS - Parcurgere in latime

Parcurgere in latime

h2. Aplicatii

Algoritmul de parcurgere in latime ({_Breadth First Search_}) poate fi adaptat in multe probleme. De exemplu, la problema 'Muzeu':problema/muzeu putem consideram matricea data un graf in care celulele sunt noduri, iar laturile comune dintre celule sunt muchii. La problema "CrazySwitches":http://www.topcoder.com/stat?c=problem_statement&pm=6071&rd=9812, graful este reprezentat de stari binare, iar muchiile de posibilitatea de a ne deplasa dintr-o stare in alta. Un tip mai aparte de BFS, prezent si in problema anterioara, este acela cand costurile de pe muchii sunt mici si pentru a rezolva problema folosim mai multe cozi (complexitatea fiind mai mica decat daca am folosi algoritmul 'Dijkstra':problema/dijkstra). Mai multe explicatii asupra acestui procedeu gasiti in acest 'articol':preoni-2005/runda-2/solutii, la problema 'Car':problema/car. Alte probleme ce folosesc algoritmul de parcurgere in latime in rezolvare sunt:

Algoritmul de parcurgere in latime ({_Breadth First Search_}) poate fi adaptat in multe probleme. De exemplu, la problema "Muzeu":/problema/muzeu putem consideram matricea data un graf in care celulele sunt noduri, iar laturile comune dintre celule sunt muchii. La problema "CrazySwitches":http://www.topcoder.com/stat?c=problem_statement&pm=6071&rd=9812, graful este reprezentat de stari binare, iar muchiile de posibilitatea de a ne deplasa dintr-o stare in alta. Un tip mai aparte de BFS, prezent si in problema anterioara, este acela cand costurile de pe muchii sunt mici si pentru a rezolva problema folosim mai multe cozi (complexitatea fiind mai mica decat daca am folosi algoritmul "Dijkstra":/problema/dijkstra). Mai multe explicatii asupra acestui procedeu gasiti in acest "articol":/preoni-2005/runda-2/solutii, la problema "Car":/problema/car. Alte probleme ce folosesc algoritmul de parcurgere in latime in rezolvare sunt:

* 'Graf':problema/graf
* 'Sate':problema/sate

* 'Graf':/problema/graf
* 'Sate':/problema/sate

* "Cadere":http://campion.edu.ro/problems/3/455/cadere_ro.htm
* "Honest":http://campion.edu.ro/problems/3/237/honest_ro.htm

* 'Padure':problema/padure

* 'Padure':/problema/padure

== include(page="template/taskfooter" task_id="bfs") ==

3448