Algorithm of wave tracing ( bølgealgoritme , Lees algoritme ) er en stifindende algoritme, en algoritme til at finde den korteste vej på en plan graf . Tilhører algoritmer baseret på bredde-først søgemetoder .
Det bruges hovedsageligt til computersporing ( ledningsføring) af trykte kredsløbskort , der forbinder ledere på overfladen af mikrokredsløb. En anden anvendelse af bølgealgoritmen er at finde den korteste afstand på et kort i computerstrategispil.
Bølgealgoritmen i forbindelse med at finde en sti i en labyrint blev foreslået af E. F. Moore [2] . Lee opdagede uafhængigt den samme algoritme, mens han formaliserede routingalgoritmer for printkort i 1961 [3] [4] [5] .
Algoritmen fungerer på et diskret arbejdsfelt (DWP), som er en figur afgrænset af en lukket linje, ikke nødvendigvis rektangulær, opdelt i rektangulære celler, i et bestemt tilfælde firkantede. Sættet af alle DRP-celler er opdelt i undergrupper: "passable" (gratis), dvs. når man søger efter en sti, kan de passeres, "ufremkommelige" (hindringer), stien gennem denne celle er forbudt, startcelle (kilde ) og efterbehandling (modtager). Tildelingen af start- og slutcellerne er betinget, det er nok at angive et par celler, mellem hvilke du skal finde den korteste vej.
Algoritmen er designet til at finde den korteste vej fra startcellen til den endelige celle, hvis det er muligt, eller, i mangel af en vej, udsende en besked om obstruktion [6] .
Driften af algoritmen omfatter tre trin: initialisering , bølgeudbredelse og vejgendannelse .
Under initialiseringen bygges et billede af et sæt celler i det behandlede felt, attributter for fremkommelighed / obstruktion tildeles hver celle, start- og slutceller huskes.
Fra startcellen genereres der yderligere et trin ind i nabocellen, mens det kontrolleres, om det er acceptabelt, og om det hører til den celle, der tidligere er markeret i stien.
Naboceller klassificeres normalt på to måder: i betydningen Moore- kvarteret og von Neumann-kvarteret , som adskiller sig ved, at i von Neumann-kvarteret, kun 4 celler lodret og vandret betragtes som naboceller, i Moore-kvarteret, alle 8 celler, herunder diagonale.
Hvis fremkommelighedsbetingelserne er opfyldt, og det ikke tilhører de celler, der tidligere er markeret på vejen, skrives et tal svarende til antallet af trin fra startcellen til celleattributten, fra startcellen ved første trin vil det blive 1. Hver celle markeret med antallet af trin fra startcellen bliver startcellen, og fra den genereres næste trin i naboceller. Det er klart, at med en sådan søgning vil en sti fra den indledende celle til den sidste blive fundet, eller det næste trin fra en hvilken som helst celle genereret i stien vil være umuligt.
Gendannelse af den korteste vej sker i den modsatte retning: Når du vælger en celle fra slutcellen til startcellen, vælges ved hvert trin en celle, der har en egenskab for afstand fra starten, der er mindre end den aktuelle celle. Det er klart, på denne måde findes den korteste vej mellem et par givne celler [6] . Der kan være flere spor med en minimum numerisk sti-længde, både når man søger efter en sti i nærheden af Moore og von Neumann. Valget af den endelige vej i applikationer er dikteret af andre overvejelser uden for denne algoritme. For eksempel ved sporing af printkort - den mindste lineære længde af den lagte leder.
Initialisering
Marker startcelle d := 0Bølgeudbredelse
LOOP FOR hver celle lokation markeret med nummer d marker alle tilstødende frie umarkerede celler med nummer d + 1 KC d := d + 1 YET (afsluttende celle er ikke markeret) OG (der er mulighed for bølgeudbredelse)Stigendannelse
IF finish celle mærket THEN gå til færdig celle CYKLUS vælg blandt naboceller markeret med et nummer 1 mindre end tallet i den aktuelle celle gå til den valgte celle og føj den til stien MENS den aktuelle celle ikke er startcellen RETURN - sti fundet ANDERS RETURN - sti ikke fundet| Algoritmer til grafsøgning | ||
|---|---|---|
| Uoplyste metoder | ||
| Informerede metoder | ||
| Genveje | ||
| Minimumspændende træ | ||
| Andet | ||