IIC2133
Duda backtracking #168
-
|
Hola, estudiando la materia de backtracking me surgió una udda con respecto al conjunto de variables que se utilizan en el ejemplo del laberinto.
|
Beta Was this translation helpful? Give feedback.
Replies: 1 comment 1 reply
-
|
El conjunto de variables X lo puedes interpretar como el conjunto de todas las posiciones con su respectiva etiqueta nonvisited, visited o exit (puedes pensarlo como una matriz donde en cada X[i][j] tienes la etiqueta de la posición i,j). El pseudocódigo conserva en X todo el estado del laberinto producto de las asignaciones anteriores, es decir, sabes las variables que has visitado o no. En cada llamado recursivo, isSolvable recibe como argumento X y la nueva variable x a revisar, y utiliza X para verificar si la variable x recibida fue visitada o no, para no revisarla de nuevo. Solo retornara true cuando haya encontrado la variable etiquetada como exit, y esto ocurre solo cuando pasas por posiciones nonvisited hasta llegar a exit. Cuando llegas a una posición visited, te devuelves para seguir el camino por una posición nonvisited, lo que significa volver a etiquetarla como nonvisited, es decir, reviertes la asignación anterior (Linea 9). Entonces no necesitas saber el largo del camino que conduce a la salida porque no influye en la búsqueda y tampoco necesitas explícitamente un conjunto de variables sin asignar porque necesitas saber las variables que asignaste antes y en caso de equivocarte, reviertes las asignaciones, y buscas por otro lado. Espero que haya quedado mas claro y cualquier cosa pregunta nomas! |
Beta Was this translation helpful? Give feedback.
-
|
Perfecto me quedó más claro ahora, muchas gracias! |
Beta Was this translation helpful? Give feedback.
El conjunto de variables X lo puedes interpretar como el conjunto de todas las posiciones con su respectiva etiqueta nonvisited, visited o exit (puedes pensarlo como una matriz donde en cada X[i][j] tienes la etiqueta de la posición i,j).
El pseudocódigo conserva en X todo el estado del laberinto producto de las asignaciones anteriores, es decir, sabes las variables que has visitado o no.
En cada llamado recursivo, isSolvable recibe como argumento X y la nueva variable x a revisar, y utiliza X para verificar si la variable x recibida fue visitada o no, para no revisarla de nuevo. Solo retornara true cuando haya encontrado la variable etiquetada como exit, y esto ocurre solo cuando pasas p…