Algoritmia

Dado el problema del laberinto con tres movimientos, ¿se puede aplicar un esquema de programación dinámica para obtener un camino de salida?. No, con este esquema se puede conocer el número total de caminos distintos que conducen a la salida pero no se puede saber la composición de ninguno de ellos. Si, en caso de existir con este esquema siempre se puede encontrar un camino desalida. No, para garantizar que se encuentra un camino de salida hay que aplicar métodos de búsqueda exhaustiva como vuelta atrás o ramificación y poda.

Dado el problema del laberinto con tres movimientos, se desea saber el número de caminos distintos desde la casilla inicial (1, 1) hasta la casilla (n, m) y para ello se aplica un esquema de programación dinámica. En cuanto a la complejidad temporal, ¿cuál es la mejora de la versión recursiva con memoización frente a la recursiva ingenua que se obtiene a partir del esquema divide y vencerás?. La mejora no está garantizada puesto que la versión recursiva con memoización podría ser peor que la obtenida a partir del esquema divide y vencerás. De una complejidad exponencial que se obtendría con la ingenua se reduciría a polinómica con la de memoización. De una complejidad cuadrática que se obtendría con la ingenua se reduciría a lineal con la de memoización.

Dado el problema del laberinto con tres movimientos, se pretende conocer la longitud del camino de salida más corto. Para ella se aplica el esquema voraz con un criterio de selección que consiste en elegir primero el movimiento "Este" siempre que la casilla sea accesible. Si no lo es se descarta ese movimiento y se prueba con "Sureste" y por último, si este tampoco es posible, se escoge el movimiento "Sur". ¿Qué se puede decir del algoritmo obtenido?. Que es un algoritmo voraz pero sin garantía de solucionar el problema…. Que en realidad no es un algoritmo voraz pues el criterio de selección no lo es. Que en realidad no es un algoritmo voraz pues las decisiones que se toman no deberían reconsiderarse.

Dado el problema del laberinto con tres movimientos, se desea saber el número de caminos distintos desde la casilla inicial (1,1) hasta la casilla (n, m) y para ello se aplica el esquema programación dinámica para obtener un algoritmo lo más eficiente posible en cuanto a complejidad temporal y espacial. ¿Cuáles serían ambas complejidades?. Temporal Θ(n x m) y espacial Θ(n x m). Temporal Θ(n x m) y espacial Θ(mín{n,m}). Temporal Θ(máx{n, m}) y espacial Θ(máx{n, m}).

Dado el problema del laberinto con tres movimientos, se desea saber el número de caminos distintos desde la casilla inicial (1, 1) hasta la casilla (n, m) y para ello se aplica un esquema de divide y vencerás. ¿Cuál sería la recurrencia apropiada para el caso general?. nc(n, m) = nc(n - 1, m) + nc(n, m - 1) + nc(n - 1, m - 1). nc(n, m) = nc(n - 1, m) * nc(n, m - 1) * nc(n - 1, m - 1). Ninguna de las otras dos recurrencias se corresponde con un esquema de divide y vencerás.

Dado el problema del laberinto con tres movimientos, ¿cuál de las estrategias siguientes proveería de una cota optimista para ramificación y poda?. Suponer que ya no se van a realizar más movimientos. Las otras dos estrategias son ambas válidas. Suponer que en adelante todas las casillas del laberinto son accesibles.

Se pretende resolver la versión general (8 movimientos) del problema del laberinto mediante un algoritmo de vuelta atrás. ¿Qué ocurre si el subóptimo de partida coincide con la cota optimista del nodo inicial?. Que el algoritmo sería incorrecto ya que el subóptimo de partida es en realidad una cota pesimista para el nodo inicial. Que la cota optimista está mal estimada. Que el algoritmo no debería explorar ningún nodo más.

Dada la versión restringida del problema del laberinto, estamos interesados en obtener, para cada casilla accesible del laberinto, el camino más corto entre el origen y esa casilla. ¿Qué esquema es el más apropiado en este caso?. La versión iterativa de programación dinámica. Memoización. Ambas técnicas resultan equivalentes.

Dada la versión restringida del problema del laberinto, ¿se podría modificar la solución naive de divide y vencerás para que obtenga el número total de caminos diferentes, de cualquier longitud, que conducen a la salida desde el origen?. No se puede, ya que no se trataría de un problema de optimización. No se puede, puesto que se trata de un nuevo problema que no cumple las condiciones de aplicación de divide y vencerás. Sí, pero puesto que se trata de un nuevo problema, hay que cambiar la recurrencia matemática inicial.

