UNIVERSIDAD DE CUNDINAMARCA

INTELIGENCIA ARTIFICIAL

FRANCY JOHANA CENDALES ROBAYO

BÚSQUEDAS

Búsquedas informadas o heurísticas Búsquedas no informadas o ciegas

Estrategias Estrategias básicas • Búsqueda genérica
• Búsqueda voraz primero el mejor • Búsqueda de anchura
• A* • Búsqueda de profundidad
• Búsqueda de Best-First (Primero el mejor) • Profundidad con iteración
• Anchura iterada
• Búsqueda bidireccional
• BÚSQUEDA VORAZ PRIMERO EL MEJOR • BÚSQUEDA GENÉRICA
Los espacios de búsqueda, en general, pueden
Una primera estrategia, que representa una heurística muy ser representados como árboles o como grafos.
limitada pero muy extendida. En el algoritmo de búsqueda genérica no se
proporciona ninguna estrategia para el
La heurística usada se resume en suponer que, en cada paso, el recorrido de los nodos, simplemente es un
mejor camino se consigue al minimizar el coste inmediato. patrón que indica que "existe una forma" (no
determinada) de construir los caminos que
Algoritmo: Voraz empiezan en el nodo raíz y acaban en las hojas.
Insertar Estado_inicial Est_abiertos
Actual ← Primero Est_abiertos
mientras Actual no es_final? y Est_abiertos no vacía? hacer
Quitar_primero Est_abiertos
Insertar Actual Est_cerrados
hijos ← generar_sucesores_ordenados_por_peso (Actual)
hijos ← tratar_repetidos (Hijos, Est_cerrados, Est_abiertos)
Insertar Hijos Est_abiertos
Actual ← Primero Est_abiertos
Fin

Aunque explorar antes los nodos vecinos más cercanos puede

ayudar a encontrar una solución antes, es fácil dar ejemplos en
los que no se garantice que la solución encontrada sea óptima.

EL ALGORITMO A* • BÚSQUEDA DE ANCHURA

Consiste en visitar todos los nodos que hay a
• El coste de una arista entre dos nodos nini y njnj es el profundidad ii antes de pasar a visitar aquellos
coste del operador que hay a profundidad i+1i+1. Es decir, tras
que nos permite pasar de un nodo al otro, y lo visitar un nodo, pasamos a visitar a sus
denotaremos como c(ni,nj)c(ni,nj). Este coste hermanos antes que a sus hijos. Si usamos
siempre será positivo. estructuras de programación habituales.
• El coste de un camino entre dos nodos nini y njnj es la Este algoritmo es completo, es decir, si existe
suma de los costes de todos los arcos que llevan solución, este algoritmo la encuentra. Más aún,
desde un nodo al otro y lo denotaremos como: es óptimo, en el sentido de que si hay solución,
C(ni,nj)=∑x=ij−1c(nx,nx+1)C(ni,nj)=∑x=ij−1c(nx,nx+1) encuentra una de las soluciones a distancia
• El coste del camino mínimo entre dos mínima de la raíz.
nodos nini y njnj (el del camino de menor coste de
aquellos que llevan desde un nodo al otro) se • ANCHURA ITERADA
denotará por:
K(ni,nj)=minkCk(ni,nj)K(ni,nj)=minkCk(ni,nj) El algoritmo en Anchura Iterada (IB) es análogo
al ID, pero realiza una búsqueda DFS primero en
• Si njnj es un nodo terminal, para cada
los subárboles de anchura 11, después en los de
nodo nini notaremos h∗(ni)=K(ni,nj)h∗(ni)=K(ni,nj),
 es decir, el coste del camino mínimo desde ese anchura 22,... hasta encontrar un nodo
estado a un estado solución. solución.
• Si nini es un nodo inicial, para cada
nodo njnj notaremos g∗(nj)=K(ni,nj)g∗(nj)=K(ni,nj),
es decir, el coste del camino mínimo desde un
estado inicial a ese estado.

Algoritmo: A∗
Insertar Estado_inicial Est_abiertos
Actual ← Primero Est_abiertos
mientras Actual no es_final? y Est_abiertos no vacía? hacer
Quitar_primero Est_abiertos
Insertar Actual Est_cerrados
hijos ← generar_sucesores_ordenados_por_heurística (Actual)
hijos ← tratar_repetidos (Hijos, Est_cerrados, Est_abiertos)
Insertar Hijos Est_abiertos
Actual ← Primero Est_abiertos
fin

• BÚSQUEDA DE BEST-FIRST (PRIMERO EL MEJOR) • BÚSQUEDA DE PROFUNDIDAD

