El algoritmo de profundidad primero resuelve el problema de los ocho dígitos

En primer lugar, imaginemos un ratón en un laberinto que nunca ve la luz. El ratón entra por la entrada y quiere salir por la salida. ¿Cómo se moverá el ratón? Por supuesto que es así: si el ratón encuentra un camino recto, seguirá adelante; si encuentra una bifurcación en el camino, elegirá una de ellas y continuará caminando hacia abajo; si encuentra un callejón sin salida, lo hará; retírese a la bifurcación más cercana. Elija otro camino y continúe. Si encuentra la salida, el viaje del mouse habrá terminado. El principio básico del método de búsqueda en profundidad es el siguiente: busque tentativamente hacia adelante de acuerdo con ciertas condiciones, y si encuentra fallas mientras avanza (como un mouse que encuentra un callejón sin salida), retroceda y elija otro camino para continuar buscando hasta encuentras el objetivo de las condiciones.

Para implementar este algoritmo, necesitamos utilizar otra poderosa herramienta en programación recursiva. La recursividad es un concepto muy abstracto, pero aún podemos verlo en la vida diaria. Toma dos espejos y ponlos frente a frente ¿Qué verás? ¿Verás innumerables espejos en el espejo? ¿Qué está sucediendo? Hay una imagen del espejo B en el espejo A y hay una imagen del espejo A en el espejo B. La imagen del espejo A es un reflejo verdadero del espejo A mismo. Es decir, la imagen del espejo A incluye al espejo A. , y el espejo B está en el espejo A. La imagen... es tan agotadora, molesta y complicada, y difícil de entender. En lenguaje informático, A llama a B y B llama a A. De esta manera, A llama a sí mismo indirectamente, lo que logra una función repetida. Para dar otro ejemplo: Había una vez una montaña y había un templo en la montaña. Había un viejo monje en el templo. El viejo monje estaba contando historias. Diga: Había una vez una montaña y había un templo en la montaña. Había un viejo monje en el templo. El viejo monje estaba contando historias. Diga: Había una vez una montaña y había un templo en la montaña. Había un viejo monje en el templo. El viejo monje estaba contando una historia. hablar:…………. Buen chico, no es divertido hablar así del fin del mundo. La historia contada por el viejo monje es en realidad la historia anterior. Esas llamadas continuas al programa en sí forman recursividad. Si a un viejo monje de esta historia no le gusta la historia, cambie la historia que quiere contar por: "¿Ya terminaste?" De esta manera, toda la historia llegará a un final abrupto. Debemos prestar atención a esto al programar. En el momento apropiado, debe haber un monje que se acerque y detenga toda la historia, o le impida buscar más profundamente. De lo contrario, nuestra recursividad se verá obligada a desbordarse. Limitación de la capacidad de almacenamiento del ordenador. Recuerda, recuerda.

Aplicamos el pensamiento recursivo al laberinto anterior. Recuerde que la posición actual del mouse es (x, y). Entonces ahora tiene 4 direcciones para entrar, a saber (x 1, y). x-1, y), (x, y 1), (x, y-1), una de las direcciones es la forma de donde vino, no la consideremos primero, probaremos las otras tres direcciones respectivamente, si Si una determinada dirección es un camino en lugar de una pared, el ratón dará un paso en esa dirección. En la nueva posición podemos repetir los pasos anteriores. ¿Qué pasa si el ratón llega a un callejón sin salida? Es decir, a excepción del camino por el que vinimos, hay muros en las otras tres direcciones. En este momento, este camino ha llegado a su fin y no podemos seguir avanzando. Debemos regresar por el camino por el que vinimos e intentar otra dirección.

Ejemplo: Ocho Reinas Problema: Se deben colocar 8 reinas en el tablero de ajedrez estándar (cuadrículas de 8*8). Sabemos que la reina es la más poderosa en el ajedrez. Puede moverse hacia los lados. camina vertical o diagonalmente, y cuando encuentra enemigos que bloquean su camino, puede comérselo. Se requiere colocar 8 reinas en el tablero de ajedrez para que no puedan capturarse entre sí. Encuentra la manera de colocar las reinas.

Esta es una pregunta muy clásica. Primero debemos aclarar nuestras ideas y cómo utilizar el método de búsqueda en profundidad para completar esta pregunta. Primero construimos un tablero de ajedrez con una cuadrícula de 8*8 y colocamos una reina en cualquier lugar de la primera fila del tablero.

A continuación, colocaremos la segunda fila. Hay algunas restricciones en la ubicación de la segunda fila, porque la reina no se puede colocar en la misma fila vertical o en la misma posición diagonal que la reina en la primera fila. Siguiente Es la tercera fila. ,... tal vez nos encontremos con esta situación. Cuando la coloquemos en una fila determinada, no importa dónde esté la reina, las reinas de otras filas se la comerán. Esto muestra que nuestra colocación anterior falló, es decir, según el método de colocación anterior de la reina, no podemos obtener la solución correcta. ¿Qué debemos hacer ahora? Cambiémoslo. Volvamos a la fila anterior, cambiemos la reina que colocamos originalmente a otra posición y luego regresemos y coloquemos esta fila si esto no funciona o solo hay una posición para la reina en la fila anterior. , ¿qué debemos hacer? Volvemos a la línea anterior de la línea anterior, que tiene el mismo significado que el ratón que gira hacia atrás cuando choca contra una pared. Sólo sigue intentándolo