Diseño de Algoritmos
COMENTARIOS |
ESTADÍSTICAS |
RÉCORDS
|
Título del Test: Diseño de Algoritmos Descripción: BackTracking |
Nuevo Comentario| Comentarios |
|---|
NO HAY REGISTROS |
|
Los algoritmos de vuelta atrás siempre son exponenciales. V. F. En la técnica de la Vuelta Atrás cuando se encuentra un elemento no factible, se eliminan todas las combinaciones que lo contengan. V. F. En el problema de las Permutaciones, a diferencia de lo que ocurre en el problema de las 8 reinas, al terminar el despliegue de los nodos hijos no hay que restablecer el valor anterior de la casilla considerada. V. F. En el problema del Laberinto, si al terminar la ejecución una casilla tiene valor 0 eso quiere decir que dicha casilla nunca se han visitado. V. F. ¿Cuál de los siguientes es un problema que presenta la técnica de Vuelta Atrás?. No realiza una búsqueda exhaustiva del espacio de soluciones. Examina un número excesivo de nodos. La función de factibilidad suele ser ineficiente. En el problema del Sudoku, por cada casilla del tablero siempre se generan los 9 hijos. V. F. En el problema del Laberinto, el siguiente cambio en la codificación del significado de las casillas puede mejorar sensiblemente el algoritmo: [0, 1, 2, 3, 4] => [-1, 1, -2, 3, 0]. V. F. El número total de nodos del árbol explícito en un problema de Vuelta Atrás será el cardinal del conjunto de todos los que satisfacen la función de factibilidad. V. F. La Vuelta Atrás examina un número excesivo de nodos. V. F. En el problema del Laberinto, el siguiente cambio en la codificación del significado de las casillas puede mejorar sensiblemente el algoritmo: [0, 1, 2, 3,4] => [1, -1, -2, -3, 0]. V. F. En el problema de las 8 reinas, dos reinas se amenazan si r1.x == r2.x || r1.y == r2.y || r2.x-r1.x = r2.y-r1. V. F. La función que determina si una solución parcial no puede generar ninguna solución completa se llama función de factibilidad. V. F. En el problema del Sudoku el árbol implícito más alto tendrá m+1 niveles, siendo m el número de casillas libres. V. F. En la técnica de vuelta atrás el recorrido del árbol implícito se hace usando una pila. V. F. En la técnica de la Vuelta Atrás, el número de nodos del árbol implícito que están desplegados en un momento determinado de la ejecución está en O(log(n)). V. F. |