¿Cuál es la característica principal de la búsqueda heurística? Explorar todo el espacio de estados Explorar solo un camino del espacio de estados Asociar costes numéricos a los operadores Utilizar conocimiento del dominio para dirigir la búsqueda hacia las zonas más prometedoras.
Una predicción heurística es Siempre cierta Siempre falsa Generalmente no cierta, pero preferiblemente cercana a la realidad No se puede determinar si es cierta o falsa.
La búsqueda "primero mejor", que es una especialización del algoritmo general de búsqueda de grafos, posee como característica principal El uso de una función de evaluación de los nodos, cuyos valores numéricos indican cuan prometedores son No usa ningún tipo de función numérica, si no metarreglas No usa ningún tipo de función numérica, sino árboles El uso de una función de evaluación de los nodos, cuyos valores numéricos indican cuántas veces han sido visitados.
En el contexto del algoritmo A*, siendo n un nodo del espacio de estados, g*(n) representa: Una estimación positiva del coste del camino más corto desde n a una meta El coste del camino más corto desde el nodo inicial hasta n obtenido hasta el momento en el proceso de búsqueda El coste del camino más corto desde el nodo inicial hasta n El coste del camino más corto desde n a una meta.
En el contexto del algoritmo A*, siendo n un nodo del espacio de estados, g(n) representa El coste del camino más corto desde n a una meta El coste del camino más corto desde el nodo inicial hasta n Una estimación positiva del coste del camino más corto desde n a una meta El coste del camino más corto desde el nodo inicial hasta n obtenido hasta el momento en el proceso de búsqueda.
En el contexto del algoritmo A*, siendo n un nodo del espacio de estados, h*(n) representa El coste del camino más corto desde n a una meta El coste del camino más corto desde el nodo inicial hasta n obtenido hasta el momento en el proceso de búsqueda El coste del camino más corto desde el nodo inicial hasta n Una estimación positiva del coste del camino más corto desde n a una meta.
En el contexto del algoritmo A*, siendo n un nodo del espacio de búsqueda, h(n) representa Una estimación positiva del coste del camino más corto desde n a una meta El coste del camino más corto desde el nodo inicial hasta n El coste del camino más corto desde el nodo inicial hasta n obtenido hasta el momento en el proceso de búsqueda El coste del camino más corto desde n a una meta.
En el contexto del algoritmo A*, siendo n un nodo del espacio de estados, f*(n) = g*(n) + h*(h) representa Una estimación del coste del camino más corto del espacio de estados que abarque desde el nodo inicial a una meta El coste del camino más corto que pase por n y abarque desde el nodo inicial a una meta Una estimación del coste del camino más corto que pase por n y abarque desde el nodo inicial a una meta.
En el contexto del algoritmo A*, siendo n un nodo del espacio de búsqueda, f(n)=g(n)+h(n) representa Una estimación del coste del camino más corto del espacio de estados que abarque desde el nodo inicial a una meta El coste del camino más corto que pase por n y abarque desde el nodo inicial a una meta Una estimación del coste del camino más corto que pase por n y abarque desde el nodo inicial a una meta El coste del camino más corto del espacio de estados que abarque desde el nodo inicial a una meta.
El algoritmo A* ordena los nodos de ABIERTA en orden creciente de h(n g(n) g*(n)+h(n) g(n)+h(n).
¿Qué relación existe entre g(n) y g*(n)? g(n) <= g*(n) g(n) >= g*(n) g(n) < g*(n) g(n) > g*(n).
En general, ¿qué relación existe entre h(n) y h*(n)? Las dos son funciones positivas que devuelven valores mayores o iguales que cero h(n) >= h*(n) h(n) <= h*(n) h(n) = h*(n).
En el algoritmo A*, ¿cómo cambian los valores de g(n) y h(n) a lo largo del proceso de búsqueda? g(n) y h(n) son estáticos g(n) es estático y h(n) es dinámico g(n) es dinámico y h(n) es estático g(n) y h(n) son dinámicos.
Considere grafos localmente finitos, es decir, aquellos en que cada nodo tiene un número finito de sucesores (o hijos). ¿Son completas la búsqueda primero mejor y el algoritmo A* en este tipo de grafos? La búsqueda primero mejor es completa si el grafo es infinito, mientras que A* es completo siempre La búsqueda primero el mejor es completa siempre, mientras que A* es completo si el grafo es infinito La búsqueda primero mejor es completa si el grafo es finito, mientras que el algoritmo A* es completo siempre La búsqueda primero el mejor es completa siempre, mientras que el algoritmo A* es completo si el grafo es finito.
Una función heurística es admisible si h(n) > h*(n) para todo n h(n) = h*(n) para todo n h(n) < h*(n) para todo n h(n) <= h(*n) para todo n.
Siendo h admisible y C* el coste de la solución óptima, antes de que el algoritmo A* termine: No existe ningún nodo n' en ABIERTA tal que f(n') <= C* No existe ningún nodo n' en ABIERTA tal que f(n') < C Existe un nodo n' en ABIERTA tal que f(n') < C* Existe un nodo n' en ABIERTA tal que f(n') <= C*.
Si h es admisible, A* encuentra la solución óptima Solo si todos los arcos tienen igual coste Siempre Solo si h(n) es constante y no varía con n Nunca.
Una heurística h2 está "más informada" que otra heurística "h1" si: La dos son admisibles y h2(n) > h1(n) para todo nodo n que no sea meta Las dos son admisibles y h2(n) >= h1(n) para todo nodo n que no sea meta Las dos son admisibles y h2(n) < h1(n) para todo nodo n que no sea meta Las dos son admisibles y h2(n) <= h1(n) para todo nodo n que no sea meta.
Considere una heurística h2 que está más informada que otra heurística h1. ¿Qué relación existe entre los nodos que expande con A* con h1 y los que expande A* con h2? Expanden los mismos nodos Todo nodo expandido con h2 será expandido con h1 No expanden ningún nodo común Todo nodo expandido con h1 será expandido con h2.
Un heurístico h es monótono si Para todo par de nodos n y n' se cumple que h(n) <= k(n,n') + h(n'), donde k(n,n') es el coste mínimo para ir de n a n' Para todo par de nodos n y n' se cumple que h(n') <= k(n,n') + h(n'), donde k(n,n') es el coste mínimo para ir de n a n' Para todo par de nodos n y n' se cumple que h(n) < k(n,n') + h(n'), donde k(n,n') es el coste mínimo para ir de n a n' Para todo par de nodos n y n' se cumple que h(n') <= k(n,n') + h(n'), donde k(n,n') es el coste mínimo para ir de n a n'.
¿Es monótono el heurístico h(n) = h*(n) No Si Depende del problema Depende de si el espacio es un árbol o un grafo.
¿Es monótono el heurístico h(n) = 0? No Si Depende del problema particular considerado Depende de si el espacio de estados tiene forma de árbol o de grafo.
¿Es admisible todo heurístico monótono? Sí No Depende de si el espacio de estados tiene forma de árbol o de grafo Depende del problema particular considerado.
Si h es monótono en el contexto del algoritmo A*, ¿en qué casos no es necesario rectificar el mejor camino hallado hasta el momento entre el nodo inicial y un nodo n? Cuando n ya ha sido expandido Cuando n está en ABIERTA Cuando n está en TABLA_A Cuando n es un nodo meta.
En el problema del 8-puzzle considere las dos heurísticas siguientes:
h1(n): número de fichas que en el estado n están fuera de su posición en el estado meta
h2(n): suma de las distancias ortogonales de cada ficha a su posición en el estado meta
¿Son admisibles estos dos heurísticos? H1 si, h2, no Ambos lo son Ninguno lo es H2 sí, h1 no.
El método de "ponderación dinámica" proporciona un peso dinámico "h" de manera que: Se reduce el peso de h a lo largo del proceso de búsqueda Se incrementa el peso de h a lo largo del proceso de búsqueda Se varia el peso de h aleatoriamente Se varia el peso de h de forma sinusoidal.
¿Qué estructura de datos usa el algoritmo A* para almacenar los nodos generados pero no expandidos? Una lista denominada FOCAL Una lista denominada ABIERTA Una lista denominada ABIERTA y una sublista denominada FOCAL Una lista denominada FOCAL y una sublista denominada ABIERTA.
¿Qué tipo de búsqueda realiza el algoritmo IDA* en cada ciclo? Búsqueda en anchura iterativo Búsqueda en profundidad Búsqueda de coste uniforme A*.
¿Qué parámetro adicional es necesario utilizar (y actualizar en cada ciclo) en el algoritmo IDA*? La anchura límite de la búsqueda en anchura iterativa La profundidad límite de la búsqueda en profundidad No es necesario utilizar ningún parámetro adicional, por realizarse una búsqueda de coste uniforme en cada ciclo El tamaño máximo de ABIERTA utilizada por el algoritmo A* en cada ciclo.
¿Qué restricción emplea el algoritmo SMA*? El número de expansiones de nodos que realizan es limitado No emplea ninguna restricción particular El número de nodos que se exploran es limitado El espacio de TABLA_A es limitado.
¿Qué acción particular toma el algoritmo SMA* que no toma el algoritmo A*? Elimina el nodo menos prometedor de ABIERTA y TABLA_A cuando no queda espacio en TABLA_A Da por terminado el algoritmo cuando se ha alcanzado un número determinado de expansiones de nodos Da por terminado el algoritmo cuando se ha explorado un número determinado de nodos No toma ninguna acción particular con respecto a A*.
¿Cuales son las características de un algoritmo voraz? Considera alternativas en el proceso de búsqueda, no es completo, no es admisible y es muy eficiente Toma decisiones irrevocables, no es completo, no es admisible y es muy eficiente Toma decisiones irrevocables, es completo, es admisible y muy eficiente Toma decisiones, no es completo, no es admisible y es poco eficiente.
En el algoritmo de ramificación y poda, un estado representa Un subconjunto de soluciones del problema original Una solución del problema original No es necesario definir estados en este algoritmo Una redefinición del problema original.
En el algoritmo de ramificación y poda, el espacio de estados tiene forma de Árbol Grafo Solo existe un único estado Este método no utiliza un espacio de estados.
En el algoritmo de ramificación y poda, ramificar un estado significa Dividir en subconjuntos el conjunto de soluciones al problema original representados por el estado Hallar todos los caminos que parten del estado y llevan a alguna meta Hallar todos los descendientes del estado Hallar las soluciones asociadas al estado.
En el algoritmo de ramificación y poda, un nodo hoja representa Un subconjunto de las soluciones del problema original Una solución del problema original No existen nodos hoja en este algoritmo Una redefinición del problema original.
En el algoritmo de ramificación y poda, una cota inferior asociada a un estado (o nodo) representa Una cota inferior de los costes de operadores que parten de dicho estado Una cota inferior del valor asociado a la mejor solución contenida en el estado Una cota inferior de los costes de los operadores que conducen a dicho estado No existen tales cotas inferiores en este algoritmo.
En el algoritmo de ramificación y poda, una cota superior representa Una cota superior del valor asociado a la solución óptima al problema original Este algoritmo no maneja "cotas superiores" Una cota superior de los costes de los operadores El valor de la mejor solución real encontrada hasta el momento en los nodos hoja.
En el algoritmo de ramificación y poda, se produce una poda cuando Se ha ramificado, o expandido, cualquier nodo Tras ramificar un nodo, uno de sus sucesores tiene una cota inferior que sea mayor o igual que la cota superior actual La memoria disponible se ha agotado No existen podas en este algoritmo.
En un método de búsqueda local, el resultado de interés es El camino desde el nodo inicial hasta el nodo meta El nodo meta y no el camino para llegar al mismo desde el nodo inicial Los nodos desechados La regla de vecindad.
La búsqueda del gradiente acepta una solución vecina si Es mejor que la actual Es mejor o igual de buena que la actual Es igual de buena que la actual Este método no tiene en cuenta las soluciones vecinas de la actual.
La búsqueda del gradiente tiene como principal problema Que generalmente necesita demasiado tiempo de ejecución Que queda estancado en óptimos locales Que generalmente necesita demasiada memoria Que es muy complejo de implementar.
¿Cuál es la principal diferencia entre el método del temple simulado y el método del gradiente? Que el primero realiza decisiones de exploración revocables, mientras que el segundo no Que el primero puede no "saltar" a un nodo vecino mejor que el nodo actual, mientras que el segundo siempre salta en dicho caso Que el primero usa mucha más memoria que el segundo Que el primero puede "saltar" con cierta probabilidad a nodos vecinos peores que el nodo actual mientras que el segundo nunca salta en dicho caso.
El método del temple simulado es prácticamente equivalente al método del gradiente Al principio del proceso de búsqueda, cuando la temperatura aún no ha disminuido lo suficiente Nunca se suele considerar que sean equivalentes Al final del proceso de búsqueda, cuando la temperatura ha disminuido lo suficiente Cuando el estado actual se corresponde con un óptimo local.
La característica principal de la búsqueda tabú es El disponer de un mecanismo de memoria, por ejemplo, sobre el historial reciente de la búsqueda El ser una simplificación de la búsqueda del gradiente El ser una generalización del algoritmo A* El basarse en la búsqueda de coste uniforme.
|
