Aaltojäljitysalgoritmi ( aaltoalgoritmi , Leen algoritmi ) on polunetsintäalgoritmi , algoritmi lyhimmän polun löytämiseksi tasograafista . Kuuluu algoritmeihin, jotka perustuvat leveysensin hakumenetelmiin .
Sitä käytetään pääasiassa painettujen piirilevyjen tietokonejäljittämisessä (johdotuksessa) , jotka yhdistävät johtimia mikropiirien pinnalle. Toinen aaltoalgoritmin sovellus on lyhimmän etäisyyden etsiminen kartalta tietokonestrategiapeleissä.
E. F. Moore ehdotti aaltoalgoritmia polun löytämisen yhteydessä sokkelosta [2] . Lee löysi itsenäisesti tämän saman algoritmin formalisoidessaan piirilevyjen reititysalgoritmeja vuonna 1961 [3] [4] [5] .
Algoritmi toimii diskreetillä työkentällä (DWP), joka on suljetulla viivalla, ei välttämättä suorakaiteen muotoisella, jaettuna suorakaiteen muotoisiin soluihin, tietyssä tapauksessa neliöihin. Kaikkien DRP-solujen joukko on jaettu osajoukkoihin: "passable" (vapaa), eli polkua etsittäessä ne voidaan ohittaa, "läpäisemättömät" (esteet), polku tämän solun läpi on kielletty, aloitussolu (lähde) ) ja viimeistely (vastaanotin). Aloitus- ja lopetussolujen määrittäminen on ehdollista, riittää, kun ilmoitetaan solupari, joiden välillä sinun on löydettävä lyhin polku.
Algoritmi on suunniteltu etsimään mahdollisuuksien mukaan lyhin polku aloitussolusta viimeiseen soluun, tai jos polkua ei ole, antamaan viesti esteestä [6] .
Algoritmin toiminta sisältää kolme vaihetta: alustus , aallon eteneminen ja polun palautus .
Alustuksen aikana muodostetaan kuva käsitellyn kentän solujoukosta, kullekin solulle osoitetaan läpäisevyyden/esteen attribuutit, aloitus- ja loppusolut muistetaan.
Edelleen aloitussolusta generoidaan askel naapurisoluun, samalla kun tarkistetaan, onko se läpäistävissä ja kuuluuko se aiemmin polkuun merkittyyn soluun.
Naapurisolut luokitellaan yleensä kahdella tavalla: Mooren naapurustossa ja von Neumannin naapurustossa , joka eroaa siinä, että von Neumannin naapurustossa vain 4 solua pystysuunnassa ja vaakasuunnassa katsotaan naapurisoluiksi, Mooren naapurustossa kaikki 8 solut, mukaan lukien diagonaaliset.
Jos hyväksyttävyysehdot täyttyvät eikä se kuulu matkalla aiemmin merkittyihin soluihin, solun attribuutille kirjoitetaan aloitussolusta askelmäärää vastaava luku, ensimmäisen vaiheen aloitussolusta 1. Jokainen aloitussolun askelmäärällä merkitty solu tulee aloitussoluksi ja siitä muodostetaan seuraavat vaiheet viereisiin soluihin. Ilmeisesti tällaisella haulla löydetään polku alkuperäisestä solusta lopulliseen, tai seuraava askel mistä tahansa polulle luodusta solusta on mahdoton.
Lyhimmän polun palautus tapahtuu päinvastaiseen suuntaan: valittaessa solua loppusolusta aloitussoluun valitaan jokaisessa vaiheessa solu, jonka attribuutti on etäisyys aloituksesta yhtä pienempi kuin nykyinen solu. Ilmeisesti tällä tavalla löydetään lyhin polku tietyn soluparin välillä [6] . Vähimmäisellä numeerisella polun pituudella voi olla useita jälkiä, sekä etsittäessä polkua Mooren ja von Neumannin läheisyydestä. Lopullisen polun valinta sovelluksissa määräytyy muista tämän algoritmin ulkopuolisista seikoista. Esimerkiksi painettuja piirilevyjä jäljitettäessä - asennetun johtimen lineaarinen vähimmäispituus.
Alustus
Merkitse aloitussolu d := 0Aallon leviäminen
SILMUKAALLE jokaiselle numerolla d merkitylle solupaikalle merkitse kaikki viereiset vapaat merkitsemättömät solut numerolla d + 1 KC d := d + 1 YET (lopetussolua ei ole merkitty) JA (on mahdollisuus aallon etenemiseen)Polun palautuminen
JOS viimeistely solu merkitty NIIN mene loppuun soluun PYÖRÄLLE valita viereisistä soluista, jotka on merkitty numerolla 1 pienempi kuin nykyisen solun numero mene valittuun soluun ja lisää se polkuun WHILE nykyinen solu ei ole aloitussolu RETURN polku löytyi ELSE RETURN polkua ei löydy| Kaavion hakualgoritmit | ||
|---|---|---|
| Tietämättömät menetelmät | ||
| Tietoon perustuvat menetelmät | ||
| Pikanäppäimet | ||
| Vähintään ulottuva puu | ||
| Muut | ||