Algoritmo de Lee explicado con ejemplos

El algoritmo de Lee es una posible solución para los problemas de enrutamiento de laberintos. Siempre ofrece una solución óptima, si existe, pero es lenta y requiere mucha memoria para un diseño denso.

Entendiendo como funciona

El algoritmo es un breadth-firstalgoritmo basado que se utiliza queuespara almacenar los pasos. Suele seguir los siguientes pasos:

  1. Elija un punto de partida y agréguelo a la cola.
  2. Agregue las celdas vecinas válidas a la cola.
  3. Elimine la posición en la que se encuentra de la cola y continúe con el siguiente elemento.
  4. Repita los pasos 2 y 3 hasta que la cola esté vacía.

Un concepto clave a entender es que las breadth-firstbúsquedas son amplias, mientras que las depth-firstbúsquedas son profundas.

Usando el ejemplo de un algoritmo de resolución de laberintos, un depth-firstenfoque probará todos los caminos posibles uno por uno hasta que llegue a un callejón sin salida o al final y devuelva el resultado. Sin embargo, la ruta que devuelve puede no ser la más eficiente, sino simplemente la primera ruta completa hasta el final que el algoritmo pudo encontrar.

En breadth-firstsu lugar, se realizará una búsqueda en cada espacio abierto adyacente al punto de partida, luego buscará otros posibles espacios abiertos. Seguirá haciendo esto, saliendo capa por capa y probando cada posible camino en tándem, hasta que encuentre el punto final. Dado que está probando cada ruta al mismo tiempo, puede estar seguro de que la primera ruta completa de principio a fin también es la más corta.

Implementación

C ++ ya tiene la cola implementada en la biblioteca, pero si está usando algo más, puede implementar su propia versión de la cola.

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