Lee algoritmusa példákkal magyarázva

A Lee algoritmus az egyik lehetséges megoldás a labirintus útválasztási problémáira. Mindig optimális megoldást ad, ha van ilyen, de lassú és nagy memóriát igényel a sűrű elrendezéshez.

A működésének megértése

Az algoritmus egy breadth-firstalapú algoritmus, amely queuesa lépések tárolására szolgál. Általában a következő lépéseket hajtja végre:

  1. Válasszon kiindulási pontot, és vegye fel a sorba.
  2. Adja hozzá az érvényes szomszédos cellákat a sorba.
  3. Távolítsa el azt a pozíciót, amelyen tartózkodik, és lépjen a következő elemre.
  4. Ismételje meg a 2. és 3. lépést, amíg a sor üres nem lesz.

Az egyik kulcsfontosságú megértés az, hogy a breadth-firstkeresések széles körűek, míg a depth-firstkeresések mélyek.

A labirintusmegoldó algoritmus példáján keresztül egy depth-firstmegközelítés minden lehetséges utat egyenként kipróbálja, amíg vagy zsákutcába vagy célba nem ér, és visszaadja az eredményt. A visszatérő út azonban nem biztos, hogy a leghatékonyabb, hanem egyszerűen az első teljes út a célig, amelyet az algoritmus megtalált.

A breadth-firstkeresés ehelyett a kiindulási ponttal szomszédos minden szabad helyre kerül, majd más lehetséges szabad helyeket keres. Folyamatosan fogja ezt csinálni, rétegenként haladva kipróbálja az összes lehetséges utat tandemben, amíg meg nem találja a célpontot. Mivel mindegyik utat egyszerre próbálja meg, biztos lehet benne, hogy az első teljes út az elejétől a végéig szintén a legrövidebb.

Végrehajtás

A C ++ már be van építve a várólistába a könyvtárban, de ha mást használ, akkor szívesen megvalósítja a sor saját verzióját.

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