El método voraz se emplea en la resolución de problemas de selección y optimización en los que se pretende encontrar: Una solución que satisfaga unas restricciones y optimice una cierta función objetivo. Todas las soluciones que satisfagan unas restricciones. La dos respuestas anteriores son correcta. Voraz siempre da solución óptima: Al problema de la mochila sin fraccionamiento. Al problema de la mochila con fraccionamiento. A los dos. En el método Voraz, aunque las decisiones son irreversibles, podemos asegurar que: Siempre obtendremos la solución óptima. Siempre obtendremos una solución factible. Sólo obtendremos la solución óptima para algunos problemas. Dado un problema de optimización y un algoritmo Voraz que lo soluciona, ¿cuándo podemos estar seguros de que la solución obtenida
será óptima?: Cuando demostremos formalmente que el criterio conduce a una solución óptima para cualquier instancia del problema. Voraz siempre encuentra solución óptima. En ambos casos. Las dos son correctas. Si aplicamos un algoritmo voraz que no nos garantiza la solución óptima sobre un problema entonces... Obtendremos una solución factible.
Puede que no encuentre ninguna solución aunque ésta exista. Si el problema tiene solución óptima, el esquema voraz nos garantiza que la encuentra. El problema de la mochila, ¿encuentra su solución óptima empleando la estrategia voraz?: Sólo para el caso de la mochila con fraccionamiento Sólo para el caso de la mochila sin fraccionamiento En cualquiera de los casos anteriores. Dado un grafo G que representa las poblaciones de la provincia de Alicante de más de 20.000 habitantes junto con todas las carreteras de
conexión entre ellas. Queremos obtener el recorrido que nos permita pasar por todas estas ciudades una única vez y volver al punto de
origen recorriendo el mínimo número de kilómetros. Si aplicamos una estrategia voraz sobre este grafo obtendremos... Una solución factible La solución óptima Puede que no encuentre ninguna solución aunque ésta exista. Al aplicar backtracking obtenemos la solución óptima a un problema: Siempre En algunos casos Sólo cuando el problema cumple el principio de Optimalidad. Si aplicamos un esquema backtracking que no nos garantiza la solución óptima sobre un problema entonces Obtendremos una solución factible.
Puede que no encuentre ninguna solución aunque ésta exista. Ninguna de las anteriores. Backtracking es aplicable a problemas de selección y optimización en los que: El espacio de soluciones es un conjunto infinito. El espacio de soluciones es un conjunto finito. En cualquiera de los casos. En un problema resuelto por backtracking, el conjunto de valores que pueden tomar las componentes de la tupla solución, ha de ser: Infinito. finito continuo. Al aplicar vuelta atrás a la solución de problemas, obtenemos algoritmos con costes computacionales: Polinómicos. Exponenciales. Los dos son correctos. Depende del problema. Vuelta atrás se emplea en la resolución de problemas de optimización en los que se pretende encontrar: Una solución que satisfaga unas restricciones y optimice una cierta función objetivo. Todas las soluciones que satisfagan unas restricciones. La dos respuestas anteriores son correctas. Bactracking procede a obtener la solución a un problema de optimización empleando la siguiente estrategia: Genera todas las combinaciones de la solución y selecciona la que optimiza la función objetivo. Genera todas las soluciones factibles y selecciona la que optimiza la función objetivo. Genera una solución factible empleando un criterio óptimo. Bactracking es una técnicas de resolución general de problemas basada en: La búsqueda sistemática de soluciones. La construcción directa de la solución. Ninguna de las anteriores. Bactracking genera las soluciones posibles al problema: Mediante el recorrido en profundidad del árbol que representa el espacio de soluciones. Mediante el recorrido en anchura del árbol que representa el espacio de soluciones Ninguna de las anteriores. El problema de la mochila, ¿puede solucionarse empleando vuelta atrás?: Sólo para el caso de la mochila con fraccionamiento Sólo para el caso de la mochila sin fraccionamiento Se puede aplicar para ambos casos. El problema del viajante de comercio puede resolverse correctamente empleando estos esquemas de programación: Solo backtracking Empleando cualquiera de estos: Voraz y backtracking. Sólo programación dinámica. El tiempo de ejecución de un algoritmo de ramificación y poda depende de: La instancia del problema La función de selección de nodos para su expansión De ambos. Dado un problema resuelto mediante backtracking y mediante ramificación y poda, el coste computacional de la solución por
ramificación y poda, en comparación con la de backtracking es: Igual Mayor Menor. ¿Cuál de estas afirmaciones es falsa? Bactracking inspecciona todo el espacio de soluciones de un problema mientras que Ramificación y poda no. La complejidad en el peor caso de las soluciones Backtracking y ramificación y poda a un mismo problema es la misma. Para un mismo problema, ramificación y poda explora siempre un número de nodos menor o igual que backtracking. El problema de la asignación de turnos tiene solución óptima voraz aplicando la siguiente estrategia: Seleccionamos los alumnos en orden descendente de preferencia respetando las restricciones de cabida de cada turno. Seleccionamos los alumnos en orden ascendente de preferencia respetando las restricciones de cabida de cada turno El problema no tiene solución óptima voraz. El problema de la asignación de turnos tiene solución óptima empleando: Bactracking Voraz Ambos. El problema de la asignación de turnos tiene solución... Optima mediante bactracking Aproximada (sub-óptima) mediante voraz Ambas. Dada la solución recursiva mediante vuelta atrás al problema de la asignación de turnos ¿cuántas nuevas llamadas recursivas genera cada
llamada recursiva? una o dos una o ninguna ninguna de las anteriores. El problema de la asignación de turnos resuelto mediante backtracking tiene una complejidad: Exponencial Polinómica Ninguna de la dos.
