Repaso T1 Mth3

Una heurística es un algoritmo aproximado general aplicable a una gran variedad de problemas, que utiliza estrategias robustas para resolver problemas complejos. V. F.

Las metaheurísticas son estrategias de alto nivel que guían a otras heurísticas subordinadas para explorar y explotar el espacio de búsqueda, siendo aplicables a múltiples problemas distintos. V. F.

¿Cuál de las siguientes afirmaciones describe mejor un problema de tipo NP-Duro?. Son problemas que pueden resolverse en tiempo polinomial determinista. Son problemas que garantizan una solución óptima en un tiempo razonable siempre que n < 1000. Son problemas "al menos tan duros" como los NP-completos y, a menudo, requieren métodos aproximados para instancias grandes. Son un subconjunto de los problemas P (P subconjunto de NP-Duro).

En los problemas de optimización, una solución candidata es válida simplemente con que verifique todas las restricciones del problema, independientemente del valor de su función objetivo. V. F.

En los problemas de optimización, una solución candidata debe tener obligatoriamente el mejor valor posible de la función de calidad f para ser considerada una solución válida. V. F.

Los algoritmos heurísticos son dependientes del problema, mientras que las metaheurísticas son algoritmos aproximados más generales aplicables a una gran variedad de problemas. V. F.

Una heurística diseñada para un problema específico garantiza poder aplicarse con éxito a cualquier otro tipo de problema de optimización. V. F.

La clase de complejidad P agrupa los problemas que pueden resolverse con un algoritmo determinista en tiempo polinomial (los más simples). V. F.

Los problemas NP son aquellos que NO pueden resolverse, bajo ninguna circunstancia, en tiempo polinomial, ni siquiera con algoritmos no deterministas. V. F.

¿Cuál es la relación correcta entre las clases de complejidad según el documento?. NP subconjunto de P. P subconjunto de NP. P = NP - Hard. NP - Hard.

Los métodos exactos son ideales para cualquier tamaño de problema, garantizando siempre el óptimo en segundos. V. F.

Para problemas NP-Duros con n > 100, se suelen utilizar métodos aproximados que generan soluciones de calidad en tiempo razonable, aunque no garantizan el óptimo global. V. F.

En un problema combinatorio, buscamos una agrupación u ordenación de un conjunto finito que verifique ciertas restricciones. V. F.

Evaluar si una solución candidata es válida en un problema combinatorio es computacionalmente más costoso que encontrar la solución óptima. V. F.

Una solución candidata es aquella que cumple necesariamente todas las condiciones y restricciones del problema. V. F.

Una solución (o solución factible/buena) es una solución candidata que verifica todas las restricciones. V. F.

En un problema de optimización, ¿cuál es el objetivo principal respecto a la función f?. Ignorar la función f y solo cumplir restricciones. Minimizar o Maximizar el valor de f. Encontrar el valor promedio de f.

La búsqueda constructiva trabaja con soluciones completas y las va modificando iterativamente. V. F.

La búsqueda perturbativa trabaja con soluciones completas y realiza extensiones o modificaciones sobre ellas. V. F.

La búsqueda sistemática es completa, es decir, garantiza encontrar la solución óptima o determinar que no existe. V. F.

La búsqueda local es un tipo de búsqueda sistemática que garantiza encontrar siempre el óptimo global. V. F.

Intensificación se refiere a la capacidad de explorar nuevas regiones del espacio de búsqueda no visitadas anteriormente. V. F.

Diversificación se refiere a la exploración de nuevos espacios de búsqueda. V. F.

¿Qué características debe cumplir una buena codificación (representación) de una solución?. Complejidad, Desconexión y Rigidez. Completitud, Conexión y Eficiencia. Aleatoriedad, Dualidad y Redundancia.

Respecto a la representación de soluciones, ¿cuál se considera la "peor" opción por generar redundancia?. One-to-one (Uno a uno). Many-to-one (Muchos a uno). One-to-many (Uno a muchos).

Las metaheurísticas basadas en poblaciones mantienen y mejoran una única solución a lo largo del tiempo. V. F.

PREGUNTA 22. SI. NO.