También puede ser vista como un proceso por
El usar el costo acumulado (búsqueda de costo uniforme) no niveles, tras visitar un nodo, se visitan sus hijos
necesariamente guía la búsqueda hacia la meta. Para ésto, se utiliza antes que sus hermanos, por lo que el
una estimación del costo del camino del estado hacia una meta ( algoritmo tiende a bajar por las ramas del árbol
hacia las hojas antes de visitar cada una de las
ramas posibles. De nuevo, si hacemos uso de
). estructuras clásicas de programación.
Para evitar este problema es común trabajar
Esta estrategia (minimizar el costo estimado para alcanzar una meta) a con una pequeña variante de este algoritmo
veces se llama una estrategia ``greedy''. que se llama de Profundidad limitada, que
impone un límite máximo al nivel alcanzado.

La función de evaluación ( ) puede ser lo que sea Procedimiento: Busqueda en profundidad

limitada (limite: entero)
Est_abiertos.insertar(Estado inicial)
mientras si es una meta. Actual ← Est_abiertos.primero()
mientras no es_final?(Actual) y no
Una estrategia ``greedy'' es susceptible de errores. El tiempo en el Est_abiertos.vacia?() hacer
Est_abiertos.borrar_primero()
Est_cerrados.insertar(Actual)
peor de los casos es donde es la profunidad máxima si profundidad(Actual) ≤ limite entonces
del espacio. Hijos ← generar_sucesores (Actual)
Hijos ← tratar_repetidos (Hijos, Est_cerrados,
Debido a que guardan todos los nodos en memoria, su complejidad en Est_abiertos)
espacio es igual a la del tiempo. Est_abiertos.insertar(Hijos)
fin
Actual ← Est_abiertos.primero()
Fin

• PROFUNDIDAD CON ITERACIÓN

Mezcla los requerimientos espaciales del
dfs (lineal en dd) y las propiedades
óptimas del bfs (completo y
asintóticamente óptimo). la idea principal
de este algoritmo es hacer una búsqueda
dfs repetidamente sobre subárboles de
profundidad 00, después de
 profundidad 11, después 22, hasta que se
alcanza el objetivo.

Procedimiento: Busqueda en profundidad

iterativa (limite: entero)
prof ← 1
Actual ← Estado inicial
mientras no es_final?(Actual) y prof
Est_abiertos.inicializar()
Est_abiertos.insertar(Estado inicial)
Actual ← Est_abiertos.primero()
mientras no es_final?(Actual) y no
Est_abiertos.vacia?() hacer
Est_abiertos.borrar_primero()
Est_cerrados.insertar(Actual)
si profundidad(Actual) ≤ prof entonces
Hijos ← generar_sucesores (Actual)
Hijos ← tratar_repetidos (Hijos, Est_cerrados,
Est_abiertos)
Est_abiertos.insertar(Hijos)
fin
Actual← Est_abiertos.primero()
fin
prof ← prof+1
fin

• • Búsqueda bidireccional
Se realizan dos búsquedas simultáneas: una
desde el estado inicial hasta el estado final, y
otra desde el estado final hasta el estado inicial.
La búsqueda global acaba cuando ambas
búsquedas parciales se encuentran. Sin
embargo, no todos los problemas de búsqueda
básicos se pueden plantear de forma sencilla
como problemas de búsqueda bidireccionales,
muchas veces porque no es sencillo
proporcionar la función de transición inversa.
Habitualmente, se suele implementar como un
par de algoritmos BFS simultáneos, así que,
como ellos, será óptimo y completo.
Ventajas • Normalmente en problemas complejos necesitamos soluciones • Si existe solución la encuentra en el
optimas, solo suficientemente buenas. menor tiempo posible.
• Aunque las aproximaciones conseguidas con heurísticos no sean • Tiene mejor complejidad que
buenas en el peor caso, este caso no se da normalmente. búsqueda en amplitud
• Tratar de entender porque funciona (o no funciona) un • Evita repetir la exploración de
heurístico muchas veces nos da un conocimiento mayor del caminos abandonados.
problema que estamos intentando resolver.
Bibliografía

• Sancho. F . (2019). Búsquedas informadas. http://www.cs.us.es/~fsancho/?e=62

• Benites. E. (2010). Resolución de problemas mediante búsquedas.
https://www.uv.mx/personal/edbenitez/files/2010/09/CursoIA10-II-3.pdf
• Alvarez. J. Búsqueda informada.
https://www.infor.uva.es/~jjalvarez/asignaturas/IA_teoria/lectures/busqueda_informada.pdf
• Sancho. F . (2019). Búsquedas No informadas .http://www.cs.us.es/~fsancho/?e=95