Dada la versión restringida del problema del laberinto, si solo se desea conocer la longitud del camino de salida más corto, ¿Cuál es la mejor complejidad temporal y espacial que se puede conseguir si se aplica programación dinámica?. Temporal Θ(n·m) y espacial Θ(mín{n,m}). Ninguna de las otras dos opciones es cierta. Temporal Θ(n·m) y espacial Θ(n·m).

Dada la solución naive de la versión restringida del problema del laberinto, en general, ¿Cuántas veces se llega al caso base de la recursión?. Solo una. Un valor que puede crecer exponencialmente con el tamaño del laberinto. Un valor que a lo sumo es n·m.

Con respecto a la técnica poda con memoria, solo una de las siguientes afirmaciones es cierta. Cuál es?. No resulta eficaz para resolver la versión general del problema del laberinto mediante ramificación y poda. No se puede aplicar para resolver la versión restringida del problema del laberinto. En una solución de vuelta atrás para la versión general del problema del laberinto, sirve también para descartar ciclos.

Dada la versión restringida del problema del laberinto, ¿Cuál de las estrategias siguientes proveería de una cota optimista para ramificación y poda?. Suponer que en adelante todas las casillas del laberinto son accesibles. Las otras dos estrategias son ambas válidas. Suponer que ya no se van a realizar más movimientos.

Se pretende resolver la versión general del problema del laberinto mediante ramificación y poda. Para obtener la cota optimista de un nodo cualquiera procedemos así: calculamos el número de casillas que quedan, por la diagonal derecha–abajo, hasta llegar a una pared del laberinto. A ese valor le sumamos el número de casillas que podrían quedar desde esa pared hasta la salida utilizando únicamente movimientos del tipo abajo o derecha, según corresponda. ¿Qué podemos decir acerca de la cota optimista que se obtendría?. Que no cumple la condición para ser una cota optimista correcta. Que no sería eficiente con respecto a otras cotas optimistas, ya que su cálculo requiere una complejidad temporal que no es constante. Que es una cota optimista correcta y además puede obtenerse con complejidad temporal constante.

La distancia de Manhattan (d) entre dos puntos (x1, y1) y (x2, y2) viene dada por la expresión (d = |x1 - x2| + |y1 - y2|). ¿Podría utilizarse como cota optimista para resolver la versión general de problema del laberinto?. No, puesto que incumple la condici´on para ser una cota optimista correcta. Sí, pero hay otros estimadores que se suelen comportar mejor ante este problema. Sí, y además tiene la ventaja de que se puede calcular con complejidad temporal constante.

Dada la versión general del problema del laberinto, se pretende resolver mediante vuelta atrás haciendo uso de un mecanismo de poda basado en la mejor solución encontrada hasta el momento. ¿Cuándo se podaría un nodo?. Cuando el valor de su cota optimista supere al valor de la mejor cota pesimista encontrada hasta el momento. Cuando el valor de su cota pesimista supere al valor de su cota optimista. Cuando el valor de su cota optimista supere al valor de su cota pesimista.

Dada la versión general del problema del laberinto ¿Qué ocurre si la cota optimista de un nodo resulta ser el valor que se obtiene de una solución factible pero que no es la mejor en el subárbol generado por ese nodo?. Nada especial, las cotas optimistas se corresponden con soluciones factibles que no tienen por qué ser las mejores. Que el algoritmo sería incorrecto pues podría descartarse el nodo que conduce a la solución óptima. Que el algoritmo sería más lento pues se explorarían más nodos de los necesarios.

Dada la versión general del problema del laberinto, tratamos de completar un nodo cualquiera del árbol de búsqueda con el camino que, en caso de existir, obtendríamos asumiendo solo los tres movimientos de la versión restringida. ¿Qué obtendríamos en el caso de completar el nodo?. Una cota optimista para ese nodo. Un nodo hoja del subárbol generado por aquel nodo. Nada de interés, puesto que el camino resultante no contemplaría todos los movimientos permitidos.

Estamos resolviendo la versión restringida del problema del laberinto. Ya hemos obtenido el almacén de resultados parciales. ¿Con qué complejidad temporal podemos obtener un camino de salida de longitud mínima si es que existe?. Θ(m+n). Ω(mín(n,m)) y O(m·n). Θ(m·n).

¿Cuál de los siguientes enfoques es más eficiente para resolver la versión restringida del problema del laberinto?. Enfoque voraz. Enfoque de programación dinámica. Enfoque de vuelta atrás.

¿Cuál es la característica principal de un algoritmo voraz aplicado al problema del laberinto?. Explora exhaustivamente todas las posibles soluciones del laberinto. Toma decisiones locales óptimas en cada paso sin considerar el panorama general. Utiliza una estrategia basada en estimaciones heurísticas para encontrar la solución óptima.

