L'algorithme de Lee expliqué: l'exécution du labyrinthe et la recherche du chemin le plus court

Qu'est-ce que l'algorithme de Lee?

L'algorithme de Lee est une solution possible aux problèmes de routage de labyrinthe. Il donne toujours une solution optimale, s'il en existe une, mais est lent et nécessite une grande mémoire pour une mise en page dense.

Comprendre comment ça marche

L'algorithme est un   breadth-first  algorithme basé   queues  sur le stockage des étapes. Il utilise généralement les étapes suivantes:

  1. Choisissez un point de départ et ajoutez-le à la file d'attente.
  2. Ajoutez les cellules voisines valides à la file d'attente.
  3. Supprimez la position sur laquelle vous vous trouvez de la file d'attente et passez à l'élément suivant.
  4. Répétez les étapes 2 et 3 jusqu'à ce que la file d'attente soit vide.

la mise en oeuvre

C ++ a déjà implémenté la file d'attente dans la    bibliothèque, mais si vous utilisez autre chose, vous êtes invités à implémenter votre propre version de file d'attente.

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