Cuando se resuelve un algoritmo de vuelta atrás un problema de n decisiones, en el que siempre hay como mínimo dos opciones para cada decisión, ¿cuál de las siguientes complejidades en el caso peor es la mejor que nos podemos encontrar? O(2^n) O(n!) O(n^2). Al resolver el problema del viajante de comercio mediante vuelta atrás y asumiendo un grafo de n vértices totalmente conexo, ¿cuál de estas es una buena cota pesimista al iniciar la búsqueda? Se multiplica n por la distancia de la arista más corta que nos queda por considerar Se ordenan las aristas restantes de menor a mayor distancia y se calcula la suma de las n aristas más cortas Se resuelve el problema usando un algoritmo voraz que añade cada vez al camino el vértice más cercano al último añadido. Se desea obtener todas las permutaciones de una lista compuesta por n elementos, ¿Qué esquema es el más adecuado? Ramificación y poda, puesta que con buenas funciones de cota es más eficiente para este problema que vuelta atrás Divide y vencerás, puesto que la división en sublistas se podría hacer en tiempo constante Vuelta atrás, para este problema no hay un esquema más eficiente. La complejidad en el menor de los casos de un algoritmo de ramificación y poda... es siempre exponencial con el número de decisiones a tomar suele ser polinómica con el número de alternativas por cada decisión puede ser polinómica con el número de decisiones a tomar. La complejidad en el peor de los casos de un algoritmo de ramificación y poda... Puede ser exponencial con el número de alternativas por cada decisión Puede ser polinómica con el número de decisiones a tomar Es exponencial con el número de decisiones a tomar. La estrategia de ramificación y poda genera las soluciones posibles al problema mediante... un recorrido guiado por estimaciones de las mejores ramas del árbol que representa el espacio de soluciones un recorrido en profundidad del árbol que representa el espacio de soluciones un recorrido en anchura que representa el espacio de soluciones. ¿Para qué sirven las cotas pesimistas en ramificación y poda? Para tener la certeza de que la cota optimista está bien calculada Para descartar nodos basándose en la preferencia por algún otro nodo ya completado Para descartar nodos basándose en el beneficio esperado. En los algoritmos de ramificación y poda, ¿el valor de una cota pesimista es mayor que el valor de una cota optimista? (entendiendo que ambas cotas se aplican sobre el mismo nodo) En general sí, si se trata de un problema de maximización, aunque en ocasiones ambos valores pueden coincidir En general sí, si se trata de un problema de minimización, aunque en ocasiones ambos valores pueden coincidir No, nunca es así. En los algoritmos de ramificación y poda, ¿el valor de una cota pesimista es menor que el valor de una cota optimista? En general sí, si se trata de un problema de minimización, aunque en ocasiones ambos valores pueden coincidir En general sí, si se trata de un problema de maximización, aunque en ocasiones ambos valores pueden coincidir Sí, siempre es así. En los algoritmos de ramificación y poda... El uso de cotas pesimistas sólo resulta eficaz cuando se dispone de una posible solución de partida Una cota optimista es necesariamente un valor insuperable, de no ser así se podría podar el nodo que conduce a la solución óptima Una cota optimista es necesariamente un valor alcanzable, de no ser así no está garantizado que se encuentre la solución óptima. La ventaja de la estrategia ramificación y poda frente a vuelta atrás es que la primera genera las soluciones posibles al problema mediante... un recorrido guiado por una cola de prioridad de donde se extraen primero los nodos que representan los subárboles más prometedores del espacio de soluciones las otras dos opciones son verdaderas un recorrido guiado por estimaciones de las mejores ramas del árbol que representa el espacio de soluciones. ¿Cuál es la diferencia principal entre una solución de vuelta atrás y una solución de ramificación y poda para el problema de la mochila? El orden de exploración de las soluciones El coste asintótico en el caso peor El hecho que la solución de ramificación y poda puede empezar con una solución subóptima voraz y la de vuelta atrás no. Tratándose de un problema de optimización, en la lista de nodos vivos de ramificación y poda... sólo se introducen nodos prometedores, es decir, nodos que pueden mejorar la mejor solución que se tiene en ese momento puede haber nodos que no son prometedores las otras dos opciones son ciertas. Cuando resolvemos un problema mediante un esquema de ramificación y poda... los valores entre los cuales se elige en cada una de las decisiones tienen que formar un conjunto finito las decisiones sólo pueden ser binarias los valores entre los cuales se elige en cada una de las decisiones pueden formar un conjunto infinito. La estrategia de ramificación y poda necesita cotas pesimistas... para decidir el orden de visita de los nodos del árbol de soluciones sólo si se usa para resolver problemas de optimización para determinar si una solución es factible. El uso de funciones de cota en ramificación y poda... transforma en polinómicas complejidades que antes eran exponenciales puede reducir el número de instancias del problema que pertenecen al caso peor garantiza que el algoritmo va a ser más eficiente ante cualquier instancia del problema. En la estrategia ramificación y poda... cada nodo tiene su propia cota pesimista y también su propia cota optimista cada nodo tiene su propia cota pesimista, la cota optimista sin embargo, es común para todos los nodos cada nodo tiene su propia cota optimista, la cota pesimista sin embargo, es común para todos los nodos. Si para resolver un mismo problema usamos un algoritmo de vuelta atrás y lo modificamos mínimamente para convertirlo en un algoritmo de ramificación y poda, ¿qué cambiamos realmente? La comprobación de las soluciones factibles: en ramificación y poda no es necesario puesto que sólo genera nodos factibles Cambiamos la función que damos a la cota pesimista Aprovechamos mejor las cotas optimistas. Si para resolver un mismo problema usamos un algoritmo de ramificación y poda y lo modificamos mínimamente para convertirlo en un algoritmo de vuelta atrás, ¿qué cambiamos realmente? cambiamos la función que damos a la cota pesimista provocamos que las cotas optimistas pierdan eficacia sería necesario comprobar si las soluciones son factibles o no puesto que ramificación y poda solo genera nodos factibles. En el esquema de vuelta atrás, los mecanismos de poda basados en la mejor solución hasta el momento... Las dos anteriores son verdaderas garantizan que no se va a explorar nunca todo el espacio de soluciones posibles pueden eliminar soluciones parciales que son factibles. En ausencia de cotas optimista y pesimistas, la estrategia de vuelta atrás... no se puede usar para resolver problemas de optimización debe recorrer siempre todo el árbol no recorre todo el árbol si hay manera de descartar subárboles que representan conjuntos de soluciones no factibles. La estrategia de vuelta atrás es aplicable a problemas de selección y optimización en los que: El espacio de soluciones puede ser tanto finito como infinito pero en este último caso debe ser al menos numerable El espacio de soluciones es un conjunto infinito El espacio de soluciones es un conjunto finito. Decid cuál de estas tres es la cota optimista que poda más eficientemente cuando se usa la estrategia de vuelta atrás para resolver el problema de la mochila: El valor de la mochila discreta que se obtiene usando un algoritmo voraz basado en el valor específico del objeto El valor de una mochila El valor óptimo de la mochila continua correspondiente. Decid cuál de estas tres no sirve como cota optimista para obtener el valor óptimo de la mochila discreta: El valor de una mochila que contiene todos los objetos aunque se pase del peso máximo permitido El valor de la mochila discreta que se obtiene usando un algoritmo voraz basado en el valor específico de los objetos El valor de la mochila continua correspondiente. Decid cuál de estas tres es la cota pesimista más ajustada al valor óptimo de la mochila discreta: El valor de la mochila discreta que se obtiene usando un algoritmo voraz basado en el valor específico de los objetos El valor de la mochila continua correspondiente El valor de una mochila que contiene todos los objetos aunque se pase del peso máximo permitido. Es un problema de optimización, si el dominio de las decisiones es un conjunto infinito Podemos aplicar el esquema vuelta atrás siempre que se trate de un conjunto infinito numerable Es probable que a través de programación dinámica se obtenga un algoritmo eficaz que lo soluciones Una estrategia voraz puede ser la única alternativa. Dado un problema de optimización cualquiera, ¿la estrategia de vuelta atrás garantiza la solución óptima? Es condición necesaria que el dominio de las decisiones sea discreto o discretizable y que el número de decisiones a tomar esté acotado Sí, puesto que ese método analiza todas las posibilidades Sí, siempre que el dominio de las decisiones sea discreto o discretizable y además se empleen mecanismos de poda basados en la mejor solución hasta el momento. Se desea encontrar el camino más corto entre dos ciudades.
Para ello se dispone de una tabla con la distancia entre los pares de ciudades en los que hay carreteras o un valor centinela (por ejemplo, -1) si no hay, por lo que para ir de la ciudad inicial a la final es posible que haya que pasar por varias ciudades. Para limitar la búsqueda en un algoritmo de vuelta atrás, se utiliza la solución de un algoritmo voraz basado en moverse en cada paso a la ciudad, de entre las posibles según el mapa de carreteras, que esté más cercana al destino en línea recta.
¿Qué tipo de cota sería? Sería una cota pesimista siempre que se tenga la certeza de que esa aproximación encuentra la solución factible. Ninguna de las otras dos opciones Sería una cota optimista siempre que se tenga la certeza de que esa aproximación encuentra una solución factible. Se desea encontrar el camino más corto entre dos ciudades.
Para ello se dispone de una tabla con la distancia entre los pares de ciudades en los que hay carreteras o un valor centinela (por ejemplo, -1) si no hay, por lo que para ir de la ciudad inicial a la final es posible que haya que pasar por varias ciudades. Como también se conocen las coordenadas geográficas de cada ciudad se quiere usar la distancia geográfica (en línea recta) entre cada par de ciudades para como cota para limitar la búsqueda en un algoritmo de vuelta atrás.
¿Qué tipo de cota sería? No se trataría de ninguna poda puesta que es posibls que esa heurística no encuentre una solución factible Una cota pesimista Una cota óptimista. Se desea encontrar el camino más corto entre dos ciudades.
Para ello se dispone de una tabla con la distancia entre los pares de ciudades en los que hay carreteras o un valor centinela (por ejemplo, -1) si no hay, por lo que para ir de la ciudad inicial a la final es posible que haya que pasar por varias ciudades. También se conocen las coordenadas geográficas de cada ciudad y por tanto la distancia geográfica (en línea recta) entre cada par de ciudades. Se pretende acelerar la búsqueda de un algoritmo de ramificación y poda priorizando los nodos vivos (ciudades) que estén a menor distancia geográfica de la ciudad objetivo.
Seleccione una: El nuevo algoritmo solo será más rápido para algunas instancias del problema Esta estrategia no asegura que se obtenga el camino más corto El nuevo algoritmo siempre sea más rápido. Se desea encontrar el camino más corto entre dos ciudades.
Para ello se dispone de una tabla con la distancia entre los pares de ciudades en los que hay carreteras o un valor centinela (por ejemplo, -1) si no hay, por lo que para ir de la ciudad inicial a la final es posible que haya que pasar por varias ciudades. También se conocen las coordenadas geográficas de cada ciudad y por tanto la distancia geográfica (en línea recta) entre cada par de ciudades. Para limitar la búsqueda en un algoritmo de vuelta atrás, se utiliza la solución de un algoritmo voraz basado en moverse en cada paso a la ciudad, de entre las posibles según el mapa de carreteras, que esté más cercana al destino según su distancia geográfica.
Este algoritmo voraz, ¿serviría como cota pesimista?
Seleccione una: No, ya que no asegura que se encuentre una solución factible Sí, puesto que la distancia geográfica asegura que otra solución mejor no es posible No, ya que en algunos casos puede dar distancias menores que la óptima.
