Diferencia entre revisiones de «Algoritmo de Búsqueda Heurística A*»

(Página creada con ' El '''Algoritmo de Búsqueda A*''' conocido también como A asterisco o A estrella se clasifica dentro de los algoritmos de búsqueda en grafos. Su función es encontrar ...')
(Etiqueta: nuestro-nuestra)
 
m (Texto reemplazado: «<div align="justify">» por «»)
 
(No se muestran 9 ediciones intermedias de 5 usuarios)
Línea 1: Línea 1:
 
El  '''Algoritmo de Búsqueda A*''' conocido también como A asterisco o A estrella se clasifica dentro de los [[algoritmos de búsqueda en grafos]]. Su función es encontrar siempre y cuando se cumplan determinadas condiciones, el [[camino de menor costo]] entre un nodo origen y uno objetivo, es la forma más ampliamente conocida de la [[búsqueda primero el mejor]],  siendo la búsqueda A* tanto completa como óptima.
 
 
 
{{Ficha Software
 
{{Ficha Software
 
|nombre= Algoritmo de Búsqueda Heurística A*.
 
|nombre= Algoritmo de Búsqueda Heurística A*.
 
|imagen=A.PNG ‎
 
|imagen=A.PNG ‎
 
|presentado por= [[Peter E. Hart]], [[Nils J. Nilsson]] y [[Bertram Raphael]].
 
|presentado por= [[Peter E. Hart]], [[Nils J. Nilsson]] y [[Bertram Raphael]].
|año=1968.
+
|año=[[1968]]
 
}}
 
}}
 +
 +
'''Algoritmo de Búsqueda A.''' Conocido también como A asterisco o  A estrella fue presentado por [[Peter E. Hart]], [[Nils J. Nilsson]] y  [[Bertram Raphael]] en el año [[1968]],se clasifica dentro de los  [[algoritmos de búsqueda en grafos]]. Su función es encontrar siempre y  cuando se cumplan determinadas condiciones, el [[camino de menor costo]]  entre un nodo origen y uno objetivo, es la forma más ampliamente  conocida de la [[búsqueda primero el mejor]],  siendo la búsqueda A*  tanto completa como óptima.
  
 
==Características Principales==
 
==Características Principales==
Línea 28: Línea 27:
 
   
 
   
 
La familia de los [[algoritmos informados]], frente a los desinformados o por fuerza bruta, son aquellos que poseen una información extra sobre la estructura a objeto de estudio, la cual explotan para alcanzar más rápidamente su objetivo final, con un camino de costo mínimo desde el punto inicial al final.
 
La familia de los [[algoritmos informados]], frente a los desinformados o por fuerza bruta, son aquellos que poseen una información extra sobre la estructura a objeto de estudio, la cual explotan para alcanzar más rápidamente su objetivo final, con un camino de costo mínimo desde el punto inicial al final.
 +
 
La búsqueda informada es aquella que utiliza el conocimiento específico del problema más allá de la definición del problema en sí mismo, la cual puede encontrar soluciones de una manera más eficiente que una estrategia no informada, increíblemente ineficiente en la mayoría de los casos.
 
La búsqueda informada es aquella que utiliza el conocimiento específico del problema más allá de la definición del problema en sí mismo, la cual puede encontrar soluciones de una manera más eficiente que una estrategia no informada, increíblemente ineficiente en la mayoría de los casos.
  
Línea 38: Línea 38:
 
El algoritmo es una combinación entre búsquedas del tipo [[primero en anchura]] con [[primero en profundidad]]: mientras que h'(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia de camino de búsqueda cada vez que existen nodos más prometedores.
 
El algoritmo es una combinación entre búsquedas del tipo [[primero en anchura]] con [[primero en profundidad]]: mientras que h'(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia de camino de búsqueda cada vez que existen nodos más prometedores.
  
===Función heurística de A*===
+
*Función heurística de A*
*f (n) = g(n) + h(n): Coste real del plan (camino) de mínimo coste que pasa por n.
+
f (n) = g(n) + h(n): Coste real del plan (camino) de mínimo coste que pasa por n.
 
   
 
   
*f* (n) = g(n) + h*(n): estimación de f.
+
f* (n) = g(n) + h*(n): estimación de f.
  
===Estrategia de A*===
+
*Estrategia de A*
 
Entre las hojas del [[árbol de búsqueda]], elegir el nodo de valor f* mínimo.
 
Entre las hojas del [[árbol de búsqueda]], elegir el nodo de valor f* mínimo.
  
===Interpretación fuerte de A*===
+
*Interpretación fuerte de A*
*Una heurística suele facilitar la resolución de un problema, pero no garantiza que se resuelva.
+
Una heurística suele facilitar la resolución de un problema, pero no garantiza que se resuelva.
 
   
 
   
*Una heurística es una regla de tres para un problema.
+
Una heurística es una regla de tres para un problema.
 
   
 
   
*Búsqueda: Optimalidad o incluso completitud no garantizados.
+
Búsqueda: Optimalidad o incluso completitud no garantizados.
  
===Esquematización de A*===
+
*Esquematización de A*
*Se basa en la búsqueda general.
+
Se basa en la búsqueda general.
 
   
 
   
*Almacenar el valor g de cada nodo expandido.
+
Almacenar el valor g de cada nodo expandido.
 
   
 
   
*Mantener la estructura abierta ordenada por valores crecientes de f*.
+
Mantener la estructura abierta ordenada por valores crecientes de f*.
 
   
 
   
*Insertar nuevos nodos en la estructura abierta según sus valores de f*.
+
Insertar nuevos nodos en la estructura abierta según sus valores de f*.
  
 
==Pseudocódigo==
 
==Pseudocódigo==
Línea 136: Línea 136:
 
Es la estructura dinámica, en nuestro caso a nivel de implementación [[cola con prioridad]] según valores de la estimación f*, de almacenamiento temporal del expansionamiento de los nodos intermedios de camino al nodo meta o fin, a medida que el algoritmo vaya iterando, esta irá viendo cómo se introducen en el nodos hijos a consecuencia del expansionamiento de sus respectivos antecesores, los cuales se irán ordenando por mínimo f*, dando prioridad no garantiza a nuestra heurística, puesto que estará determinada por los patrones de costes reales asociados, número de paradas y transbordos realizados hasta el momento, y el coste estimado obtenido según rectitud en el camino al nodo meta.
 
Es la estructura dinámica, en nuestro caso a nivel de implementación [[cola con prioridad]] según valores de la estimación f*, de almacenamiento temporal del expansionamiento de los nodos intermedios de camino al nodo meta o fin, a medida que el algoritmo vaya iterando, esta irá viendo cómo se introducen en el nodos hijos a consecuencia del expansionamiento de sus respectivos antecesores, los cuales se irán ordenando por mínimo f*, dando prioridad no garantiza a nuestra heurística, puesto que estará determinada por los patrones de costes reales asociados, número de paradas y transbordos realizados hasta el momento, y el coste estimado obtenido según rectitud en el camino al nodo meta.
  
===Especificación del coste real g===
+
===Especificación del coste real g*===
 
   
 
   
 
Tomaremos de partida y para relajar la toma de mediciones y las numerosas pruebas en la implementación del algoritmo, que el coste real asociado en cada avance en el cálculo de la mejor solución costará una unidad por movilidad de una estación n1 a otra n2, así como la adición de una unidad extra más para el caso de transbordos entre líneas, si fuera el caso de que n2 perteneciera a una línea con la que n1 no tuviera correspondencia, o en la particularidad de 3 estaciones que, por aspectos de infraestructura, aún encontrándose en la misma línea que sus estaciones antecesora y sucesora, resulta obligatorio un cambio de tren.
 
Tomaremos de partida y para relajar la toma de mediciones y las numerosas pruebas en la implementación del algoritmo, que el coste real asociado en cada avance en el cálculo de la mejor solución costará una unidad por movilidad de una estación n1 a otra n2, así como la adición de una unidad extra más para el caso de transbordos entre líneas, si fuera el caso de que n2 perteneciera a una línea con la que n1 no tuviera correspondencia, o en la particularidad de 3 estaciones que, por aspectos de infraestructura, aún encontrándose en la misma línea que sus estaciones antecesora y sucesora, resulta obligatorio un cambio de tren.
Línea 144: Línea 144:
 
Precisamos que la heurística o coste estimado que tomaremos desde un nodo actual hasta el nodo meta y para todo nodo en el árbol de exploración de camino a la solución será en función de cuanto de recto se presenten los nodos; es decir, el coste estimado h* es la distancia en línea recta. En cada nodo hijo, el coste estimado es su distancia en línea recta con el nodo meta. Tomando como referencia que cada estación tiene un punto en el mapa, unas coordenadas en la imagen, y aplicando una escala más o menos aproximada, se logra la obtención de coordenadas reales (valores discretos, relativos), escogiendo las coordenadas de una cualquiera y las de la destino, y haciendo uso de la [[distancia euclídea]], distancia ordinaria entre dos puntos de un [[espacio euclídeo]] que se deduce a partir del [[teorema de Pitágoras]].
 
Precisamos que la heurística o coste estimado que tomaremos desde un nodo actual hasta el nodo meta y para todo nodo en el árbol de exploración de camino a la solución será en función de cuanto de recto se presenten los nodos; es decir, el coste estimado h* es la distancia en línea recta. En cada nodo hijo, el coste estimado es su distancia en línea recta con el nodo meta. Tomando como referencia que cada estación tiene un punto en el mapa, unas coordenadas en la imagen, y aplicando una escala más o menos aproximada, se logra la obtención de coordenadas reales (valores discretos, relativos), escogiendo las coordenadas de una cualquiera y las de la destino, y haciendo uso de la [[distancia euclídea]], distancia ordinaria entre dos puntos de un [[espacio euclídeo]] que se deduce a partir del [[teorema de Pitágoras]].
  
   
+
==Véase también==
 +
*[[Algoritmo de ordenamiento]]
 +
*[[Algoritmo de búsqueda]]
 +
*[[Algoritmo de Kruskal]]
 +
*[[Algoritmo  de Euclides]]
 +
*[[Algoritmo de Prim]]
 +
*[[Algoritmo de Boruvka]]
 +
*[[Algoritmo  de Gutmann]]
 +
*[[Algoritmo criptográfico]]
 +
*[[Algoritmo de Ordenamiento  Burbuja]]
 +
*[[Algoritmo de Ordenamiento Shell]]
 +
*[[Algoritmo  genético]]
 +
*[[Algoritmo de  ordenamiento por  selección]]
 +
*[[Algoritmo de  árboles de decisión de  Microsoft]]
 +
*[[Algoritmo]]
 +
*[[Algoritmo asimétrico]]
 +
 
 
==Fuentes==
 
==Fuentes==
Juan José Salazar Gónzalez, “Programación Matemática”.  
+
* Juan José Salazar Gónzalez, “Programación Matemática”.  
  
Javier Alcáraz Soria, Concepción Maroto Alvarez, Rubén Ruiz García, “Investigación Operativa: modelos y técnicas de optimización”.
+
* Javier Alcáraz Soria, Concepción Maroto Alvarez, Rubén Ruiz García, “Investigación Operativa: modelos y técnicas de optimización”.
Robert Sedgewick,  “Algoritmos en C++”.
 
  
Varios Autores, “Metaheurísticas”,[[ 2007]].  
+
* Robert Sedgewick,  “Algoritmos en C++”.
 +
 
 +
* Varios Autores, “Metaheurísticas”,[[ 2007]].
  
 
 
==Referencias==
 
==Referencias==
http://poiritem.wordpress.com/2010/01/14/6-5-2-busqueda-heuristica-algoritmo-a/
+
*http://poiritem.wordpress.com/2010/01/14/6-5-2-busqueda-heuristica-algoritmo-a/
 
+
*http://es.scribd.com/doc/19950923/Busqueda-Heuristica
http://es.scribd.com/doc/19950923/Busqueda-Heuristica
+
*http://www.lawebdelprogramador.com/foros/Inteligencia_Artificial/492749-busqueda_heuristica.html
 
+
*http://www.iiia.csic.es/~pedro/busqueda1-introduccion.pdf
http://www.lawebdelprogramador.com/foros/Inteligencia_Artificial/492749-busqueda_heuristica.html
 
 
 
http://www.iiia.csic.es/~pedro/busqueda1-introduccion.pdf
 
 
   
 
   
 
[[Category:Algoritmos]]
 
[[Category:Algoritmos]]

última versión al 00:10 15 jul 2019

Algoritmo de Búsqueda Heurística A*.
Información sobre la plantilla
A.PNG

Algoritmo de Búsqueda A. Conocido también como A asterisco o A estrella fue presentado por Peter E. Hart, Nils J. Nilsson y Bertram Raphael en el año 1968,se clasifica dentro de los algoritmos de búsqueda en grafos. Su función es encontrar siempre y cuando se cumplan determinadas condiciones, el camino de menor costo entre un nodo origen y uno objetivo, es la forma más ampliamente conocida de la búsqueda primero el mejor, siendo la búsqueda A* tanto completa como óptima.

Características Principales

  • Para garantizar la optimalidad del algoritmo, la función h(n) debe ser admisible, o sea que no sobrestime el coste real de alcanzar el nodo objetivo.
  • De no cumplirse dicha condición, el algoritmo pasa a denominarse simplemente A, y a pesar de seguir siendo completo, no se asegura que el resultado obtenido sea el camino de coste mínimo. Asimismo, si garantizamos que h(n) es consistente (o monótona), es decir, que para cualquier nodo n y cualquiera de sus sucesores, el coste estimado de alcanzar el objetivo desde n no es mayor que el de alcanzar el sucesor más el coste de alcanzar el objetivo desde el sucesor.
  • La complejidad computacional está 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, mientras que en el caso mejor, con una buena h'(n), el algoritmo se ejecutará en tiempo lineal.
  • El espacio requerido por A* para ser ejecutado es su mayor problema. Dado que tiene que almacenar todos los posibles siguientes nodos de cada estado, la cantidad de memoria que requerirá será exponencial con respecto al tamaño del problema. Para solucionar este problema, se han propuesto diversas variaciones de este algoritmo, como pueden ser RTA*, IDA* o SMA*.

Búsqueda Heurística

La familia de los algoritmos informados, frente a los desinformados o por fuerza bruta, son aquellos que poseen una información extra sobre la estructura a objeto de estudio, la cual explotan para alcanzar más rápidamente su objetivo final, con un camino de costo mínimo desde el punto inicial al final.

La búsqueda informada es aquella que utiliza el conocimiento específico del problema más allá de la definición del problema en sí mismo, la cual puede encontrar soluciones de una manera más eficiente que una estrategia no informada, increíblemente ineficiente en la mayoría de los casos.

El problema de algunos algoritmos de búsqueda informada en estructuras de relativa complejidad, como puede ser el algoritmo voraz, es que se guían exclusivamente por la función heurística, la cual puede no indicar el camino de coste más bajo, o por el coste real de desplazarse de un nodo a otro, pudiéndose dar el caso de que sea necesario realizar un movimiento de coste mayor para alcanzar la solución. Es por ello bastante 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. A la forma más ampliamente conocida de la búsqueda primero el mejor se le llama búsqueda A*.

¿Cómo funciona A*?

Este algoritmo utiliza una función de evaluación f(n) = g(n) + h'(n), donde h'(n) representa el valor heurístico del nodo a evaluar desde el actual, n, hasta el final, y g(n), el costo real del camino recorrido para llegar a dicho nodo, n. A* mantiene dos estructuras de datos auxiliares, que podemos denominar abiertos, implementado como una cola de prioridad ordenada por el valor f(n) de cada nodo, y cerrados, donde se guarda la información de los nodos que ya han sido visitados. En cada paso del algoritmo, se expande el nodo que esté primero en abiertos, y en 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úsquedas del tipo primero en anchura con primero en profundidad: mientras que h'(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia de camino de búsqueda cada vez que existen nodos más prometedores.

  • Función heurística de A*

f (n) = g(n) + h(n): Coste real del plan (camino) de mínimo coste que pasa por n.

f* (n) = g(n) + h*(n): estimación de f.

  • Estrategia de A*

Entre las hojas del árbol de búsqueda, elegir el nodo de valor f* mínimo.

  • Interpretación fuerte de A*

Una heurística suele facilitar la resolución de un problema, pero no garantiza que se resuelva.

Una heurística es una regla de tres para un problema.

Búsqueda: Optimalidad o incluso completitud no garantizados.

  • Esquematización de A*

Se basa en la búsqueda general.

Almacenar el valor g de cada nodo expandido.

Mantener la estructura abierta ordenada por valores crecientes de f*.

Insertar nuevos nodos en la estructura abierta según sus valores de f*.

Pseudocódigo

Tratar Punto

// coste del camino hasta .

caso . = . perteneciente a ()
  si g(.) < g(.) entonces // (-----)
     // nos quedamos con el camino de menor coste
     .:= MEJORNODO
     actualizar g(.) y f'(.)
     propagar g a . de .
  eliminar .
  añadir . a ._MEJORNODO
caso . = . perteneciente a )-----(
  si g(.) < g(.) entonces
     // nos quedamos con el camino de menor coste
     .:= MEJORNODO
     actualizar g(.) y f'(.)
  eliminar .
  añadir . a ._MEJORNODO
caso . no estaba en ).( ni (.)
  añadir . a ).(
  añadir . a ._MEJORNODO
  f'(.) := g(.) + h'(.)

Implementación

ABIERTOS := [INICIAL] //inicialización 
CERRADOS := [] 
f'(INICIAL) := h'(INICIAL) 
repetir 
si ABIERTOS = [] entonces FALLO 
si no // quedan nodos 
extraer MEJORNODO de ABIERTOS con f' mí¬nima 
// cola de prioridad 
mover MEJORNODO de ABIERTOS a CERRADOS 
si MEJORNODO contiene estado_objetivo entonces 
SOLUCION_ENCONTRADA := TRUE 
si no 
generar SUCESORES de MEJORNODO 
para cada SUCESOR hacer TRATAR_SUCESOR 
hasta SOLUCION_ENCONTRADA o FALLO

Tratar Sucesor

SUCESOR.ANTERIOR := VIEJO 
// coste del camino hasta SUCESOR 

caso SUCESOR = VIEJO perteneciente a CERRADOS 
si g(SUCESOR) < g(VIEJO) entonces // (no si monotoní¬a) 
// nos quedamos con el camino de menor coste 
VIEJO.ANTERIOR := MEJORNODO 
actualizar g(VIEJO) y f'(VIEJO) 
propagar g a sucesores de VIEJO 
eliminar SUCESOR 
añadir VIEJO a SUCESORES_MEJORNODO 
caso SUCESOR = VIEJO perteneciente a ABIERTOS 
si g(SUCESOR) < g(VIEJO) entonces 
// nos quedamos con el camino de menor coste 
VIEJO.ANTERIOR := MEJORNODO 
actualizar g(VIEJO) y f'(VIEJO) 
eliminar SUCESOR 
añadir VIEJO a SUCESORES_MEJORNODO 
caso SUCESOR no estaba en ABIERTOS ni CERRADOS 
añadir SUCESOR a ABIERTOS 
añadir SUCESOR a SUCESORES_MEJORNODO 
f'(SUCESOR) := g(SUCESOR) + h'(SUCESOR)

Observaciones

Función Abiertos

Es la estructura dinámica, en nuestro caso a nivel de implementación cola con prioridad según valores de la estimación f*, de almacenamiento temporal del expansionamiento de los nodos intermedios de camino al nodo meta o fin, a medida que el algoritmo vaya iterando, esta irá viendo cómo se introducen en el nodos hijos a consecuencia del expansionamiento de sus respectivos antecesores, los cuales se irán ordenando por mínimo f*, dando prioridad no garantiza a nuestra heurística, puesto que estará determinada por los patrones de costes reales asociados, número de paradas y transbordos realizados hasta el momento, y el coste estimado obtenido según rectitud en el camino al nodo meta.

Especificación del coste real g*

Tomaremos de partida y para relajar la toma de mediciones y las numerosas pruebas en la implementación del algoritmo, que el coste real asociado en cada avance en el cálculo de la mejor solución costará una unidad por movilidad de una estación n1 a otra n2, así como la adición de una unidad extra más para el caso de transbordos entre líneas, si fuera el caso de que n2 perteneciera a una línea con la que n1 no tuviera correspondencia, o en la particularidad de 3 estaciones que, por aspectos de infraestructura, aún encontrándose en la misma línea que sus estaciones antecesora y sucesora, resulta obligatorio un cambio de tren.

Elección del coste estimado h*

Precisamos que la heurística o coste estimado que tomaremos desde un nodo actual hasta el nodo meta y para todo nodo en el árbol de exploración de camino a la solución será en función de cuanto de recto se presenten los nodos; es decir, el coste estimado h* es la distancia en línea recta. En cada nodo hijo, el coste estimado es su distancia en línea recta con el nodo meta. Tomando como referencia que cada estación tiene un punto en el mapa, unas coordenadas en la imagen, y aplicando una escala más o menos aproximada, se logra la obtención de coordenadas reales (valores discretos, relativos), escogiendo las coordenadas de una cualquiera y las de la destino, y haciendo uso de la distancia euclídea, distancia ordinaria entre dos puntos de un espacio euclídeo que se deduce a partir del teorema de Pitágoras.

Véase también

Fuentes

  • Juan José Salazar Gónzalez, “Programación Matemática”.
  • Javier Alcáraz Soria, Concepción Maroto Alvarez, Rubén Ruiz García, “Investigación Operativa: modelos y técnicas de optimización”.
  • Robert Sedgewick, “Algoritmos en C++”.
  • Varios Autores, “Metaheurísticas”,2007.

Referencias