SI - Parcial (Prácticas)

¿Qué representa un estado en un problema de búsqueda?. Una acción aplicable. La configuración de un problema. El coste acumulado desde el inicio. Un nodo del árbol de búsqueda.

La clase Estado obliga a redefinir un método que permite comparar dos objetos que representan el mismo estado. ¿Cuál?. toString. equals. hashCode. compareTo.

¿Para qué sirve que Estado implemente hashCode correctamente?. Sirve para encapsular el Estado y pasárselo a un problema. Sirve para usar estados tipo HashSet. Sirve para calcular el coste de las acciones. Sirve para generar el estado sucesor en hash.

¿Por qué es importante que los estados implementen equals y hashCode en búsqueda en grafo?. Para ordenar los nodos por prioridad. Para evitar repetir estados ya explorados. Para calcular corretamente la heurística. Para reconstruir el camino solución.

¿Qué debe poder hacer un Estado según la clase base?. Generar acciones aplicables. Indicar si es meta o no. Permitir comparaciones equals y hashCode. Devolver el estado inicial.

¿Qué representa una acción en el modelo de búsqueda?. Un estado del problema. El coste mínimo hasta la meta. Transformación permitida de un estado a otro. Un nodo ya expandido en la frontera.

aplicaA(). Genera un estado resultante de aplicar una acción. Genera un estado frontera (si existe). Devuelve un booleano de si se ha creado un estado o no. Construye un nuevo estado tras aplicar la acción.

¿Qué hace el método esAplicable(Estado es) de la clase Accion?. Construye el nuevo estado tras aplicar la acción. Comprueba precondiciones. Devuelve el coste de la acción. Comprueba todas las acciones aplicables del Estado.

getCoste(). Devuelve 0 por defecto. Devuelve 1 por defecto. Ayuda a saber el número de acciones aplicables. b) y c) son correcta.

¿Qué método de ProblemaBusqueda utiliza internamente aplicaA de Accion?. acciones(). esMeta(). getEstadoInicial(). result().

¿Qué define formalmente la clase ProblemaBusqueda?. Estado inicial. Si es meta. Las acciones aplicables y sus resultados. Todas son correctas.

¿Qué devuelve el método acciones(Estado es) de ProblemaBusqueda?. La lista de acciones aplicables al estado. El grafo de nodos posibles tras la accion. La lista de estados posibles tras la acción al estado. La lista de acciones predecesoras al estado.

¿Qué indica el método esMeta(Estado es)?. Si es solución al problema o no. Si es una función esmetable o no. Si el estado es predecesor a la meta. Ninguna de las opciones es correcta.

¿Qué hace result(Estado es, Accion acc) en ProblemaBusqueda?. Devuelve una acción aplicable. Devuelve un estado resultante. Devuelve un estado previo a la acción. Devuelve una lista de estados posibles tras la acción.

¿Quién proporciona el estado inicial en el modelo?. Accion. Estado. ProblemaBusqueda. Main.

En el modelo de búsqueda, ¿qué papel tiene la clase que extiende ProblemaBusqueda?. Definir el orden de exportación de acciones y estados. Definir los parámetros de inicio, restricciones y finalización de la solución. Almacenar los nodos de la frontera correctamente. Implementar los métodos necesarios para las comprobaciones de estados.

¿Cuál es la diferencia entre estado y nodo?. Son lo mismo. El nodo es el estado + información del camino. El estado es nodo + información del camino. Se puede calcular la heurística del nodo pero no del estado.

¿Qué información típicamente lleva un nodo en búsqueda (según teoría)?. El estado. El estado, el padre y la acción que llevó a este estado. El padre. La acción que llevó a este estado.

¿Qué representa g(n) en un nodo?. La estimación del coste restante hasta la meta. El coste acumulado. El valor f = g + h. El número de nodos en la frontera.

¿Qué representa f(n) en A*?. Heurística. Estimación del coste total. El número de sucesores. El coste de la última acción.

¿Qué significa expandir un nodo?. Eliminarlo de la frontera. Generar sucesores de un nodo fronterizo. Calcular la heurística de un nodo fronterizo. Generar sucesores de cualquier nodo.

¿Qué método exige el interfaz EstrategiaBusqueda?. soluciona(p). evalua(es). acciones(es). getEstadoInicial().

¿Qué recibe el método soluciona() en el interfaz EstrategiaBusquedaInformada que no recibe en EstrategiaBusqueda?. El estado inicial. La heurística. La lista de explorados. La frontera.

¿Qué tipo devuelve soluciona en EstrategiaBusquedaInformada según el interfaz de base?. Nodo[]. Acción[]. Estado. Acción.

¿Por qué puede fallar la Estrategia4?. Heurística parcial e incorrecta. No existe frontera. No usa nodos. No implementa el equals de Estado.

¿Qué es la frontera en búsqueda en grafo?. Los estados ya expandidos. Nodos descubiertos no expandidos. Nodos descubiertos ya expandidos. Los estados no expandidos.

¿Qué son los explorados?. Nodos pendientes a expandir. Nodos ya expandidos. Nodos con acciones disponibles. Nodos sin acciones disponibles.

¿Cuál es la diferencia principal entre Estrategia4 y búsqueda en grafo?. No hay, son técnicamente lo mismo. Grafo tiene frontera, Estrategia4 no. Estrategia4 tiene frontera, Grafo no. Estrategia4 usa un FIFO, Grafo usa un LIFO.

