Algoritmos de Búsqueda: Conceptos Clave y Ejercicios Resueltos

Conceptos Clave y Ejercicios Resueltos sobre Algoritmos de Búsqueda

Ejercicio 1

Dado un problema de búsqueda en el que todos sus operadores tienen el mismo coste, indica cuál de las siguientes afirmaciones es correcta:

• A. Un algoritmo de búsqueda con una heurística admisible devolverá la solución más corta.
• B. Una estrategia en profundidad devolverá siempre la solución de menor coste.
• C. La estrategia en anchura devolverá la solución más corta pero no la solución de menor coste.
• D. La estrategia de coste uniforme devolverá la solución de menor coste pero no la solución más corta.

Ejercicio 2

Dados cuatro métodos de búsqueda: M1 aplica un algoritmo en anchura, M2 aplica un algoritmo de coste uniforme, M3 aplica un algoritmo A con una heurística admisible y M4 aplica un algoritmo A con una heurística no admisible, indica cuál es la respuesta incorrecta:

• A. M1, M2 y M3 garantizan que encontrarán la solución óptima independientemente del coste de las acciones.
• B. M2 y M3 garantizan que encontrarán la solución óptima independientemente del coste de las acciones.
• C. M3 expandirá menos nodos que M2.
• D. M4 podría encontrar la solución óptima.

Ejercicio 3

La figura muestra un tablero donde R es un robot cuyo objetivo es desplazarse a la posición donde se encuentra el objeto O1 y luego desplazarse a la posición del objeto O2. El robot solo puede moverse horizontal o verticalmente. La figura muestra una instancia concreta de este problema, pudiendo estar R, O1 y O2 en cualquiera de las casillas del tablero. Sea n un nodo de un árbol de búsqueda que representa una situación particular de R, O1 y O2, y manh(x,y) la distancia de Manhattan entre x e y, donde x, y ∈ {R,O1,O2}. Indica la afirmación que es correcta:

• A. h(n)=manh(R,O1)+manh(R,O2) es una heurística admisible para este problema.
• B. h(n)=manh(R,O1)+ manh(O1,O2) es una heurística admisible para este problema.
• C. h(n)=manh(R,O1)*2 es una heurística admisible para este problema.
• D. No se puede definir una heurística admisible para este problema.

Ejercicio 4

Para el espacio de estados de la figura y dada una búsqueda de tipo A (f(n)=g(n)+h(n)) ¿cuántos nodos es necesario generar para encontrar la solución?

• A. 6
• B. 8
• C. 10
• D. 12

Ejercicio 5

Para el espacio de estados de la pregunta 4, indica cuál es la afirmación correcta:

• A. La aplicación de un algoritmo de tipo A devuelve la solución óptima.
• B. La función h(n) es consistente (monótona).
• C. Una estrategia de coste uniforme devolverá la misma solución que un algoritmo de tipo A.
• D. Ninguna de las anteriores.

Ejercicio 6

Dado el espacio de búsqueda de un juego que se muestra en la figura, ¿qué valor tendría que tener el nodo terminal señalado en negrita?

• A. [-∞, 1]
• B. 1
• C. [2, +∞]
• D. No se puede determinar con los datos disponibles.

Ejercicio 7

Dado un SBR, con una única regla:

(defrule regla-1
?f <- (lista $?y)
(retract ?f)
(assert (lista $?y))
)

y la BH inicial {(lista a b c b c b c b c b a b c b c b c b c b a)}, ¿cuál será el estado final de la Base de Hechos?

Nota: No se proporciona una respuesta explícita a este ejercicio en el texto original, ya que requiere una ejecución del sistema basado en reglas para determinar el estado final de la base de hechos. Sin embargo, se puede inferir que la regla elimina el hecho coincidente y lo vuelve a insertar, por lo que, en este caso particular, la base de hechos final sería igual a la inicial.