ADA Laberinto

Dado el problema del laberinto con tres movimientos, se desea saber el numero de caminos distintos desde la casilla inicial (1, 1) hasta la casilla (n,m) y para ello se aplica un esquema de programacion dinamica. En cuanto a la complejidad temporal, ¿cual es la mejora de la version recursiva con memoizacion frente a la recursiva ingenua que se obtiene a partir del esquema divide y venceras?. De una complejidad cuadratica que se obtendrıa con la ingenua se reducirıa a lineal con la de memoizacion. De una complejidad exponencial que se obtendrıa con la ingenua se reducirıa a polinomica con la de memoizacion. La mejora no esta garantizada puesto que la version recursiva con memoizacion podrıa ser peor que la obtenida a partir del esquema divide y venceras.

Dado un problema de laberinto en el que se permiten tres tipos de movimientos, se desea calcular el número de caminos distintos desde la casilla inicial (1,1) hasta la casilla final (n,m), utilizando un enfoque de programación dinámica. En cuanto a la complejidad temporal, ¿cuál es la mejora que ofrece la versión recursiva con memoización frente a la versión recursiva ingenua, basada en el esquema de divide y vencerás?. La complejidad cuadrática que se obtendría con la versión ingenua se reduciría a lineal con la versión con memoización. La complejidad exponencial que se obtendría con la versión ingenua se reduciría a polinómica con la versión con memoización. La mejora no está garantizada, ya que la versión recursiva con memoización podría ser más lenta que la basada en divide y vencerás.

Dado un problema de laberinto en el que se permiten tres tipos de movimientos, ¿cuál de las siguientes estrategias proporcionaría una cota optimista adecuada para aplicar el método de 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.

Dado el problema del laberinto con tres movimientos válidos (Este, Sur y Sureste), se desea calcular el número de caminos distintos desde la casilla inicial (1,1) hasta la casilla final (n,m), aplicando 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). Ninguna de las otras dos recurrencias es válida. nc(n,m)=nc(n−1,m)+nc(n,m−1)+nc(n−1,m−1).

Dado el problema del laberinto con tres movimientos válidos (Este, Sur y Sureste), ¿se puede aplicar un esquema de programación dinámica para obtener un camino de salida, no solo contar cuántos hay?. Sí, con este esquema siempre se puede encontrar un camino de salida si existe. 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. 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.

Dado el problema del laberinto con tres movimientos, se desea saber el numero de caminos distintos desde la casilla inicial(1,1) hasta la casilla (n,m) y para ello se aplica se aplica el esquema de programacion dinamica para obtener un algoritmo lo mas eficiente posible en cuanto a complejidad temporal y espacial. ¿Cuales serian ambas complejidades?. Temporal O(n * m) y espacial O (min {n, m}). Temporal O(max {n, m}) y espacial O(max{n,m}). Temporal O(n * m) y espacial O(n * m).

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 en realidad no es un algoritmo voraz pues el criterio de seleccion no lo es. Que en realidad no es un algoritmo voraz pues las decisiones que se toman no deberian reconsiderarse. Que es un algoritmo voraz pero sin garantia de solucionar el problema.

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?. Nada de interes, puesto que el camino resultante no contemplaria todos los movimientos permitidos. Un nodo hoja del subarbol generado por aquel nodo. Una cota optimista para ese nodo.

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 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). 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 booleanos para descartar caminos que llegan a una casilla ya visitada. Cada casilla (i, j) de la matriz se inicializa con el valor false.

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 exploraria menos nodos de los necesarios. Que si comienza con una solucion suboptima encontraria antes la optima. Que presuntamente exploraria mas nodos de los necesarios.

Dada la version restringida del problema del laberinto, queremos obtener todos los caminos que llegan a la salida. ¿Cual de las siguientes tecnicas resultaria mas eficiente?. Programacion dinamica. Vuelta atras. Tanto programacion dinamica como vuelta atras resultaria equivalentes.

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 version general del problema del camino de coste minimo, ¿cual de las estrategias siguientes proveeria de una cota optimista para ramificacion y poda?. Suponer que solo nos vamos a mover en tres direcciones (Como en el caso restringido). Suponer que ya no se van a realizar mas movimientos. Las otras dos estrategias son ambas validas.

