Li algoritam (engl. Lee algorithm) je algoritam za pronalaženje puta u grafu, koji se zasniva na pretrazi po širini (BFS). Koristi se za rešavanje problema rutiranja u lavirintima, a posebno za automatsko projektovanje štampanih ploča. Algoritam je razvio C. Y. Li (C. Y. Lee) i objavio ga 1961. godine u časopisu IRE Transactions on Electronic Computers.
Istorijat
Algoritam je prvobitno osmišljen za primenu u automatizovanom projektovanju štampanih ploča (PCB - engl. printed circuit board), gde je bilo potrebno pronaći puteve između tačaka na ploči uz izbegavanje prepreka. Ova vrsta problema poznata je pod nazivom problem rutiranja u lavirintu (engl. maze routing problem). Pored primene u elektronici, algoritam se danas široko koristi u računarskim igrama za pronalaženje putanje likova kroz mrežasti prostor.
Opis algoritma
Li algoritam radi na pravougaonoj mreži ćelija (matrici), pri čemu su neke ćelije slobodne, a neke zauzete (prepreke). Cilj je pronaći najkraći put od početne ćelije do ciljne ćelije.
Algoritam se izvodi u četiri faze:
1. Inicijalizacija
Početnoj ćeliji dodeljuje se oznaka 0. Sve slobodne ćelije su inicijalno neoznačene, a prepreke su trajno nedostupne.
2. Širenje talasa
Od početne ćelije, algoritam iterativno označava sve slobodne, neoznačene susedne ćelije (gore, dole, levo, desno) vrednostima koje se povećavaju za 1 u svakom koraku. Ovaj proces se nastavlja sve dok:
se ne dostigne ciljna ćelija — u tom slučaju put postoji, ili ne ostane više ćelija za označavanje — u tom slučaju put ne postoji.
Ovaj korak odgovara standardnoj pretrazi po širini i garantuje da je pronađeni put najkraći mogući.
3. Povratno praćenje
Počevši od ciljne ćelije, algoritam prati put unazad ka početnoj ćeliji, birajući u svakom koraku susednu ćeliju čija je oznaka za jedan manja od trenutne. Na ovaj način se rekonstruiše najkraći put.
4. Čišćenje
U primeni na štampane ploče, pronađeni put se blokira (označava kao zauzet), a sve ostale oznake se brišu kako bi algoritam mogao da pronađe sledeći put. U primeni u računarskim igrama, ovaj korak obično nije potreban.
Pseudokod
funkcija LiAlgoritam(mreža, početak, cilj): red ← prazan red dodaj početak u red označi početak sa 0
dok red nije prazan: trenutna ← uzmi iz reda za svaku susednu ćeliju od trenutna: ako je slobodna i neoznačena: označi je sa oznaka(trenutna) + 1 dodaj je u red ako je jednaka cilju: izlaz iz petlje
ako cilj nije označen: vrati "put ne postoji"
// Povratno praćenje put ← [] trenutna ← cilj dok trenutna ≠ početak: dodaj trenutna u put trenutna ← sused sa oznakom(trenutna) − 1 dodaj početak u put vrati obrnuti put
Složenost
Li algoritam ima vremensku i memorijsku složenost O(m × n), gde su m i n dimenzije mreže. Algoritam uvek pronalazi najkraći put ako on postoji, ali zbog velikih memorijskih zahteva na velikim mrežama, često se koriste efikasnije heuristike poput A* algoritma.
Primene
Projektovanje štampanih ploča — automatsko rutiranje provodnika između komponenti Računarske igre — pronalaženje putanje likova i NPC-ova Robotika — planiranje kretanja u mrežastim okruženjima Umrežavanje — rutiranje podataka u mrežama
Nedostaci
Glavni nedostatak Li algoritma je visoka potrošnja memorije, jer algoritam mora da čuva oznake za sve ćelije mreže. Na velikim mrežama s retkim preprekama ovo može biti neprihvatljivo. Zbog toga su razvijene varijante i alternativni algoritmi koji smanjuju memorijsku potrošnju, kao što je Rubinov algoritam iz 1974. godine.
Vidi još
Pretraga po širini A* algoritam Dijkstrin algoritam Problem pronalaženja puta Štampana ploča
Reference
Literatura
Wolf, Wayne (2002). Modern VLSI Design: System-on-Chip Design. Prentice Hall.
Kategorija:Algoritmi za pretragu grafova Kategorija:Algoritmi za pronalaženje puta Kategorija:Projektovanje štampanih ploča