Tema7 Flashcards
(46 cards)
¿En qué consiste el problema del agente viajero (TSP)?
Consiste en encontrar la ruta óptima para que un viajero visite un conjunto de ciudades una única vez y regrese a la ciudad de origen minimizando la distancia o el costo.
¿Cómo se representa el problema del agente viajero en términos de grafos?
Se modela como un grafo donde los nodos representan ciudades y las aristas representan las posibles rutas con sus respectivos costos.
¿Cuál es el objetivo del problema de la mochila?
Determinar qué combinación de objetos maximiza el valor total sin exceder la capacidad de la mochila.
¿Cómo se resuelve el problema de programación lineal entera?
Utilizando métodos como el Simplex, el método de punto interior o la ramificación y poda.
¿En qué se diferencia el problema de enrutamiento (VRP) del problema del agente viajero?
En VRP hay múltiples rutas óptimas para una flota de vehículos en lugar de una única ruta óptima.
¿Qué es el problema de satisfacibilidad booleana (SAT)?
Es determinar si existe una combinación de valores de verdad para variables booleanas que haga que una expresión lógica sea verdadera.
¿Cuál es el objetivo del problema de transporte en optimización?
Minimizar el costo total de trasladar mercancías desde varios puntos de abastecimiento hasta puntos de destino.
¿En qué consiste el problema del recubrimiento (SCP)?
Encontrar el subconjunto mínimo de elementos que cubra todo un conjunto de referencia.
¿El problema del agente viajero es NP-difícil? (Sí/No)
Sí.
¿El método de ramificación y poda garantiza encontrar la solución óptima en el problema de la mochila? (Sí/No)
Sí.
¿El método Simplex se utiliza para resolver problemas de programación lineal? (Sí/No)
Sí.
¿El problema de enrutamiento es una variante del problema del agente viajero? (Sí/No)
Sí.
¿El problema SAT pertenece a la clase NP-completo? (Sí/No)
Sí.
¿El problema de la mochila solo puede resolverse con algoritmos exactos? (Sí/No)
No, también se pueden usar heurísticas y metaheurísticas.
¿El problema del transporte se puede modelar como un problema de programación lineal? (Sí/No)
Sí.
¿El problema del recubrimiento es un problema de optimización combinatoria? (Sí/No)
Sí.
El problema del agente viajero es un problema de optimización ____.
combinatoria.
El problema de la mochila busca maximizar el ____ de los objetos sin superar una capacidad dada.
valor total.
El método de programación lineal más utilizado es el método ____.
Simplex.
El problema del enrutamiento busca optimizar rutas para una flota de ____.
vehículos.
El problema SAT busca una asignación de valores de ____ que satisfaga una expresión lógica.
verdad.
El problema del transporte busca minimizar el ____ total de distribución de mercancías.
costo.
El problema del recubrimiento intenta encontrar un subconjunto ____ del conjunto original.
mínimo.
La técnica de ramificación y poda se usa para resolver problemas de optimización ____.
exacta.