Queremos resolver el problema general del camino de coste mınimo. Supon que estamos usando una funcion f como cota optimista y funciona correctamente. ¿Que pasaria si, en el fuente, multiplicamos esta funcion por 1,1. Marca la falsa. Podria perderse la solucion optima pero la que obtendriamos no se alejara mucho de ella. El programa terminaria mas rapido. Seguiria funcionando bien pero seria mas lento.

Queremos resolver la version general del problema del camino de coste mınimo por ramificacion y poda. Para ello se usa una estrategia que consiste en priorizar las expansiones de los nodos que contienen un camino explorado de menor coste. ¿Que podemos decir del algoritmo resultante?. Que la primera hoja a la que se llegue es la solucion del problema y por lo tanto ya no sera necesario explorar mas nodos de la lista de nodos vivos, aunque no este vacıa. Que el recorrido en el arbol de busqueda sera equivalente a un recorrido por niveles, por lo que no es necesario utilizar una cola de prioridad. Las otras dos opciones son ambas ciertas.

En la solucion de ramificacion y poda del problema del camino de coste mınimo, ¿para que puede resultar util la tecnica de poda con memoria?. Para obtener cotas pesimistas. Para evitar la formacion de ciclos. Para ambas cosas.

Queremos resolver la versi´on general del problema del camino de coste mınimo mediante ramificacion y poda. Para obtener la cota optimista de un nodo cualquiera procedemos asi: calculamos el numero de casillas que quedan, por la diagonal derecha–abajo, hasta llegar a una pared del mapa. A ese valor le sumamos el numero de casillas que podrıan quedar desde esa pared hasta la salida utilizando unicamente movimientos del tipo abajo o derecha, segun corresponda (distancia de Chebishev). ¿Que podemos decir acerca de la cota optimista que se obtendrıa?. Que solo sera una cota optimista valida si se asegura que todas las casillas tengan un coste minimo de 1. Que solo sera una cota optimista valida si se asegura que todas las casillas tengan un coste minimo de 0. Que solo sera una cota optimista valida si las casillas contienen valores reales mayores que 0.0.

En la resolucion mediante ramificacion y poda del problema del camino de coste mınimo, obtenemos para un nodo determinado, una cota pesimista parcial estrictamente menor que su cota optimista. ¿Que quiere decir esto?. Que el nodo debe expandirse. Que el nodo no debe expandirse. Que hay un error en alguna de las dos cotas.

En la resolucion mediante ramificacion y poda del problema del camino de coste mınimo, obtenemos para un nodo determinado, una cota pesimista parcial estrictamente menor que su cota optimista. ¿Que quiere decir esto?. Solo una. Un valor que es O(2^n), donde n es el tamaño del mapa. Un valor que es O(n), donde n es el tamaño del mapa.

Sea el problema Camino de coste minimo con tres movimientos se pretende encontrar el camino mas favorable con la menor complejidad temporal posible. ¿Cual seria la mas ajustada para realizar todo el proceso?. O(n*m + n). O(n*m + m). O(n*m + n+m).

Sea el problema camino de coste minimo con tres movimientos. Utilizando la tecnica de memoizacion se pretende conocer la dificultad del camino mas favorable. ¿Cual es la mejor complejidad espacial y temporal que se puede conseguir. espacial O(n) y temporal O(n*m). O(n*m), tanto espacial como temporal. espacial O(n) y temporal(2^max(n, m)).

Sea el problema camino de coste minimo con tres movimientos. Utilizando un algoritmo voraz se pretende conocer la dificultad del camino mas favorable y para ello se va seleccionando una casilla escogida al azar de entre las tres posibles, hasta llegar al destino. ¿Que podemos decir de este algoritmo?. Que aun siendo voraz existen otros criterios de seleccion con mejores resultados a priori. Que no es voraz. Que es voraz puesto que las decisiones no se replantean.

Sea el problema camino de coste minimo con tres movimientos, en cuanto a la complejidad espacial y temporal, ¿cual de los siguientes esquemas algoritmicos resulta mas eficiente para resolverlo?. Programacion dinamica. Divide y venceras. Ramificacion y poda.

