Algoritmul Lee este o soluție posibilă pentru problemele de rutare a labirintului. Oferă întotdeauna o soluție optimă, dacă există, dar este lentă și necesită memorie mare pentru un aspect dens.

Înțelegerea modului în care funcționează

Algoritmul este un breadth-first algoritm bazat pe care folosește queues pentru a stoca treptele. De obicei, folosește următorii pași:

  1. Alegeți un punct de plecare și adăugați-l la coadă.
  2. Adăugați celulele vecine valide la coadă.
  3. Eliminați poziția pe care vă aflați din coadă și continuați cu elementul următor.
  4. Repetați pașii 2 și 3 până când coada este goală.

Un concept cheie de înțeles este că breadth-first căutările merg larg, în timp ce depth-first căutările se adâncesc.

Folosind exemplul unui algoritm de rezolvare a labirintului, a depth-first abordarea va încerca fiecare cale posibilă una câte una până când va ajunge fie la un punct mort sau la final și va întoarce rezultatul. Cu toate acestea calea pe care o returnează s-ar putea să nu fie cea mai eficientă, ci pur și simplu prima cale completă până la finalizare pe care algoritmul a reușit să o găsească.

Citește mai multCum se face o promisiune dintr-o funcție de apel invers în JavaScript

A breadth-first în schimb, căutarea va ieși în fiecare spațiu deschis adiacent punctului de plecare, apoi va căuta alte posibile spații deschise. Acesta va continua să facă acest lucru, ieșind strat cu strat și încercând fiecare cale posibilă în tandem, până când va găsi punctul de sosire. Deoarece încercați fiecare cale în același timp, puteți fi sigur că prima cale completă de la început până la sfârșit este, de asemenea, cea mai scurtă.

Implementare

C ++ are coada deja implementată în <queue> bibliotecă, dar dacă utilizați altceva, sunteți binevenit să implementați propria dvs. versiune de coadă.

Cod C ++:

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<int> 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();
    
  }


}