Lees algoritme forklaret med eksempler

Lee-algoritmen er en mulig løsning til problemer med routing af labyrinter. Det giver altid en optimal løsning, hvis en findes, men er langsom og kræver stor hukommelse til tæt layout.

Forstå hvordan det fungerer

Algoritmen er en breadth-firstbaseret algoritme, der bruger queuestil at gemme trinnene. Det bruger normalt følgende trin:

  1. Vælg et startpunkt, og tilføj det til køen.
  2. Føj de gyldige naboceller til køen.
  3. Fjern den position, du befinder dig fra køen, og fortsæt til det næste element.
  4. Gentag trin 2 og 3, indtil køen er tom.

Et nøglebegreb at forstå er, at breadth-firstsøgninger går bredt, mens depth-firstsøgninger går dybt.

Ved hjælp af eksemplet med en labyrintløsningsalgoritme vil en depth-firsttilgang prøve alle mulige stier en efter en, indtil den enten når en blindgyde eller slutningen og returnerer resultatet. Den sti, den returnerer, er måske ikke den mest effektive, men simpelthen den første komplette vej til den finish, som algoritmen var i stand til at finde.

En breadth-firstsøgning vil i stedet gå ud til hvert åbent rum ved siden af ​​startpunktet og derefter se efter andre mulige åbne rum. Det vil fortsætte med at gøre dette, gå ud lag for lag og prøve hver mulig sti i tandem, indtil det finder slutpunktet. Da du prøver hver sti på samme tid, kan du være sikker på, at den første komplette sti fra start til slut også er den korteste.

Implementering

C ++ har køen allerede implementeret i biblioteket, men hvis du bruger noget andet, er du velkommen til at implementere din egen version af køen.

C ++ kode:

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