¿Cual de los siguientes es un problema que representa la técnica de vuelta atras? 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.
Para la técnica de la ramificación y poda Se realiza un recorrido en profundidad hasta que encuentre una solución. El valor de esta nos servirá para podar ciertas ramas del árbol El cálculo de la función cota sólo nos sirve para seleccionar, de entre los abiertos, el nodo más prometedor Para cada nodo seleccionado, siempre se generan todos sus hijos.
En ramificación y poda, un nodo que no es factible es declarado nodo muerto V F.
Backtracking inspecciona todo el árbol implicito, mientras que ramificación y poda solo explora parte V F.
Los algoritmos de vuelta atras siempre son exponenciales V F.
El número de nodos vivos en la técnica de la vuelta atras está en O(log(n)) V F.
En la tecnica de vuelta atras el recorrido del arbol implicito se hace usando Una pila Una cola Un heap Ninguna de las anteriores.
Si usamos ramificacion y poda Es necesario encontrar un valor real para poder empezar a podar Las cotas son orientativas, nunca fuerzan una poda Cuando el objetivo es minimizar, si la cota de un nodo es mayor que el mínimo valor real encontrado, se poda la rama Todas son ciertas.
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 8 reinas, dos reinas se amenazan si: están en la misma fila, columna o diagonal V F.
Cuando se resuelve el problema del viajante de comercio utilizando ramificación y poda, para el cálculo de la función cota la mitad de la distancia entre dos nodos (i,j) es debida al nodo i y la otra mitad al nodo j V F.
Las técnicas de vuelta atras y de ramificación y poda se resuelven de manera sencilla y elegante utilizando algoritmos recursivos V F.
En la técnica de la ramificacion y poda el cálculo de la función cota solo nos sirve para seleccionar, de entre los abiertos, el nodo más prometedor V F.
En la técnica de la vuelta atrás cuando se encuentra un caso no factible, se eliminan todas las combinaciones que lo contengan. V F.
En el problema de las permutaciones, al igual que en el problema de las 8 reinas, al terminar el despliegue de los nodos hijos hay que restablecer el valor anterior de la casilla considerada V F.
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 funcion de factibilidad V F.
La vuelta atras 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 implicito mas alto tendra m+1 niveles, siendo m el número de casillas libres V F.
En la técnica de la vuelta atras el recorrido del arbol se hace usando una pila V F.
En la técnica de la vuelta atras, el número de nodos del arbol implicito que están desplegados en un momento determinado de la ejecucion está en O(log(n)) V F.
|