Sea el problema camino de coste minimo con tres movimientos, utilizando la tecnica de programacion dinamica iterativa se pretende conocer la dificultad del camino mas favorable ¿Cual es la mejor complejidad espacial y temporal que se puede conseguir?. O(n+m), tanto espacial como temporal. espacial O(n) y temporal O(n*m). espacial O(min(n,m)) y temporal O(n*m).

Si en el problema del camino de coste minimo, estudiado en practicas, permitieramos casillas con coste 0, ¿Cual de las siguientes distancias seria una cota optimista valida si le sumamos al coste del camino actual? (i, j) es la posicion actual y (n, m) el numero de filas y columnas, respectivamente, del mapa. max(n-1-i, m-1- j). (n-1-i)+(m-1-j). Ninguna de las anteriores.

Queremos resolver un problema parecido a la version restringida del problema del camino de coste minimo pero ahora permitirmos(además) movimientos de dos pasos en las mismas direcciones. ¿Como se podria resolver este problema?. Usando programacion dinamica, de una forma muy parecida al original. Ya no se podria resolver usando programacion dinamica y habria que recurrir a la vuelta atras. No se puede resolver ni usando programacion dinamica ni vuelta atras.

¿Cual de las siguientes tecniccas NO resuelve la version general del problema del camino de coste minimo?. Ramificacion y poda. Programacion dinamica. Vuelta atras.

En la resolucion mediane ramificacion y poda del problema del camino de coste minimo, ordenamos ascendentemente las casillas del mapa por coste. Dado un nodo parcial (o nodo incompleto), sumamos al coste del camino que llevamos hasta el momento, la suma de las k casillas con menor coste, siendo k = max(n-1-i,m-1-j). (i,j) es la posicion actual y (n,m) el numero de filas y columnas del mapa. El valor obtenido es. Una cota optimista. Una cota pesimista. Ninguna de las anteriores.

Dada una version general del problema mcp ¿Cual es la mejor complejidad temporal (de entre las indicadadas) con la que podria obtenerse una cota pesimista para el nodo inicial del arbol de busqueda?. Ω(n + m). Ω(nm). Ω(1).

Dada la version general del problema mcp, en cuanto al valor de una cota pesimista de un nodo cualquiera... de las siguientes afirmaciones, o bien dos son ciertas y una es falsa, o bien al contrario, una es cierta y dos son falsas. Marca la que en este sentido es diferente a las otras dos. ... debe corresponder con la dificultad de un camino completado, es decir, que comienza en (0,0) y termina en (n-1, m-1). ... debe ser inferior al de una cota optimista de cualquier otro nodo. ... debe ser superior al de una cota optimista de cualquier otro nodo.

Dada la version restringida del problema mcp, queremos listar todos los caminos posibles(sean o no los optimos).¿Que tecnica deberiamos utilizar?. Memoizacion. Divide y venceras. Programacion dinamica iterativa.

Queremos resolver la version restringida del problema del camino de coste minimo usando una tecnica de vuelta atras. Eso no se puede hacer, ese problema no se puede resolver usando vuelta atras. La tecnica de vuelta atras se podria aplicar, pero siempre seria mas lento que si usamos programacion dinamica. La tecnica de vuelta atras se podria aplicar, incluso en algunos raros casos podria ir mas rapido que usando programacion dinamica.

Dada la version general general del problema del camino de coste minimo, cual de las estrategias siguientes proveeria de una cota optimista para ramificacion y poda. Tomar la dificultad del camino parcial (hasta el nodo en cuestion) y sumarle la dificultad del camino que, desde el nodo en cuestion, se completa siguiendo un algoritmo voraz que solo toma los movimientos de la version restringida. Tomar la dificultad del camino parcial (hasta el nodo en cuestion) y nada mas. Las otras dos estrategias son ambas validas.

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.

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.

Dada la version restrringida del problema del laberinto, estamos interesados en obtener, para cada casilla accesible del laberinto, le camino mas corto entre el origen y esa casilla. ¿Que esquema es mas apropiado en este caso?. La version iterativa de programacion dinamica. Memoizacion. Ambas tecnicas resultan equivalentes.

