A hullámkövetési algoritmus ( hullám-algoritmus , Lee algoritmusa ) egy útkereső algoritmus, egy algoritmus a legrövidebb út megtalálására egy síkgráfon . A szélesség-első keresési módszereken alapuló algoritmusokhoz tartozik .
Főleg nyomtatott áramköri kártyák számítógépes nyomon követésére (huzalozására) használják, vezetékeket összekötve a mikroáramkörök felületén. A hullámalgoritmus másik alkalmazása a legrövidebb távolság megtalálása a térképen számítógépes stratégiai játékokban.
A labirintusban való útkeresés összefüggésében a hullámalgoritmust E. F. Moore javasolta [2] . Lee önállóan fedezte fel ugyanezt az algoritmust, miközben 1961-ben formalizálta az áramköri lapok útválasztási algoritmusait [3] [4] [5] .
Az algoritmus egy diszkrét munkamezőn (DWP) dolgozik, amely egy zárt vonallal határolt, nem feltétlenül téglalap alakú, téglalap alakú cellákra, adott esetben négyzet alakú cellákra osztott ábra. Az összes DRP cella halmaza részhalmazokra van felosztva: „átjárható” (ingyenes), azaz útkereséskor át lehet adni, „átjárhatatlan” (akadályok), ezen a cellán keresztüli út tiltott, kezdő cella (forrás ) és befejező (vevő). A start és cél cellák hozzárendelése feltételes, elegendő egy olyan cellapárt megadni, amelyek között meg kell találni a legrövidebb utat.
Az algoritmus úgy van kialakítva, hogy lehetőség szerint megtalálja a legrövidebb utat a kezdő cellától a végső celláig, vagy út hiányában üzenetet ad ki az akadályról [6] .
Az algoritmus működése három szakaszból áll: inicializálás , hullámterjedés és út helyreállítása .
Az inicializálás során a feldolgozott mező celláinak készletének képe készül, minden cellához hozzárendelődik az átjárhatóság / akadályozás attribútuma, a kezdő és befejező cellák emlékeznek.
Továbbá a kiinduló cellából egy lépés generálódik a szomszédos cellába, miközben ellenőrzi, hogy az átjárható-e, és az útvonalon korábban megjelölt cellához tartozik-e.
A szomszédos cellákat általában kétféleképpen osztályozzák: a Moore szomszédság és a von Neumann szomszédság értelmében, ami abban különbözik, hogy a Neumann negyedben függőlegesen és vízszintesen csak 4 cellát tekintenek szomszédos cellának, a Moore szomszédságban mind a 8 cellát. cellák, beleértve az átlósakat is.
Ha az átjárhatósági feltételek teljesülnek, és nem tartozik az úton korábban megjelölt cellák közé, akkor a cella attribútumába a kezdőcellától a lépések számával megegyező szám íródik, az első lépésben lévő kezdő cellából 1. A kezdő cellától számítva minden lépésszámmal jelölt cella kezdő cellává válik, és ebből a következő lépések generálódnak a szomszédos cellákban. Nyilvánvaló, hogy egy ilyen kereséssel a kezdeti cellától a végső celláig elérési út található, vagy az útvonalban generált bármely cellából lehetetlen lesz a következő lépés.
A legrövidebb út visszaállítása az ellenkező irányban történik: a célcellától a kezdőcelláig tartó cella kiválasztásakor minden lépésben kiválasztásra kerül egy olyan cella, amelynek a kezdettől való távolság attribútuma eggyel kisebb, mint az aktuális cella. Nyilvánvalóan így találjuk meg a legrövidebb utat egy adott cellapár között [6] . Több nyom is lehet minimális numerikus úthosszal, mind Moore, mind von Neumann környékén keresve. Az alkalmazásokban a végső útvonal kiválasztását ezen az algoritmuson kívüli egyéb megfontolások határozzák meg. Például nyomtatott áramköri lapok nyomon követésekor - a lefektetett vezető minimális lineáris hossza.
Inicializálás
Jelölje ki a d kezdőcellát := 0Hullámterjedés
LOOP FOR minden d számmal jelölt cellahelyet jelöljön meg minden szomszédos szabad jelöletlen cellát d számmal + 1 KC d := d + 1 MÉG (a befejező cella nincs megjelölve) ÉS (lehetőség van hullámterjedésre)Út helyreállítása
HA befejezi a THEN feliratú cellát menj a cella befejezéséhez CIKLUS válasszon az aktuális cellában lévő számnál 1-gyel kisebb számmal jelölt szomszédos cellák közül lépjen a kiválasztott cellára, és adja hozzá az elérési úthoz Míg az aktuális cella nem a kezdő cella. RETURN útvonal található ELSE RETURN útvonal nem található| Grafikon keresési algoritmusok | ||
|---|---|---|
| Tájékozatlan módszerek | ||
| Tájékozott módszerek | ||
| Parancsikonok | ||
| Minimálisan átívelő fa | ||
| Egyéb | ||