Leejev algoritam objašnjen na primjerima

Lee algoritam jedno je od mogućih rješenja za probleme usmjeravanja labirinta. Uvijek daje optimalno rješenje ako postoji, ali je sporo i zahtijeva veliku memoriju za gusti raspored.

Razumijevanje kako to funkcionira

Algoritam je breadth-firstbazirani algoritam koji koristi queuesza pohranu koraka. Obično koristi sljedeće korake:

  1. Odaberite početnu točku i dodajte je u red čekanja.
  2. Dodajte važeće susjedne ćelije u red čekanja.
  3. Uklonite položaj na kojem se nalazite iz reda i nastavite do sljedećeg elementa.
  4. Ponavljajte korake 2 i 3 dok se red ne isprazni.

Jedan od ključnih pojmova koji treba razumjeti jest da breadth-firstpretrage idu široko, dok depth-firstpretraživanja idu duboko.

Na primjeru algoritma za rješavanje labirinta depth-firstpristup će isprobati svaki mogući put jedan po jedan sve dok ne dođe do slijepe ulice ili cilja i vrati rezultat. Međutim put koji vraća možda nije najučinkovitiji, već jednostavno prvi cjeloviti put do cilja koji je algoritam uspio pronaći.

breadth-firstTraži umjesto toga ići na svakom otvorenom prostoru u susjedstvu na početnu točku, a zatim tražiti druge moguće otvorenim prostorima. Nastavit će to raditi, izlazeći sloj po sloj i iskušavajući svaki mogući put u tandemu, sve dok ne pronađe završnu točku. Budući da istodobno isprobavate svaki put, možete biti sigurni da je prvi cjeloviti put od početka do kraja ujedno i najkraći.

Provedba

C ++ ima red već implementiran u knjižnicu, ali ako koristite nešto drugo, dobrodošli ste da implementirate svoju verziju reda.

C ++ kôd:

int dl[] = {-1, 0, 1, 0}; // these arrays will help you travel in the 4 directions more easily int dc[] = {0, 1, 0, -1}; queue X, Y; // the queues used to get the positions in the matrix X.push(start_x); //initialize the queues with the start position Y.push(start_y); void lee() { int x, y, xx, yy; while(!X.empty()) // while there are still positions in the queue { x = X.front(); // set the current position y = Y.front(); for(int i = 0; i < 4; i++) { xx = x + dl[i]; // travel in an adiacent cell from the current position yy = y + dc[i]; if('position is valid') //here you should insert whatever conditions should apply for your position (xx, yy) { X.push(xx); // add the position to the queue Y.push(yy); mat[xx][yy] = -1; // you usually mark that you have been to this position in the matrix } } X.pop(); // eliminate the first position, as you have no more use for it Y.pop(); } }