Bootcamp Inteligencia Artificial
Nivel Explorador
Semana 8: Principios de la inteligencia artificial (IA)
Algoritmos de búsqueda Formulación de un problema de
búsqueda Búsqueda no informada: DFS, BFS y UCS
Agenda
1. Problemas de Búsqueda.
2. Representación de estados
3. Búsqueda en Amplitud
4. Búsqueda en Profundidad
5. Búsqueda de Costo Uniforme
1.1 Problemas de Búsqueda
Buscar la Ejecutar la
Formular el
Entradas problema
secuencia de secuencia de Salidas
acciones acciones
1.2 Problemas de Búsqueda
Podemos especificar formalmente un problema de búsqueda definiendo los siguientes
aspectos:
• Espacio de estados: conjunto de estados alcanzables desde el estado inicial a partir de una
secuencia de acciones
• Un estado inicial: so es el estado donde inicia el agente.
• Acciones por estado: A(s), dado un estado s se debe conocer que acciones podría realizar el
agente en el dicho estado.
• Modelo de transición: result s, a , especifica cuál es el estado resultante de aplicar la acción a
en un estado s
• Función de evaluación: Goal(s), determina si el estado actual es el estado objetivo
• Función de costo: c s, a, s ′ , función que asigna a cada acción un valor numérico
1.3 Problemas de Búsqueda • Estados
• S=
{Ciudades en el mapa}
• Estado inicial
• so = Arad
• Acciones:
• Moverme a las ciudades
adyacentes
• Modelo de transición
• Alcanzar una ciudad
adyacente
• Función de evaluación:
• s = Bucharest?
• Función de costo
• Distancia entre s y s′
• ¿Solución?
1.4 Problemas de Búsqueda
A B • Estados
• Combinan la posición del agente
y la posición de la suciedad
• Estado inicial
• so = ?
• Acciones:
• Derecha, Izquierda, Aspirar
• Modelo de transición
• Ver imagen
• Función de evaluación:
• s =¿Todos los cuadros están
limpios?
• Función de costo
• 1 por cada movimiento
Espacio de estados
• ¿Solución?
1.5 Problemas de Búsqueda
• En el caso de Pacman:
• Espacio de estados: S
• Estado inicial: s0
• Acciones en cada estado N
• Modelo de transición E
• Función de evaluación
• s = tiene puntos de comida?
• Función de costo
• +1 por movimiento; -10 comida; -500 ganar; +500 morir; -200 comer fantasma
1.6 Problemas de Búsqueda
• Estados: posición de las fichas en el tablero (cada ficha se identifica por su número)
• Acciones: Mover el espacio vacío (Arriba, Abajo, Izquierda, Derecha)
• Función de evaluación: ¿El estado actual es igual al deseado?
• Función de costo: 1 por movimiento
9!
• Espacio de estados: alcanzables desde un estado inicial
2
1.7 Problemas de Búsqueda
El mundo real es absurdamente complejo. Para
formular el problema debemos realizar una
abstracción.
• Un estado representa una simplificación de
un fenómeno real
• Se deben eliminar los detalles innecesarios
(tipo de música, color del vehículo,
población de las ciudades, etc.)
• La acciones también deben pasar por un
proceso de abstracción.
2.1 Representación de estados
• Grafo del espacio de estados: representación
matemática de un problema de búsqueda a G
• Nodos: representaciones (abstractas) de la b c
configuración del mundo e
• Arcos: representan transiciones asociadas a las d f
acciones S h
• Cada estado ocurre una sola vez p r
q
• Generalmente es imposible representarlo en memoria
(demasiado grande), sin embargo, es una idea útil
2.2 Representación de estados
E E E
S S
N N
N
E E
W
S
N N N
E N S
W
N E
E
E E
W W
2.3 Representación de estados
Grafo del Árbol de búsqueda
espacio de estados Cada nodo en el
S
árbol representa una
a G ruta desde so e p
d
b c
b c e h r q
e El árbol se genera
d f a a h r p q f
S h cuándo sea
p r necesario, y se p q f q c G
q
construye tan q c a
G
pequeño como sea
posible a
2.3 Arboles de búsqueda
Considere el siguiente grafo: ¿Qué tan grande es el árbol de búsqueda
comenzado en el estado s?
a
S G
b
2.4 Arboles de búsqueda
Considere el siguiente grafo: ¿Qué tan grande es el árbol de búsqueda
comenzado en el estado s?
a s
a b
S G
b G a G
b a G b G
… …
¡Los estados que visitamos en el pasado son relevantes!
2.5 Arboles de búsqueda
Nodos
De forma sistemática podemos ver el proceso
de la siguiente forma: Frontera
• Los nodos frontera separan los nodos
inexplorados de los nodos expandidos Inexplorado Expandidos
• Expandir un nodo:
• Lo mueve del conjunto de frontera a los
expandidos
• Agrega nodos inexplorados a los nodos
frontera 𝐴𝑙𝑐𝑎𝑛𝑧𝑎𝑏𝑙𝑒𝑠 = {𝐸𝑥𝑝𝑎𝑛𝑑𝑖𝑑𝑜𝑠 ∪ 𝑓𝑟𝑜𝑛𝑡𝑒𝑟𝑎}
Arad
2.5 Arboles de búsqueda Sibiu Timisoara Zerind
Arad Fagaras Oradea Rimnicu VilceaArad Arad Lugoj Arad Oradea
Sibiu Timisoara Zerind
Arad
Arad
Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea
Sibiu Timisoara Zerind Sibiu Timisoara Zerind
Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea Arad Fagaras Oradea Rimnicu VilceaArad Arad Lugoj Arad Oradea
Sibiu Timisoara Zerind
Arad
Arad
Sibiu Timisoara Zerind Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea
Sibiu Timisoara Zerind
Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea
Arad Fagaras Oradea Rimnicu VilceaArad Arad Lugoj Arad Oradea
Arad Sibiu Timisoara Zerind
Sibiu Timisoara Zerind
Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea
2.6 Búsqueda en grafos
• ¿Cuál criterio utilizamos para seleccionar un nodo de la frontera?
• ¿Cuáles estructuras de datos podemos utilizar para modelar este proceso?
2.7 Búsqueda en grafos
• Una estrategia de búsqueda se define como la forma de seleccionar un nodo de la frontera
para ser expandido.
• Una estrategia de búsqueda se puede evaluar a través de las siguientes dimensiones:
▪ Completitud: ¿Si la solución existe, la estrategia la encuentra?
▪ Complejidad en el tiempo: Número de nodos generados/expandidos
▪ Complejidad en el espacio: Cantidad máxima de nodos en memoria
▪ Optimalidad: ¿Siempre se encuentra la solución con el menor costo?
2.7 Búsqueda en grafos
• ¿Complejidad en el tiempo?
• ¿Complejidad en el espacio? b
1 nodo
… b nodos
• En nuestro diagrama: b2 nodos
• b es el factor de ramificación m niveles
• m máxima profundidad del árbol
• , solución
bm nodos
• Número total de nodos en el árbol:
1 + b + b2 + …. bm = O(bm)
3.1 BFS (Búsqueda en Amplitud)
Estrategia: expandir el nodo
menos profundo primero
S
Implementación: la frontera se
representa mediante una cola d e p
(FIFO) Niveles
b c e h r q
búsqueda
a G a a p q f
b c
c G
e
d f
S a
h
p q r
Nota: para este ejemplo los empates se resolverán según el orden alfabético
3.2 BFS (Búsqueda en Amplitud)
• ¿Qué nodos expande BFS?
• Procesa todos los nodos por encima de la solución más
superficial 1 nodo
• Supongamos que la solución menos profunda está en el nivel s b
… b nodos
• Si m es finito, expandirá O(bs) nodos Nivel s
b2 nodos
• ¿Cuánta memoria se necesita para almacenar la frontera?
• Aproximadamente necesitará almacenar la cantidad de nodos
del último del nivel explorado. Por lo tanto, O(bs)
• BFS es completo?
• s debe ser finito para que la solución exista. Luego, es una
estrategia completa
• BFS es óptimo?
• Si todos los costos son iguales (e.g. 1)
3.3 BFS (Búsqueda en Amplitud)
3.4 BFS (Búsqueda en Amplitud). Ejercicio
• Encuentre la solución para el siguiente problema
de búsqueda utilizando BFS
• Suponga que los empates se rompen
alfabéticamente
• S → X → A será expandido antes S → X → B
• S → A → Z será expandido antes S → B → A
• Para cada caso encuentre la solución y la
secuencia de nodos expandidos
4.1 Búsqueda en profundidad
Estrategia: expandir el nodo
más profundo primero
S
Implementación: la frontera se
representa mediante una Pila d e p
(LIFO)
b c e
a G a a h r
b c
e p q f
d f
S h q c G
p q r
Nota: para este ejemplo los empates se resolverán según el orden alfabético
4.2 Búsqueda en profundidad
4.3 Búsqueda en profundidad
• ¿Qué nodo expande DFS?
• Proceso todos los nodos a la izquierda de la solución hasta el nivel m
• ¡Podría procesar todo el árbol! 1 nodo
• Si m es finito, expandirá O(bm) nodos b
… b nodos
• ¿Cuánta memoria se necesita para almacenar la frontera? b2 nodos
Nivel m
• Solo almacenará los nodos vecinos en el camino a la raíz. Por lo
tanto, O(bm)
• DFS es completo?
• m podría ser infinito.
• Prevenir ciclos podría ayudar bm nodos
• DFS es óptimo?
• No. Encuentra la solución más a la izquierda sin contemplar
profundidad o costo.
4.4 Búsqueda en profundidad
¿Qué estrategia podríamos utilizar para solucionar el problema
de un espacio de estados infinito para DFS?
4.5 Búsqueda en profundidad
• Se establece un límite en la profundidad l que podemos explorar en el árbol
• Los nodos en el nivel l son tratados como si no tuvieran hijos.
• Agrega otra fuente de incompletitud. Supongamos que d es la profundidad de la solución
más superficial.
• Si elegimos un valor de l < d no habrá solución
• Aún si elegimos l > d, la complejidad en el tiempo será O(bl) y la complejidad en el
espacio será O bl
• En muchos casos la utilización de este método depende del conocimiento del
problema a solucionar
4.6 Búsqueda en profundidad
4.5 Búsqueda en profundidad. Ejercicio
• Encuentre la solución para el siguiente problema
de búsqueda utilizando DFS
• Suponga que los empates se rompen
alfabéticamente
• S → X → A será expandido antes S → X → B
• S → A → Z será expandido antes S → B → A
• Para cada caso encuentre la solución y la
secuencia de nodos expandidos
5.1 Búsqueda de Costo Uniforme
g(n) = costo de la raíz a n S 0
Estrategia: expandir el nodo con el d 3 e 9 p 1
menor valor de g(n)
b 4 c 11 e 5 q 16
La frontera es una cola de
prioridad ordenada según g(n) Contorno a 6 h 13 r 7
del costo
f 8
2 a 3 G 11 c G 10
b c 3
1 8 2
2 e
3 d f
9 2
S h 8 1
1 p q r
Nota: para este ejemplo los empates se resolverán según el orden alfabético
15
5.3 Búsqueda de Costo Uniforme
• ¿Qué nodo expande UCS?
• Procesa todos los nodos con un costo menor a la solución
óptima
• Si la solución óptima cuesta C ∗ y suponemos que cada b
g1
acción cuesta mínimo …
• Si m es finito, expandirá O(bC*/) nodos g2
C*/ “Niveles”
g3
• ¿Cuánta memoria se necesita para almacenar la
frontera?
• Almacenará al menos O(bC*/)
• UCS es completo?
• Sí, asumiendo que >0
• UCS es óptimo?
• Sí. (se demostrará más adelante a través de A*)
5.4 Búsqueda. Comparación
Una comparación en términos de eficiencia para los tres algoritmos
Preguntas