Algoritmul de urmărire a undelor ( algoritmul undelor , algoritmul lui Lee ) este un algoritm de găsire a căii , un algoritm pentru găsirea celei mai scurte căi pe un grafic plan . Aparține algoritmilor bazați pe metode de căutare pe lățimea întâi .
Este utilizat în principal în urmărirea computerizată (cablarea) plăcilor de circuite imprimate , conectarea conductoarelor pe suprafața microcircuitelor. O altă aplicație a algoritmului unde este găsirea celei mai scurte distanțe pe o hartă în jocurile de strategie pe computer.
Algoritmul undelor în contextul găsirii unei căi într-un labirint a fost propus de E. F. Moore [2] . Lee a descoperit în mod independent același algoritm în timp ce formaliza algoritmii de rutare a plăcilor de circuite în 1961 [3] [4] [5] .
Algoritmul funcționează pe un câmp de lucru discret (DWP), care este o figură delimitată de o linie închisă, nu neapărat dreptunghiulară, împărțită în celule dreptunghiulare, într-un caz particular, pătrate. Setul tuturor celulelor DRP este împărțit în subseturi: „accesibil” (gratuit), adică, atunci când se caută o cale, acestea pot fi trecute, „netrecătoare” (obstacole), calea prin această celulă este interzisă, celula de pornire (sursă ) și finisare (receptor). Atribuirea celulelor de început și de sfârșit este condiționată, este suficient să indicați o pereche de celule între care trebuie să găsiți calea cea mai scurtă.
Algoritmul este conceput pentru a găsi calea cea mai scurtă de la celula de pornire la celula finală, dacă este posibil, sau, în absența unei căi, să emită un mesaj despre obstrucție [6] .
Funcționarea algoritmului include trei etape: inițializarea , propagarea undelor și recuperarea căii .
În timpul inițializării, este construită o imagine a unui set de celule din câmpul procesat, atributele de trecere/obstrucție sunt atribuite fiecărei celule, celulele de început și de sfârșit sunt memorate.
În plus, din celula de pornire, se generează un pas în celula vecină, verificând în același timp dacă este acceptabil și dacă aparține celulei marcate anterior în traseu.
Celulele învecinate sunt de obicei clasificate în două moduri: în sensul cartierului Moore și al cartierului von Neumann , care diferă prin aceea că în cartierul von Neumann, doar 4 celule pe verticală și orizontală sunt considerate celule învecinate, în cartierul Moore, toate cele 8 celule. celule, inclusiv cele diagonale.
Dacă sunt îndeplinite condițiile de trecere și nu aparține celulelor marcate anterior pe parcurs, în atributul celulei se scrie un număr egal cu numărul de pași din celula de pornire, din celula de pornire la primul pas va fi 1. Fiecare celulă marcată cu numărul de pași din celula de pornire devine cea de pornire și din aceasta se generează pașii următori în celulele vecine. Evident, cu o astfel de căutare se va găsi o cale de la celula inițială la cea finală, sau următorul pas din orice celulă generată în cale va fi imposibil.
Restabilirea căii celei mai scurte are loc în direcția opusă: la selectarea unei celule de la celula finală la celula de început, la fiecare pas este selectată o celulă care are un atribut de distanță de la început mai mic decât celula curentă. Evident, în acest fel se găsește calea cea mai scurtă între o pereche de celule date [6] . Pot exista mai multe urme cu o lungime numerică minimă a căii, atât la căutarea unei căi în vecinătatea lui Moore, cât și a lui von Neumann. Alegerea căii finale în aplicații este dictată de alte considerații în afara acestui algoritm. De exemplu, la trasarea plăcilor de circuite imprimate - lungimea liniară minimă a conductorului așezat.
Inițializare
Marcați celula de început d := 0Propagarea undelor
LOOP PENTRU fiecare celulă loc marcată cu numărul d marchează toate celulele învecinate libere nemarcate cu numărul d + 1 KC d := d + 1 YET (celula finală nu este marcată) ȘI (există posibilitatea de propagare a undelor)Recuperarea traseului
DACĂ terminați celula etichetată ATUNCI du-te să termin celula CICLU selectați dintre celulele învecinate marcate cu un număr 1 mai mic decât numărul din celula curentă mergeți la celula selectată și adăugați-o la cale ÎN CÂT timp celula curentă nu este celula de pornire calea RETURN găsită ELSE calea RETURN nu a fost găsită| Algoritmi de căutare grafică | ||
|---|---|---|
| Metode neinformate | ||
| Metode informate | ||
| Comenzi rapide | ||
| Arborele de întindere minim | ||
| Alte | ||