titulos
Páginas: 2 (478 palabras)
Publicado: 21 de noviembre de 2013
El algoritmo de búsqueda A* (A Estrella) se clasifica
dentro de los algoritmos de
búsqueda en grafos.
Presentado por primera vez en 1968 por Peter E.
Hart, Nils J. Nilsson yBertram
Raphael.
El algoritmo encuentra, siempre y cuando se
cumplan unas determinadas condiciones: el camino
de menor coste entre un nodo origen y uno
objetivo.
El problema de algunosalgoritmos de
búsqueda en grafos informados (algoritmo
voraz ) , es que se guían en exclusiva por la
función heurística, la cual puede no indicar el
camino de coste más bajo, o por el coste realde desplazarse de un nodo a otro (como los
algoritmos de escalada), pudiéndose dar el
caso de que sea necesario realizar un
movimiento de coste mayor para alcanzar la
solución.
Es por ellobastante intuitivo el hecho de que
un buen algoritmo de búsqueda informada
debería tener en cuenta ambos factores, el
valor heurístico de los nodos y el coste real
del recorrido.
Una pila deelementos denominada abierta
Una pila de elementos denominada cerrada
Una función de evaluación
Y claro el grafo que vamos a evaluar
El algoritmo A* utiliza una funciónde
evaluación f(n) = g(n) + h(n)
Trata de minimizar el coste estimado total de la
solución.
f(n) Combina el costo del camino para llegar a
n y el costo estimado para llegar desde nal
objetivo.
g(n): costo de haber alcanzado n
h(n): costo para llegar desde n hasta el objetivo
En cada paso del algoritmo, se expande el
nodo que esté primero en abiertos, yen caso
de que no sea un nodo objetivo, calcula la
f(n) de todos sus hijos, los inserta en
abiertos, y pasa el nodo evaluado a cerrados.
El algoritmo es una combinación entre
búsquedasdel tipo anchura prioritaria y
profundidad prioritaria: mientras que h(n)
tiende a profundidad prioritaria, g(n) tiende
a anchura prioritaria. De este modo, se
cambia de camino de búsqueda cada...
El algoritmo de búsqueda A* (A Estrella) se clasifica
dentro de los algoritmos de
búsqueda en grafos.
Presentado por primera vez en 1968 por Peter E.
Hart, Nils J. Nilsson yBertram
Raphael.
El algoritmo encuentra, siempre y cuando se
cumplan unas determinadas condiciones: el camino
de menor coste entre un nodo origen y uno
objetivo.
El problema de algunosalgoritmos de
búsqueda en grafos informados (algoritmo
voraz ) , es que se guían en exclusiva por la
función heurística, la cual puede no indicar el
camino de coste más bajo, o por el coste realde desplazarse de un nodo a otro (como los
algoritmos de escalada), pudiéndose dar el
caso de que sea necesario realizar un
movimiento de coste mayor para alcanzar la
solución.
Es por ellobastante intuitivo el hecho de que
un buen algoritmo de búsqueda informada
debería tener en cuenta ambos factores, el
valor heurístico de los nodos y el coste real
del recorrido.
Una pila deelementos denominada abierta
Una pila de elementos denominada cerrada
Una función de evaluación
Y claro el grafo que vamos a evaluar
El algoritmo A* utiliza una funciónde
evaluación f(n) = g(n) + h(n)
Trata de minimizar el coste estimado total de la
solución.
f(n) Combina el costo del camino para llegar a
n y el costo estimado para llegar desde nal
objetivo.
g(n): costo de haber alcanzado n
h(n): costo para llegar desde n hasta el objetivo
En cada paso del algoritmo, se expande el
nodo que esté primero en abiertos, yen caso
de que no sea un nodo objetivo, calcula la
f(n) de todos sus hijos, los inserta en
abiertos, y pasa el nodo evaluado a cerrados.
El algoritmo es una combinación entre
búsquedasdel tipo anchura prioritaria y
profundidad prioritaria: mientras que h(n)
tiende a profundidad prioritaria, g(n) tiende
a anchura prioritaria. De este modo, se
cambia de camino de búsqueda cada...
Leer documento completo
Regístrate para leer el documento completo.