Dada la version general del problema del laberinto ¿que ocurre si la cota optimista de un nodo resulta ser el valor que se obtinene de una solucion factible pero que no es la mejor en el subarbol generado por ese nodo?. Nada especial, las cotas optimistas se corresponden con soluciones factibles que no tienen por que ser las mejores. Que el algoritmo seria incorrecto pues podria descartarse el nodo que conduce a la solucion optima. Que el algoritmo seria mas lento pues se explorarian mas nodos de los necesarios.

Dada la versión restringida del problema del laberinto, ¿se podría modificar la solución nai-ve 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.

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). Ω(min(n,m), y O(mn). ∅(mn).

¿Cómo se utiliza la cola de prioridad en el algoritmo de ramificación y poda para resolver el problema del laberinto?. Se agregan los nodos a la cola de prioridad en orden aleatorio para explorar todas las posibilidades. Los nodos se agregan a la cola de prioridad según una estimación heurística para priorizar los caminos más prometedores. Los nodos se extraen de la cola de prioridad según se vayan obteniendo.

¿Cual es la condicion base para terminar la recursion en la implementacion por divide y venceras del problema restringido del laberinto?. Llegar al inicio del laberinto (fila 0 columna 0) o al final del laberinto (fila m - 1,columna n - 1), segun como se establezca la recursion. Llegar a una celda con valor 0 en el laberinto. Las otras dos opciones son ambas ciertas.

En la implementacion naive de la version restringida del problema del laberinto, en el caso de que las tres direcciones sean posibles ¿que hay que hacer con las longitudes de los caminos obtenidos con las llamadas recursivas?. Elegir la mas grande y sumarle uno. Elegir la mas pequeña y sumarle uno. Elegir la mas cercana y sumarle uno.

¿Que estructuras de datos utilizaste en la implementacion naive de la version restringida del problema del laberinto? (excluyendo el laberinto). Una cola de prioridad. Una matriz bidimensional. Ninguna de las otras dos opciones es cierta.

Queremos conocer el camino de mınima longitud en el problema restringido del laberinto usando un algoritmo de programacion dinamica con la tecnica de complejidad espacial mejorada (con dos vectores). ¿Como se puede obtener?. Ninguna de las otras dos opciones es valida. Recorriendo el primer vector, empezando por la casilla de salida y buscando los resultados de los subproblemas accesibles a partir de ella. Recorriendo el primer vector, empezando por la casilla de entrada y buscando los resultados de los subproblemas accesibles a partir de ella.

¿Que estrategia es mejor en los algoritmos voraces para resolver el problema restringido del laberinto?. Elegir siempre la direccion hacia la salida mas cercana que no este bloqueada. Elegir la direccion con menos obstaculos en cada paso. Elegir aleatoriamente una direccion en cada paso.

¿Que estrategia se sigue para realizar la exploracion del laberinto con la tecnica de vuelta atras?. Realizar una busqueda en profundidad siguiendo un orden predefinido de movimientos. Utilizar una busqueda en amplitud para explorar todas las posibles soluciones en paralelo. Realizar una busqueda heurıstica utilizando una funcion de evaluacion para guiarla exploracion hacia la solucion optima.

En la aplicacion al problema general del laberinto del algoritmo de ramificacion y poda utilizando una cola de prioridad, ¿que funcion cumple la cola de prioridad en el proceso de exploracion del laberinto?. Ordenar los caminos explorados en funcion de un criterio de evaluacion para seleccionar el siguiente camino a explorar. Almacenar todos los caminos explorados para su posterior analisis y comparacion. Realizar una busqueda en amplitud de todos los caminos posibles antes de tomar una decision.

Si estamos procesando la casilla (i, j) y la casilla de salida del laberinto es la (m,n), ¿cual de las siguientes opciones sera una buena cota pesimista al camino que queda por recorrer?. max(|m - i| , |n - j|). |m - i| + |m - j|. Ninguna de las otras dos opciones es cierta.

Se pretende resolver la version general del problema del laberinto mediante un algoritmo de busqueda y enumeracion. Para reducir los nodos visitados, utilizamos un almacen de resultados parciales obtenido mediante la tecnica de programacion dinamica iterativa aplicandola a la version restringida del mismo problema. El almacen se rellena hacia atras comenzando en la casilla de salida del laberinto. ¿de que poda se trata?. De una poda basada en la cota optimista. De una poda basada en la cota pesimista. Ninguna de las otras dos opciones es cierta.

Dada la version restringida del problema del laberinto, ¿se podrıa obtener el camino de salida de longitud mınima haciendo uso unicamente de la version naive de programacion dinamica sin ningun tipo de procesamiento posterior?. No, el camino solo puede obtenerse a traves del almacen de una version iterativa o con memoizacion, en un proceso posterior. Si, cada vez que se resuelve un subproblema hay que tomar el camino que corresponde a la mejor alternativa de las tres posibles y añadirle las coordenadas del subproblema que se esta resolviendo. Si, el mejor camino puede construirse de forma incremental, paso a paso, añadiendo la siguiente casilla a visitar que corresponde con la mejor alternativa de las tres posibles.

Para resolver la version general del problema del laberinto mediante vuelta atras, utilizamos el estimador que aparece en el listado. ¿Servirıa como cota optimista para cualquier nodo del arbol de busqueda? using Maze = vector<vector<bool>>; using Point = tuple<size_t, size_t>; size_t estimator(const Maze &maze, const Point &p) { return max(maze.size() - get<0>(p), maze[0].size() - get<1>(p)) - 1; }. No, puesto que no serıa una cota optimista valida para todos los nodos. Si, el estimador por si solo ya representaria una buena cota optimista. Sı, pero para mejorar la poda habrıa que sumarle la longitud del camino que representa cada nodo.

Se pretende resolver la version general del problema del laberinto. ¿Resultarıa util disponer de un almacen de resultados parciales obtenido mediante la tecnica de programacion dinamica iterativa aplicandola a la version restringida del mismo problema?. Las otras dos opciones son ambas ciertas. Probablemente sı, rellenando un almacen hacia delante desde la casilla de entrada al laberinto. Probablemente sı, rellenando un almacen hacia atras comenzando en la casilla de salida del laberinto.

Se pretende resolver la version general del problema del laberinto mediante un algoritmo de busqueda y enumeracion. Para reducir los nodos visitados, utilizamos una matriz de enteros donde se almacena la longitud del mejor camino encontrado hasta el momento que llega a cada casilla del laberinto. ¿de que poda se trata?. De una poda basada en la cota optimista. De una poda basada en la cota pesimista. Ninguna de las otras dos opciones es cierta.

Se pretende resolver la version general del problema del laberinto mediante un algoritmo de busqueda y enumeracion. Para agilizar la búsqueda, hemos pensado utilizar una matriz en la que cada casilla (i, j) se inicializa con la solucion de la version restringida del problema asumiendo que el origen del laberinto es (i, j). ¿Qué utilidad puede tener esta matriz?. Ninguna, en todo caso habría que inicializar cada casilla (i, j) con la solución de la versión restringida del problema asumiendo que el origen del laberinto es (0,0) y el destino (i, j). A priori poca, ya que cada vez que un nodo visita una casilla (i, j) habría que actualizar la matriz, lo que perjudicarıa la eficiencia del algoritmo resultante. Puede resultar eficaz para ajustar la mejor cota pesimista encontrada hasta el momento y ademas, no es imprescindible actualizar la matriz durante todo el proceso de búsqueda.

Con la tecnica de programacion dinamica aplicada a la version restringida del problema del laberinto... . . . no solo puede obtenerse el camino de salida mas corto, tambien puede obtenerse, sin incrementar la complejidad temporal, el camino mas corto desde el origen hasta cualquier casilla accesible del laberinto. ... puede obtenerse el camino m´as corto desde cualquier casilla accesible hasta la salida si es que existe. Las otras dos opciones son ambas ciertas.

Dada la version restringida del problema del laberinto, ¿se puede modificar la solucion de programacion dinamica con complejidad espacial reducida para obtener tambien un camino de salida de longitud mınima?. No. Sı, pero a costa de aumentar la complejidad espacial del almacén. Si, añadiendo un vector de movimientos.