¿Qué estructura se recomienda para almacenar los estados explorados?. Cola. Pila. HashSet. Array.

¿Qué estructura de datos se utiliza típicamente en la búsqueda en profundidad (DFS)?. Cola FIFO. Prio Queue. Pila LIFO. Lista ordenada.

¿Qué estructura de datos se utiliza típicamente en la búsqueda en anchura (BFS)?. Cola FIFO. Prio Queue. Pila LIFO. Lista ordenada.

Qué política de extracción sigue la búsqueda en anchura?. Cola FIFO. Por valor f(n). Pila LIFO. Aleatorioa.

¿Qué política de extracción sigue la búsqueda en profundidad?. Cola FIFO. Por valor f(n). Pila LIFO. Aleatorioa.

¿Qué estrategia encuentra la solución más superficial (menos pasos) cuando los costes son uniformes?. DFS. BFS. A*. Estrategia4.

¿Cuál de estas estrategias suele consumir más memoria en muchos problemas?. DFS. BFS. Ambas igual. Ninguna usa memoria sino espacio.

En búsqueda en profundidad, ¿cómo se explora el espacio?. Por niveles (distancia 1, 2...). Por rama hasta acabarla antes de volver atrás. Siempre el nodo de menor f(). Aleatoriamente con quick sort.

¿Qué es una heurística en búsqueda?. Acción aplicable. Estado meta. Distancia restante hasta la meta. Coste real acumulado hasta el momento.

¿Qué método obliga a implementar la clase abstracta Heuristica?. esAplicable(). aplicaA(). evalua(es). esMeta().

¿Qué representa h(n)?. Estimación del coste restante desde el estado actual hasta la meta. Coste total acumulado desde el estado inicial hasta la meta. Coste total acumulado solamente de la rama solución hasta la meta. La heurística del coste acumulado desde el inicio.

¿Cuál es la condición de consistencia para una heurística?. h(n) = 0 para todo n. h(n) ≤ c(n,n') + h(n'). h(n) ≥ g(n). h(n) = g(n) + f(n).

¿Qué estrategia de las siguientes usa heurística?. BFS. DFS. A*. Ninguna.

¿Qué significa búsqueda informada?. No usa estados. No usa nodos. Usa heurística. Usa BFS o DFS.

¿Qué significa búsqueda no informada?. No usa estados. No usa nodos. No usa heurística. No usa BFS o DFS.

¿Qué valor se utiliza para ordenar los nodos en la frontera de A*?. h(n). f(n). f(n) = g(n) + h(n). g(n) = f(n) + h(n).

¿Qué estructura de datos se usa típicamente para la frontera en A*?. Pila. Cola. Prio queue. Array.

¿Por qué Nodo puede implementar Comparable en el contexto de A*?. Para comparar estados. Para permitir ordenar nodos por prioridad. Para calcular heurística. Para generar acciones disponibles a partir de un estado.

En A*, ¿qué es g(n)?. Heurística. Coste acumulado total. Coste acumulado desde un nodo hasta el final. Coste acumulado desde el nodo padre hasta el final.

¿Qué estrategia no explora por orden de llegada ni por profundidad, sino por prioridad f(n)?. BFS. DFS. A*. Estrategia4.

¿Cuál es la fórmula de la constante mágica (suma de cada fila/columna/diagonal)?. N². N(N²+1)/2. N+1. 2N.

¿Cuál es la constante mágica para N = 3?. 12. 15. 18. 9.

En el modelo del cuadrado mágico, ¿qué representa típicamente un 0 en la matriz?. Bloqueado. Vacío. Meta. Valor de heurística.

¿Cuándo es meta un estado del cuadrado mágico?. Cuando no hay celdas vacías. Cuando las sumas de columnas, filas y todas las diagonales siguen la constante mágica. Cuando las sumas de columnas, filas y las diagonales principales siguen la constante mágica. Cuando las sumas de columnas y filas siguen la constante mágica.

Qué mide el número de nodos creados?. El total de nodos generados durante la búsqueda. El total de nodos explorados durante la búsqueda, porque los no explorados no se guardan. El total de nodos de una rama hasta el final, pues es un BFS. El total de acciones ejecutadas sobre estados durante la búsqueda completa.

¿Qué mide el número de nodos expandidos?. El número de nodos de los que han generado sucesores. El número de nodos fronterizos. El número de nodos eliminados. El número de nodos no fronterizos.

¿Qué se considera la solución completa en el modelo de la práctica?. El nodo esMetA(). La lista de nodos desde el inicio al final. El nodo que cumple el valor de heurística admisible. El número de nodos explorados hasta el final.

¿Cuál es el objetivo de los algoritmos de búsqueda en esta práctica?. Minimizar el uso de memoria. Enseñar a calcular heurísticas admisibles. Encontrar un camino desde inicio a meta. Generar un grafo y ver su creación paso a paso.

¿Qué significa que dos estados sean iguales en el modelo?. Tienen misma heurística. Tienen misma configuración del problema. Tienen el mismo nodo padre. Tienen el mismo coste total.

¿Qué método de Estado se usa para comparar si dos estados representan la misma configuración?. hashCode. equals. toString. compareTo.