¿Qué estrategia devuelve la solución más corta cuando todos los operadores tienen el mismo coste?

La estrategia en anchura devuelve la solución más corta. Como todos los operadores cuestan lo mismo, la solución más corta coincide con la de menor coste.

¿Qué es una heurística admisible?

Es una heurística que nunca sobrestima el coste real para alcanzar el objetivo. Con ella, el algoritmo A garantiza encontrar la solución óptima.

Algoritmos de búsqueda: conceptos clave y ejercicios resueltos

Resumen

Este documento recoge ejercicios sobre algoritmos de búsqueda en inteligencia artificial. Plantea preguntas sobre estrategias en anchura, profundidad y coste uniforme, sobre heurísticas admisibles y el algoritmo A, sobre búsqueda en juegos con valores minimax y sobre la ejecución de un sistema basado en reglas. El estudiante podrá practicar la identificación de soluciones óptimas y la evaluación de heurísticas.

Puntos clave

En problemas con operadores de igual coste, la búsqueda en anchura devuelve la solución más corta.
La búsqueda de coste uniforme devuelve la solución de menor coste.
Una heurística admisible nunca sobrestima el coste real hasta la meta y garantiza la solución óptima con el algoritmo A.
La distancia de Manhattan se calcula como la suma de las diferencias absolutas de las coordenadas.
El algoritmo A usa f(n)=g(n)+h(n) para ordenar los nodos a expandir.
En juegos, el valor de un nodo terminal determina la decisión de los jugadores en el árbol de búsqueda.

Ponte a prueba

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.