UNIVERSIDAD MAYOR DE SAN SIMÓN FACULTAD DE CIENCIAS Y TECNOLOGÍA

INTELIGENCIA ARTIFICIAL
(BÚSQUEDA A ESTRELLA)

​ Integrantes:
Aymar Marza Savina
Barahona Jaimes Gabriela Lucia.
Gomez Ferrufino Melina Romané
Martinez Lero Cristobal Julian

Fecha:
18/09/2019

Cochabamba - Bolivia
 Contenido

Introducción 3

Cómo funciona la búsqueda 3

Algoritmo de búsqueda 4

Estrategias de función a 4 criterios de la búsqueda 5

Completo 5

Complejidad de tiempo 5

Complejidad de espacial 5

Óptimo 5

Ejemplo 6

Conclusiones 9

Bibliografía 9
Introducción
En 1964 nace el Algoritmo A*, cuando Nils Nilsson inventó una heurística basada en
aproximaciones para incrementar la velocidad del algoritmo de Dijkstra​, ​Este algoritmo fue
llamado inicialmente como A1, después en 1967 Berthran Raphael hizo mejoras dramáticas
sobre el algoritmo A1 pero falló en demostrar su optimización ahora este algoritmo se llamaría
A2 pero Hart introdujo un argumento que el A2 era óptimo usando una heurística consistente
haciendo unos cambios menores. La comprobación del algoritmo también demostró que el A2
era el mejor algoritmo dadas algunas condiciones. Fue así que Hart llamó a este nuevo
algoritmo con la sintaxis de “Kleene Star” por ser un algoritmo que empieza con la letra A e
incluye todas las versiones de números posibles o A*.

El Algoritmo A* es uno de las estrategias más conocidas, se clasifica dentro de los ​algoritmos
de búsqueda con información y es mayormente utilizado para búsquedas sobre grafos. El
algoritmo encuentra siempre y el ​camino de menor costo ​entre un nodo origen y uno objetivo
siempre y cuando exista.

Cómo funciona la búsqueda

Lo que realiza el algoritmo es construir ​distintas rutas desde un punto ​inicial hasta encontrar
alguna que llegue hasta el nodo final.​ De este modo solo construye aquellas rutas que son
candidatas a formar una solución. Para poder determinar qué rutas son las que tienen mayor
probabilidad de llegar al nodo meta.

Se llega a una fórmula que es considerada lo más importante en este algoritmo de búsqueda
heurística que es la siguiente:

En donde:
F(n) ​= Se entiende como el costo total
g(n)​ = se entiende como el valor del camino de un nodo a otro
h(n)​ = se entiende como el valor de la heurística de un nodo a otro

Lo primero que se hace es expandir el primer nodo que se encuentre en la lista de abiertos,
en caso de que este no sea un nodo objetivo, se calcula ​F(n) de todos los descendientes de
este nodo, estos se insertan en la lista de abiertos, y el primer nodo o nodo raíz pasa de una
vez a la lista de cerrados. Así continúa sucesivamente hasta que encuentre la solución, como
se mencionó anteriormente si un nodo que esté en abiertos es igual a uno que este
encerrados este pasa a cerrados de una vez.

3
Algoritmo de búsqueda

Identificar​ nodo inicial ​y ​nodo final

Si​ ​nodo inicial = nodo fina​l
Retornar​ ​nodo inicio como respuesta
Fin si
Sí no
Crear​ lista abierta para nodos (cada nodo tiene atributos g, h, f, p)
Crear​ lista cerrada para nodos (cada nodo tiene atributos g, h, f, p)
Crear​ lista vecinos para nodos (cada nodo tiene atributos g, h, f, p)
Crear ​nodo actual
Insertar nodo inicial en lista cerrada con g=0 (costo de nodo)

Mientras ​nodo final no se encuentre en la lista cerrada

Nodo actual = último elemento agregado a la lista cerrada

Agregar los nodos vecinos del nodo actual en la lista vecinos excepto nodos que
estén en la lista cerrada

​Para ​todo nodo de la lista vecinos calcular los atributos:

​g = g del nodo actual + costo del nodo vecino al nodo actual
h = costo (directo) aproximado desde el nodo vecino al nodo final
f=g+h
p = nodo actual
​fin para

​Para ​cada nodo de la lista vecinos

Si ​el nodo vecino no se encuentra en la lista abierta ni en la lista cerrada
Copiar nodo vecino en la lista abierta
​Fin si
Si no
​Si ​nodo vecino ya se encuentra en la lista abierta
​Si ​g del nodo vecino < al g del mismo nodo de la lista abierta
Actualizar atributos del nodo de la lista abierta con atributos del mismo nodo
de la lista vecinos
Fin si
Fin si
Fin si no

​Fin para

4
 Vaciar nodos de la lista vecinos
Elegir nodo con menor f de la lista abierta y moverlo a la lista cerrada (si existe
empate, el primero de la lista)
Fin mientras ​(volver a mientras)

Crear lista ruta corta

Lista ruta corta = Invertir (Leer nodo final y trazar ruta por medio de los nodos padres
(p) hasta llegar a nodo inicio)
Retornar lista ruta corta
Fin si no

Estrategias de función a 4 criterios de la búsqueda

Completo
El algoritmo si es completo, porque si encuentra una solución, si la hay.

Complejidad de tiempo
La complejidad computacional del algoritmo está íntimamente relacionada con la calidad de la
heurística que se utilice en el problema. En el caso peor, con una heurística de pésima calidad, la
complejidad será exponencial(O(2​n​)), mientras que en el caso mejor, con una buena heurística, el
algoritmo se ejecutará en tiempo lineal(O(n)).

Complejidad de espacial
También exponencial, si en vez de buscar la solución óptima, se busca sólo una solución, entonces una
buena heurística puede lograr resultados en tiempos y espacios más reducidos.

Óptimo
A * es óptimamente eficiente, ningún otro algoritmo óptimo garantiza expandir menos nodos que A*.
Los algoritmos que no expanden todos los nodos f(n) corren el riesgo de no encontrar la solución
óptima. A estrella de la ruta menos costosa siempre y cuando le heurística sea admisible.

Ejemplo

5
S representa el punto de partida. La bandera azul representa la meta. Los casilleros de color
negro representan obstáculos y los casilleros blancos representan caminos posibles.
Nuestra función heurística será:

En pocas palabras, lo que expresamos en la fórmula anterior fue la distancia que resta para
llegar a la meta desde la posición en la cual nos encontramos.
¿Y cuáles serían las primeras movidas posibles?

En la figura anterior vemos a izquierda como avanzamos por el mapa y derecha como queda
conformado el árbol con el valor de la función f(n) para cada una de las bases abiertas. De todas
ellas seleccionaremos la de menor f, es decir, la de menor costo calculado como la suma del
costo del camino recorrido y el costo estimado del camino que resta recorrer. Para entender
cómo realizamos el cálculo del valor de la función f(n), veamos en mayor detalle como
realizamos el cálculo de la primer movida:

g siempre incrementará en uno a medida que avancemos por el mapa (ya que estamos
tomando el costo de avance en forma unitaria para todas las posiciones) y h será el resultado de
aplicar la fórmula de la figura 2, que es la distancia de dicha posición a la meta.
Una vez abiertas las bases del nivel, deberemos elegir cual tomar para seguir nuestro camino.
Para esto, siempre deberemos seleccionar la de menor f (en caso de haber más de una con
mismo valor, la elección es arbitraria). Siguiendo nuestro ejemplo, deberemos seleccionar la
movida 2.

6
Evaluamos las movidas posibles a partir de la posición elegida y volvemos a seleccionar la de
menor f. Es muy importante destacar que en dicha elección también intervienen las bases
abiertas en las movidas anteriores (que en el árbol están pintadas de color amarillo). Por lo
tanto, es posible (y muy factible) que en un determinado momento el algoritmo abandone el
camino por el cual se dirige para "probar suerte" por otro lado.

De la figura 6 es interesante notar cómo el algoritmo intenta elegir un camino que lo lleve en
línea recta hacia la meta, ¡pero dicho camino está obstruido! Efectivamente, vamos camino a un
callejón sin salida. Llegado el momento, el algoritmo tomará cuenta que a partir de una posición
no es posible realizar más movidas y deberá volver sobre sus pasos para seleccionar una base
abierta anteriormente en su búsqueda por la meta.

7
Aplicando varias movidas las novedades son las siguientes:
Abandonamos el camino por la movida 4 debido a que quedamos encerrados. Intentamos seguir
por el camino de la movida 1 pero tampoco nos llevaba a ningún
lado.
Tomamos el camino de la movida 3 y avanzamos por el único lugar que podemos.

Continuamos avanzando por el mapa, hemos abierto las bases 6 y 7, de las cuales
seleccionamos la 6. A partir de allí abrimos las bases 8, 9 y 10, de las cuales como se puede
apreciar en el árbol de la figura anterior, seleccionaremos la 8.

8
Finalmente encontramos el camino a la meta, que como podemos apreciar es el más corto de
todos los caminos posibles.

Conclusiones
La complejidad del desarrollo del algoritmo A* está ligado directamente a que tan buena sea la
heurística que se proporciona, la heurística es una aproximación cuantitativa de lo que falta
para llegar a la solución, también sabemos que existen heurísticas muy bien definidas y otras
no tanto, por ende esto es lo principal para determinar la complejidad que puede llegar a ser
exponencial si este factor es de dudosa calidad, en cuanto al espacio requerido para
ejecutarse se trata de un espacio exponencial respecto al tamaño del problema, ya que en un
problema con muchos nodos esta se vuelve una tarea ardua al tener que considerar todos los
sucesores con sus costos respectivos.

Bibliografía
“Búsqueda Heurística” (Prof. Constantino Malagón) recuperado de:
https://www.nebrija.es/~cmalagon/ia/transparencias/busqueda_heuristica.pdf

“Algoritmo A estrella” (Búsqueda Informada e Información), recuperado de:

https://advanceintelligence.wordpress.com/2014/10/07/algoritmo-a-estrella/
“Algoritmo A*” (IDElab) recuperado de:

http://idelab.uva.es/algoritmo ​“Algoritmo de Búsqueda A*”

Inteligencia Artificial “un enfoque moderno” de Stuart Russell, Peter Norving