Asdasd
Enviado por Programa Chuletas y clasificado en Lengua y literatura
Escrito el en 
español con un tamaño de 3,05 KB
Backtracking
¿Que se entiende por vuelta atrás?
Vuelta atrás (backtracking) es una tecnica de diseño de algoritmo que consiste en buscar todas las soluciones de un problema ,se asemeja a un recorrido en profundidaddentro de un árbol cuya existencia sólo es implícita, y que denominaremos árbol de expansión. Siempre puede encontrar todas las soluciones existentes (el problema es el tiempo en que toma hacerlo) construyendo soluciones parciales a medida que progresa el recorrido . .El recorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En caso de no tener una solucion se devuelve al principio (por eso el nombre “Vuelta Atras”) siguiendo otra rama de soluciones.
Posee dos tipos de restricciones. Implicitas(relacion entre las posibles soluciones) y Explicitas(reglas que restringen los valores)
Explique al menos dos casos en donde se aplica esta técnica y detalle cómo lo hace.
Las 8 reinas:
Se trata de un acertijo en el que se colocan ocho reinas sin que se amenacen.
Restricciones Explicitas:
En nuestro problema es el conjunto S = {1,2,3,4,5,6,7,8}..
Restricciones Implicitas:
En primer lugar sabemos que dos reinas no pueden situarse en la misma columna, ni en la misma fila, ni en diagonal , por lo tanto, no puede haber dos xi iguales en las posiciones nombradas anteriormente. Avanza contruyendo el arbol usando todas las columnas del tablero y ordeandolas de la mejor manera, construyendo las soluciones posibles.
A medida que encuentra una solucion para guarda , si no (llamado nodo fracaso) , la elimina y vuelve al principio llendose por otra rama hasta encontrar la solucion mas optima.
Caballo de Atila:
Se sabe que por donde pisa el caballo , el pasto no vuelve a crecer. Se analiza un problema en donde el caballo visita un jardin de nxn casillas.
Restricciones Implicitas:
El caballo no puede visitar su misma casilla dos veces,
No se puede mover en forma diagonal , solo vertical y horizontal.
El caballo empiesa su recorrido por el jardin por cierta ruta siendo estas rutas las posibles soluciones al problema. A medida de que avanza se encuentra con paredes o fin de caminos (nodos fracasos o no soluciones) , cuando sucede eso , vuelve al principio (vuelta atrás) para buscar una nueva ruta que sea la posible solucion al problema y asi encuentre la mejor solucion.
¿Que se entiende por vuelta atrás?
Vuelta atrás (backtracking) es una tecnica de diseño de algoritmo que consiste en buscar todas las soluciones de un problema ,se asemeja a un recorrido en profundidaddentro de un árbol cuya existencia sólo es implícita, y que denominaremos árbol de expansión. Siempre puede encontrar todas las soluciones existentes (el problema es el tiempo en que toma hacerlo) construyendo soluciones parciales a medida que progresa el recorrido . .El recorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En caso de no tener una solucion se devuelve al principio (por eso el nombre “Vuelta Atras”) siguiendo otra rama de soluciones.
Posee dos tipos de restricciones. Implicitas(relacion entre las posibles soluciones) y Explicitas(reglas que restringen los valores)
Explique al menos dos casos en donde se aplica esta técnica y detalle cómo lo hace.
Las 8 reinas:
Se trata de un acertijo en el que se colocan ocho reinas sin que se amenacen.
Restricciones Explicitas:
En nuestro problema es el conjunto S = {1,2,3,4,5,6,7,8}..
Restricciones Implicitas:
En primer lugar sabemos que dos reinas no pueden situarse en la misma columna, ni en la misma fila, ni en diagonal , por lo tanto, no puede haber dos xi iguales en las posiciones nombradas anteriormente. Avanza contruyendo el arbol usando todas las columnas del tablero y ordeandolas de la mejor manera, construyendo las soluciones posibles.
A medida que encuentra una solucion para guarda , si no (llamado nodo fracaso) , la elimina y vuelve al principio llendose por otra rama hasta encontrar la solucion mas optima.
Caballo de Atila:
Se sabe que por donde pisa el caballo , el pasto no vuelve a crecer. Se analiza un problema en donde el caballo visita un jardin de nxn casillas.
Restricciones Implicitas:
El caballo no puede visitar su misma casilla dos veces,
No se puede mover en forma diagonal , solo vertical y horizontal.
El caballo empiesa su recorrido por el jardin por cierta ruta siendo estas rutas las posibles soluciones al problema. A medida de que avanza se encuentra con paredes o fin de caminos (nodos fracasos o no soluciones) , cuando sucede eso , vuelve al principio (vuelta atrás) para buscar una nueva ruta que sea la posible solucion al problema y asi encuentre la mejor solucion.