Sdsfsefefzdfe

Inteligencia Artificial

2012 - 2013

Relaci´n 1 - B´ squeda en espacios de estados
o
u
Cuestiones
Cuesti´n 1. Enuncia la principal diferencia entre Inteligencia Artificial fuerte e Intelio
gencia Artificial d´bil.
e
Cuesti´n 2. Calcular cu´ntos nodos se exploran (contando las repeticiones) en el algoo
a
ritmo de profundidad iterativa en un problema de b´squeda donde el n´mero desucesores
u
u
de cualquier nodo es b y la soluci´n se alcanza en el ultimo nodo a profundidad n.
o
´
Cuesti´n 3. Dar un ejemplo de problema de espacios de estados en el que la soluci´n
o
o
m´s corta est´ a profundidad p, pero que la b´squeda en profundidad acotada con cota p
a
e
u
no encuentre la soluci´n.
o
Cuesti´n 4. Dar un ejemplo de problema de espacios de estados en los cualesaplicando
o
el algoritmos de primero el mejor con una heur´
ıstica admisible no se obtenga soluci´n
o
o
´ptima.
Cuesti´n 5. Supongamos que, para resolver un problema de espacio de estados, dos
o
alumnos deciden representar de la misma manera los estados y los operadores, y definen
de la misma manera el estado inicial y las funciones es estado final y aplica. Sin
embargo, aplicando elprocedimiento de b´squeda en profundidad obtienen soluciones
u
distintas ¿Por qu´ puede ocurrir esto?
e
Cuesti´n 6. ¿Son ciertas las siguientes afirmaciones? (justificar la respuesta):
o
La lista de ABIERTOS usada en los procedimientos de b´squeda contiene en cada
u
momento todas las hojas del arbol de b´squeda actual.
´
u
Las listas de ABIERTOS y CERRADOS no tienen nodos en com´n.
u
Cuesti´n7. Explicar en qu´ consiste (y para qu´ se usa) la t´cnica de “relajaci´n de
o
e
e
e
o
un problema de espacio de estados”.
Cuesti´n 8. Dar una ventaja de la b´squeda en profundidad frente a la b´squeda en
o
u
u
anchura, y viceversa.
Cuesti´n 9. Sea h una heur´
o
ıstica admisible para un problema planteado como espacio
de estados y k > 0 un n´mero real ¿Qu´ efecto tiene usar en elalgoritmo de b´squeda por
u
e
u
primero el mejor, en lugar de h, la heur´
ıstica que a cada estado e le asigna valor k · h(e)?
∗
¿Y en el algoritmo A ? ¿Var´ las respuestas anteriores si sabemos que k < 1?
ıan
Cuesti´n 10. Dadas dos funciones heur´
o
ısticas distintas ¿es cierto que siempre una de
ellas est´ m´s informada que la otra?
aa
Cuesti´n 11. Dado un problema de espacio deestados, supongamos que definimos una
o
heur´
ıstica h que a cada estado le asigna el coste del camino encontrado por una b´squeda
u
o
´ptima que tiene a dicho estado como estado inicial ¿Es h una heur´
ıstica admisible?
¿Qu´ inconvenientes presenta el uso de dicha heur´
e
ıstica desde el punto de vista pr´ctico?
a

1

Cuesti´n 12. Especificar, razonando la respuesta, un problema deespacio de estados en
o
el que la lista de cerrados en los algoritmos de b´squeda en anchura y en profundidad
u
sea superflua.
Cuesti´n 13. Consid´rese una modificaci´n del algoritmo A∗ en el que en lugar de usar
o
e
o
f (n) = g (n) + h(n) para ordenar la cola de abiertos se usa f ′ (n) = (1 − w) · g (n) + w · h(n),
siendo w un n´mero real constante, 0 ≤ w ≤ 1
u
(a) ¿Qu´ algoritmo deb´squeda estar´
e
u
ıamos aplicando si tomamos w = 0? ¿Y w = 0, 5?
¿Y w = 1?
(b) Demostrar que si h es admisible y w ≤ 0, 5 entonces se obtiene soluci´n ´ptima si
oo
′
ordenamos la lista ABIERTOS usando f .
(c) Dar un ejemplo de problema de espacio de estados, una heur´
ıstica admisible y un
valor w > 0, 5 tal que al ordenar por f ′ no se obtenga soluci´n ´ptima.
oo
Cuesti´n 14. Consid´renseun par de heur´
o
e
ısticas h1 y h2 , ambas admisibles para un
problema representado como espacio de estados. Supuesto que estamos interesados en
encontrar una soluci´n de coste m´
o
ınimo en el menor tiempo posible, ¿qu´ heur´
e
ıstica de
las siguientes es la mejor para ser usada junto con el algoritmo A∗ ? (justificar la elecci´n):
o
• h1 .
• h2 .
• h3 , definida por h3 (e) =...