Búsqueda exhaustiva

¿Cuál de los siguientes NO corresponde a una metodología de resolución por búsqueda exhaustiva?

• Generar y probar

• Algoritmo Naive

• Backtracking

• Branch and Bound

• Ninguna de ellas

¿Cuál de las siguientes expresa mejor el concepto de "restricciones explícitas"?

• Espacio de soluciones definido por la naturaleza del problema

• Subconjunto de soluciones que cumplen con el criterio de factibilidad

• Espacio de soluciones que superan la función de prueba del problema

• Conjunto de reglas lógicas que permiten establecer los criterios de maximización del resultado

¿Cuál de las siguiente corresponde a la mejor definición de restricción implícita

• Una restricción que determina si una solución cumple con las condiciones para ser solución factible

• Una restricción que determina si una solución corresponde a una solución óptima del problema

• Una restricción que se puede ignorar en la solución del problema

• Una restricción que se aplica solo a una variable de decisión

¿Cuál de los siguientes conceptos NO están relacionados con la metodología de generar y probar?

• Función generativa

• Función de prueba

• Función límite

• explosión combinatoria

Seleccione lo que NO corresponde: " El espacio de estados de un problema corresponde a un grafo en el qué ...

• cada nodo corresponde a un estado del problema "

• cada eje corresponde a una acción que modifica el estado del problema "

• los nodos puede corresponder a soluciones totales o parciales del problema "

• su exploración exhaustiva nos asegura encontrar la solución al problema

• existen nodos llamados estados 'solución' y 'respuesta' "

Marca lo que NO corresponde: El algoritmo de Backtracking ...

• propone recorrer el estado de soluciones como un árbol

• permite podar ramas utilizando la propiedad de corte

• el árbol de estados establece una jerarquía de estados del problema

• utilizar como forma de recorrer el árbol la estrategia de recorrido por anchura

La función costo en Branch and Bound

• Es la suma de los costos de las decisiones tomadas hasta el momento
• permite calcular el costo de la solución óptima

• brinda un valor estimado que permite acotar la mejor solución descendiente de una rama del árbol de estados

• Nos permite calcular la complejidad temporal de realizar la exploración completa del arbol de estados en el peor de los casos.

Best First comparado con depth-first branch-and-bound requiere mayor complejidad espacial para su implementación

• Verdadero

• Falso

Depth-first branch-and-bound y Best First se deben implementar de forma recursiva

• Verdadero

• Falso

Al realizar una comparación entre "Branch & Bound" y "generar y probar" podemos afirmar que la complejidad temporal del primero resultará menor siempre que en el segundo

• Verdadero

• Falso