Se pretende resolver la versión general del problema del laberinto mediante ramificación y poda y para ello se usa una estrategia que consiste en priorizar las expansiones de los nodos que contienen un camino explorado mas corto. ¿Qué podemos decir del algoritmo resultante?. Que la primera hoja a la que se llegue es la solución del problema y por lo tanto, ya no será necesario explorar más nodos de la lista de nodos vivos, aunque no esté vacía. Que el recorrido en el arbol de búsqueda será equivalente a un recorrido por niveles, por lo que no es necesario utilizar una cola de prioridad. Las otras dos opciones son ambas ciertas.

Se pretende resolver la versión general del problema del laberinto mediante un algoritmo de búsqueda y enumeración. Para reducir el número de nodos explorados, ¿Qué mecanismo de los relacionados garantiza encontrar la solución y resulta a priori más eficaz? ́. Usar una matriz de booleanos para descartar caminos que llegan a una casilla ya visitada. Cada casilla (i, j) de la matriz se inicializa con el valor false. Usar una matriz de enteros donde se almacena la longitud del mejor camino encontrado hasta el momento que llega a cada casilla del laberinto. Cada casilla (i, j) de la matriz se inicializa con el valor infinito. Usar una matriz de enteros donde se almacena la longitud del mejor camino encontrado hasta el momento que llega a cada casilla del laberinto. Cada casilla (i, j) de la matriz se inicializa con la solución de programación dinámica para la versión restringida del problema asumiendo que el destino es (i, j).

Dada la versión general del problema del laberinto, queremos obtener todos los caminos que llegan a la salida. En este caso, ¿sería útil utilizar la distancia de Chebyshev? (La distancia de Chebyshev entre dos puntos viene dada por la diferencia máxima entre las coordenadas de cada dimensión). No. Sí, presumiblemente mejoraría la estrategia de búsqueda. Sí, presumiblemente mejoraría la poda basada en la mejor solución encontrada hasta el momento.

Dada la versión restringida del problema del laberinto, queremos obtener todos los caminos que llegan a la salida. ¿Cuál de las siguientes técnicas resultaría mas eficiente?. Tanto programación dinámica como vuelta atrás resultarían equivalentes. Programación dinámica. Vuelta atrás.

Queremos resolver la versión general del problema del laberinto mediante ramificación y poda y para ello implementamos la lista de nodos vivos mediante una pila.¿qué podemos decir del algoritmo resultante?. Que para mejorar a vuelta atrás será necesario hacer uso de las cotas pesimistas de los nodos intermedios. Que presumiblemente será más eficiente que vuelta atrás, tanto en tiempo como en espacio requerido. Que presumiblemente será menos eficiente que vuelta atrás.

Se pretende resolver la versión general del problema del laberinto y para ello se dispone de tres posibles cotas pesimistas. ¿Cuál deberíamos utilizar para conseguir un programa lo más rápido posible?. Depende, para contestar a esta cuestión es necesario disponer de más información. La que obtenga valores más elevados. La que más se aproxime a la solución óptima del nodo en cuestión.

Se pretende resolver la versión general del problema del laberinto mediante ramificación y poda. Utilizamos una cota optimista que consiste en estimar la dificultad del camino restante haciendo uso del algoritmo voraz implementado en la práctica 7. ¿Qué podemos decir del programa resultante?. Que presumiblemente exploraría más nodos de los necesarios. Que presumiblemente exploraría menos nodos de los necesarios. Que si comienza con una solución subóptima encontraría antes la óptima.

Se pretende resolver la versión general del problema del laberinto mediante ramificación y poda. Para obtener la cota optimista de un nodo cualquiera procedemos así: calculamos el número de casillas que quedan, por la diagonal derecha–abajo, hasta llegar a un extremo del laberinto. A ese valor le sumamos el número de casillas que podrían quedar desde ese extremo hasta la salida utilizando únicamente movimientos del tipo abajo o derecha, según corresponda. ¿Qué podemos decir acerca de la cota optimista que se obtendría?. Que no cumple la condición para ser una cota optimista correcta. Que no sería eficiente con respecto a otras cotas optimistas, ya que su cálculo requiere una complejidad temporal que no es constante. Que es una cota optimista correcta y además puede obtenerse con complejidad temporal constante.

Dada la versión general del problema del laberinto ¿Qué ocurre si la cota optimista de un nodo resulta ser el valor que se obtiene de una solución factible pero que no es la mejor en el subárbol generado por ese nodo?. Nada especial, las cotas optimistas se corresponden con soluciones factibles que no tienen por qué ser las mejores. Que el algoritmo sería incorrecto pues podría descartarse el nodo que conduce a la solución óptima. Que el algoritmo sería m´ as lento pues se explorarían más nodos de los necesarios.