• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Parcurgerea in latime – Lee

0
  • Publicat de Andrei Avădănei
  • în C/C++ · Tehnic
  • — 9 apr., 2010 at 8:00 am

Parcurgerea in latime este cunoscuta si ca algoritmul lui Lee in lumea algoritmicii romanesti sau BFS (Breath First Search) in lumea grafurilor este la baza un algoritm de cautare ce sunt folositi in general pentru a afla drumul de lungime minima intre doua noduri.

Prezentarea algoritmului

Algoritmul are la baza o metoda iterativa. Fiecare vecin va fi bagat, iar la extragerea unuia din coada vom baga in coada toti vecinii nevizitati ai nodului curent (avand grija sa eliminam nodul curent). Algoritmul se repeta pana cand coada devine vida sau gasim solutia asteptata.

Implementare in pseudocod

intreg m[100][100];
coada c;
functie bfs(nod p)
{
   adaug_in_coada(p);
   m[k.x][k.y]=1; //vizitez nodul
   pentru(i=0;i< =n+1;i++) m[i][0]=m[i][m+1]=1; //bordam coloanele marginale
   pentru(i=0;i<=m+1;i++) m[0][i]=m[n+1][i]=1; //bordam liniile marginale
   cat_timp(c <> NULL)
   {
      k = scot_din_coada(c);
      pentru_fiecare_nod(vecin din k)
      {
          daca(m[vecin.x][vecin.y]==0) //daca vecinul e nevizitat
          { 
              m[vecin.x][vecin.y]=1; //il vizitez
              adaug_in_coada(vecin);
          }
      }
      sterg_din_coada(k);
   }
}

Aplicatii

1. Problema alee de pe .campion

Parcul orasului a fost neglijat mult timp, astfel ca acum toate aleile sunt distruse. Prin urmare, anul acesta Primaria si-a propus sa faca reamenajari.
Parcul are forma unui patrat cu latura de n metri si este inconjurat de un gard care are exact doua porti. Proiectantii de la Primarie au realizat o harta a parcului si au trasat pe harta un caroiaj care imparte parcul in nxn zone patrate cu latura de 1 metru. Astfel harta parcului are aspectul unei matrice patratice cu n linii si n coloane. Liniile si respectiv coloanele sunt numerotate de la 1 la n. Elementele matricei corespund zonelor patrate de latura 1 metru. O astfel de zona poate sa contina un copac sau este libera.
Edilii orasului doresc sa paveze cu un numar minim de dale patrate cu latura de 1 metru zonele libere (fara copaci) ale parcului, astfel incat sa se obtina o alee continua de la o poarta la alta.

Solutie
Rezolvarea acestei probleme este o aplicatie clara a algoritmului BFS pe matrici.

2. Problema RJ de pe .campion

In ultima ecranizare a celebrei piese shakespeariene Romeo si Julieta traiesc intr-un oras modern, comunica prin e-mail si chiar invata sa programeze. Intr-o secventa tulburatoare sunt prezentate framantarile interioare ale celor doi eroi incercand fara succes sa scrie un program care sa determine un punct optim de intalnire.
Ei au analizat harta orasului si au reprezentat-o sub forma unei matrice cu n linii si m coloane, in matrice fiind marcate cu spatiu zonele prin care se poate trece (strazi lipsite de pericole) si cu X zonele prin care nu se poate trece. De asemenea, in matrice au marcat cu R locul in care se afla locuinta lui Romeo, iar cu J locul in care se afla locuinta Julietei.
Ei se pot deplasa numai prin zonele care sunt marcate cu spatiu, din pozitia curenta in oricare dintre cele 8 pozitii invecinate (pe orizontala, verticala sau diagonale).
Cum lui Romeo nu ii place sa astepte si nici sa se lase asteptat n-ar fi tocmai bine, ei au hotarat ca trebuie sa aleaga un punct de intalnire in care atat Romeo, cat si Julieta sa poata ajunge in acelasi timp, plecand de acasa. Fiindca la intalniri amandoi vin intr-un suflet, ei estimeaza timpul necesar pentru a ajunge la intalnire prin numarul de elemente din matrice care constituie drumul cel mai scurt de acasa pana la punctul de. intalnire. Åži cum probabil exista mai multe puncte de intalnire posibile, ei vor sa il aleaga pe cel in care timpul necesar pentru a ajunge la punctul de intalnire este minim.

Solutie
O aplicatie foarte interesanta, ideea cea mai buna este de a face BF pornind atat din directia lui Romeo cat si din cea a Julietei. Pentru a obtine solutia minima, vom cauta solutia cea mai buna ce coincide celor doua matrici „vizitate” create de BFS.

3. Problema sotron1 de pe .campion

Ana si Bogdan au inventat un nou model de sotron. Ei deseneaza cu creta pe asfalt un caroiaj format din NxM patrate organizate in N linii si M coloane. O parte dintre aceste patrate le coloreaza in rosu, celelalte in verde. In plus, un patrat este selectat ca patrat de start si un alt patrat ca patrat de final (acestea sunt verzi).
Scopul jocului este ca jucatorul sa ajunga de la patratul de start la patratul final in cel mai scurt timp. Regulile jocului sunt:

1. este interzis ca jucatorul sa paseasca intr-un patrat rosu; este permis sa se deplaseze doar in cele verzi;
2. atunci cand jucatorul ajunge intr-un patrat el se poate deplasa in patratul din fata sa, in cel din stanga sa sau in cel din dreapta sa (fata, stanga, dreapta sunt stabilite evident in functie de sensul de mers); prin urmare este interzis ca un jucator sa se deplaseze inapoi sau in diagonala; de asemenea este interzis ca jucatorul sa paraseasca caroiajul;
3. de-a lungul intregului drum de la start la final sunt permise in total cel mult K deplasari la dreapta;
4. initial, cand jucatorul este plasat in patratul de start, el poate alege ce sens de deplasare doreste;
5. deplasarea de la un patrat la altul dureaza o secunda.
Solutie
Vom aplica algoritmul lui Lee, adaptat restrictiilor din enunt. Vom utiliza o coada in care vom introduce pozitiile de joc:
Cat timp coada nu este vida:
– extrag o pozitie din coada
– verific vecinii pozitiei extrase si daca este posibil (repsecta conditiile) ii introduc in coada.
Cum se realizeaza verificarea vecinilor? In primul rand trebuie sa verificam ca pozitia urmatoare este pe tabla de joc.

Apoi ca acea pozitie nu mai fost vizitata. In acest scop vom utiliza un tablou uz cu 4 dimensiuni : uz[i][j][d][r]= 1 daca am ajuns pe linia i, coloana j deplasandu-ne in directia d, avand r deplasari dreapta disponibile.

Alte aplicatii

http://campion.edu.ro/arhiva/index.php?page=keyword&action=view&id=26

Etichete: algoritm de cautare pe grafurialgoritmul lui leebfsbreath first searchdrum de lungime minimagrafleeparcurgerea in latime

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior Website in 6 pasi si fara coding
  • Articolul următor Stive [C]

  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • aprilie 2021
    L Ma Mi J V S D
     1234
    567891011
    12131415161718
    19202122232425
    2627282930  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Parcurgerea in latime – Lee
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons