8/18/2019 El Algoritmo A*

1/4

I.1.1 El algoritmo A*

Introducción al algoritmo a* (star o asterisco)

El algoritmo A* (conocido también como A estrella o asterisco) es un algoritmo de búsqueda que encuentra la ruta de menor coste entre dos puntos siempre y cuando se

cumplan una serie de condiciones. Está clasificado dentro de los algoritmos de

 búsqueda en grafos ya que tiene la necesidad de dar a los mecanismos robóticos,

e!iculares o irtuales un sistema de naegación autónomo.

Es ampliamente utili"ado en las ciencias de la computación para encontrar rutas y que

tan transitable es una gráfica, es decir, se refiere al problema de isitar todos los nodos

en una gráfica dada de forma particular , esto no es más que el proceso de tra"ado de laruta más eficiente entre unos puntos llamados nodos. Este algoritmo go"a de una

aceptable y continua implementación gracias a su desempe#o y precisión. $ue descrito

 por primera e" en %&' como una etensión del algoritmo de i+stra (%&-&), por eter 

/art, 0ils 0ilsson y 1ertran 2ap!ael, que epusieron que el A* lograba un me+or 

desempe#o con respecto al tiempo usando !eur3sticas.

I.1.1 Orígenes del algoritmo A*

En %&'4 0ils 0ilsson inentó una !eur3stica basada en aproimaciones para incrementar 

la elocidad del algoritmo de i+stra. Este algoritmo fue llamado inicialmente como

A%.

En %&'5 1ertran 2ap!ael !i"o me+oras dramáticas sobre este algoritmo pero falló en

demostrar su optimali"ad. 6l llamó a este algoritmo como A7. /art introdu+o un

argumento que el A7 era óptimo usando una !eur3stica consistente !aciendo unos

cambios menores. 8u comprobación del algoritmo también demostró que el A7 era el

me+or algoritmo dadas algunas condiciones. As3 /art llamó a este nueo algoritmo con

la sintais 9:leene star; (debido a que representa una operación con solamente un

operando

8/18/2019 El Algoritmo A*

2/4

determinadas condiciones, el camino de menor coste entre una condición inicial y una

condición meta.

El algoritmo A* es usualmente utili"ado en los problemas para encontrar la me+or ruta o

camino, lo que reali"a el algoritmo es construir todas las rutas desde un punto inicial

!asta encontrar alguna que llegue al nodo final o meta. e éste modo solamente

construye aquellas rutas que son candidatas a formar una solución o camino desde el

inicio !asta el nodo final. ara poder determinar que rutas son las que tienen mayor 

 probabilidad de llegar al nodo meta, el algoritmo utili"a una !eur3stica basada en la

distancia de cualquier punto dado !ac3a la meta.

onde se diferencia el algoritmo A* de otros algoritmos aaros de 9best?first searc!; es

el !ec!o de que a tomando en cuenta la distancia que ya !a recorrido !asta el

momento, !aciendo de este modo una respuesta muc!o más completa y óptima.

Este algoritmo en particular es uno de los más adecuados para este proyecto de

inestigación ya que según los creadores del mismo es un algoritmo que encuentra el

camino de menor coste de un recorrido A aun recorrido 1. Aplicando dic!o algoritmo a

este proyecto de inestigación pretendemos obtener un buen resultado en cuanto a la

optimi"ación de rutas de transportes.

I.1.1 Descripción del algoritmo A*

Es un algoritmo que se encarga de encontrar la ruta que representa un menor costo entre

un punto A y otro 1. Es una técnica de búsqueda para grafos que utili"a una función

!eur3stica (ya que trata de métodos eploratorios durante la resolución del problema en

el cual la solución se descubre por la ealuación del progreso logrado en la búsqueda de

un resultado final denotada f @(), la cual es una aproimación a f() que proporciona la

erdadera ealuación de un nodo para determinar el orden en que se reali"a la isita a

los otros nodos del árbol. a función de ealuación es el resultado de la suma de otras

dos funciones, una que indica el coste del camino que se !a seguido !asta un cierto

nodo la cual se representa como g() y otra que nos da una estimación de la distancia

del punto o nodo en que nos encontramos !asta la meta que está representada como

!(). Entonces la función de ealuación es el resultado de la suma de !() y g().

Entonces cada una de ellas se representa de la siguiente maneraB

8/18/2019 El Algoritmo A*

3/4

ondeB

costoB representa el alor epl3cito de moernos de nuestro punto actual al siguiente enalguna dirección dada, si no se especifica se toma como unitario ya que pertenece a una

distribución uniforme.

absB representa el alor absoluto de la operación dentro del paréntesis.

nodox, nodoB son las coordenadas (, y) del nodo en el que nos encontramos

actualmente.

ob!eti"ox , ob!eti"o  B representa las coordenadas de posición de nuestra meta u

ob+etio al cual deseamos llegar.

Cuando comen"amos a anali"ar el problema nuestro nodo origen tiene un alor inicial D

(cero) tanto en ! como en g.

osteriormente g() se representa de la siguiente maneraB

ondeB

#$ representa un alor entre D y % dado por las circunstancias del problema a resoler.padreg B es el alor obtenido de la ecuación g() del anterior nodo padre. Cuando

iniciamos los cálculos por primera e", este alor es D para el nodo origen.

En esta ecuación debemos prestar atención especial conforme ayamos aan"ado en el

9pat!finding; ya que debemos sumar al resultado obtenido en la ecuación anterior el

mismo alor g del padre anterior de nuea forma, es decir, tendr3amos algo as3B

e esta forma podemos empe"ar a reali"ar los cálculos para cada uno de los nodos que

se ayan anali"ando. Este algoritmo consiste entonces en atraesar una gráfica (de

forma definida normalmente) siguiendo una ruta con el menor costo conocido

manteniendo una cola sorteada de prioridades con segmentos de rutas alternas a lo largo

del camino para que si en un momento dado la ruta que se está siguiendo arro+a un alor 

(costo) superior en comparación con otro segmento de ruta encontrado, esta abandona

esa ruta actual de alto coste y en e" de ella toma la que le brinda un camino más

9barato;. e esta forma el proceso sigue !asta alcan"ar la meta u ob+etio.

8/18/2019 El Algoritmo A*

4/4

Empe"ando en un nodo inicial dado, el algoritmo epande el nodo con el menor alor 

de f@(). Este algoritmo mantiene un con+unto de soluciones parciales almacenadas en

una cola de prioridad. El proceso continua !asta que una meta tiene un alor f@()

menor que cualquier otro nodo en la cola o !asta que el árbol !a sido recorrido

completamente. Como aspecto positio podemos considerar que ningún otro algoritmo

óptimo nos garanti"a epandir menos nodos que A*, pero éste requiere un alto consumo

de memoria