ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Algoritmo de búsqueda A wiki: info, historia y vídeos

videos internet

salud  Algoritmo de búsqueda A 


wikiEjemplo de aplicación del algoritmo A*.

El algoritmo de busca A* (pronunciado "A asterisco", "A estrella" o bien "Astar" en inglés) se clasifica en los algoritmos de busca en grafos. Presentado por vez primera en mil novecientos sesenta y ocho por Peter Y también. Hart, Nils J. Nilsson y Bertram Raphael, el algoritmo A* halla, siempre que se cumplan unas determinadas condiciones, el camino de menor costo entre un nodo origen y uno objetivo.



Motivación y descripción


El inconveniente de ciertos algoritmos de busca en grafos informados, como puede ser el algoritmo insaciable, es que se guían en exclusiva por la función heurística, la que puede no apuntar el camino de costo más bajo, o bien por el costo real de desplazarse de un nodo a otro (como los algoritmos de escalada), pudiéndose dar el en el caso de que sea preciso efectuar un movimiento de costo mayor para lograr la solución. Es por este motivo bastante intuitivo el hecho de que un buen algoritmo de busca informada debería tomar en consideración los dos factores, el valor heurístico de los nodos y el costo real del recorrido.


Así, el algoritmo A* emplea una función de evaluación f(n)=g(n)+h'(n), donde h'(n) representa el valor heurístico del nodo a valorar desde el presente, n, hasta el final, y g(n), el costo real del camino recorrido para llegar a dicho nodo, n, desde el nodo inicial. A* sostiene 2 estructuras de datos auxiliares, que podemos llamar abiertos, incorporado 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 han sido visitados. En todos y cada paso del algoritmo, se expande el nodo que esté primero en abiertos, y caso de que no sea un nodo objetivo, calcula la f(n) de sus hijos, los introduce en abiertos, y pasa el nodo evaluado a cerrados.


El algoritmo es una combinación entre buscas del tipo primero en anchura con primero en profundidad: al tiempo que h'(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De esta forma, se cambia de camino de busca toda vez que existen nodos más prometedores.


Como todo algoritmo de busca en amplitud, A* es un algoritmo completo: en el caso de existir una solución, siempre y en toda circunstancia va a dar con ella.


Si para todo nodo n del grafo se cumple g(n)=0, nos hallamos frente a una busca insaciable. Si para todo nodo n del grafo se cumple h(n)=0, A* pasa a ser una busca de costo uniforme no informada.


Para asegurar la optimización del algoritmo, la función h(n) ha de ser heurística aceptable, esto es, que no sobrestime el costo real de lograr el nodo objetivo.


De no cumplirse dicha condición, el algoritmo pasa a llamarse sencillamente A, y pese a continuar siendo completo, no se asegura que el resultado logrado sea el camino de costo mínimo. También, si garantizamos que h(n) es consistente (o bien monótona), esto es, que para cualquier nodo n y cualquiera de sus sucesores, el costo estimado de lograr el propósito desde n no es mayor que el de lograr el sucesor más el costo de lograr el propósito desde el sucesor.


Complejidad computacional


La dificultad computacional del algoritmo está íntimamente relacionada con la calidad de la heurística que se utilice en el inconveniente. En el caso peor, con una heurística de pésima calidad, la dificultad va a ser exponencial, al tiempo que en el caso mejor, con una buena h'(n), el algoritmo se ejecutará en tiempo lineal. A fin de que esto último suceda, se debe cumplir que

h'(x)=g(y)-g(x)+h'(y)

donde h' es una heurística inmejorable para el inconveniente, como por servirnos de un ejemplo, el costo real de lograr la meta.


Complejidad en memoria


El espacio requerido por A* para ser ejecutado es su mayor inconveniente. Puesto que debe guardar todos y cada uno de los posibles siguientes nodos de cada estado, la cantidad de memoria que requerirá va a ser exponencial respecto al tamaño del inconveniente. Para solventar este inconveniente, se han propuesto distintas alteraciones de este algoritmo, como pueden ser RTA*, IDA* o bien SMA*.


Implementación en pseudocódigo

.:= . // costo del camino hasta .caso . = . perteneciente a () si g(.) < g(.) entonces // (-----) // nos quedamos con el camino de menor costo .:= MEJORNODO actualizar g(.) y f'(.) extender g a . de . suprimir . incorporar . a ._MEJORNODOcaso . = . perteneciente a )-----( si g(.) < g(.) entonces // nos quedamos con el camino de menor costo .:= MEJORNODO actualizar g(.) y f'(.) suprimir . agregar . a ._MEJORNODOcaso . no estaba en ).( ni (.) incorporar . a ).( agregar . a ._MEJORNODO f'(.) := g(.) + h'(.)

Implementación en pseudocódigo =

ABIERTOS := //inicialización CERRADOS := f'(INICIAL) := h'(INICIAL) reiterar si ABIERTOS = entonces FALLO si no // quedan nodos extraer MEJORNODO de ABIERTOS con f' mí­nima // cola de prioridad desplazar MEJORNODO de ABIERTOS a CERRADOS si MEJORNODO contiene estado_objetivo entonces SOLUCION_ENCONTRADA := TRUE si no producir SUCESORES de MEJORNODO para cada SUCESOR hacer TRATAR_SUCESOR hasta SOLUCION_ENCONTRADA o bien FALLO

Tratar sucesor

SUCESOR.ANTERIOR := VIEJO // costo 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 costo VIEJO.ANTERIOR := MEJORNODO actualizar g(VIEJO) y f'(VIEJO) extender g a sucesores de VIEJO suprimir SUCESOR incorporar VIEJO a SUCESORES_MEJORNODO caso SUCESOR = VIEJO perteneciente a ABIERTOS si g(SUCESOR) < g(VIEJO) entonces // nos quedamos con el camino de menor costo VIEJO.ANTERIOR := MEJORNODO actualizar g(VIEJO) y f'(VIEJO) quitar SUCESOR agregar VIEJO a SUCESORES_MEJORNODO caso SUCESOR no estaba en ABIERTOS ni CERRADOS agregar SUCESOR a ABIERTOS incorporar SUCESOR a SUCESORES_MEJORNODO f'(SUCESOR) := g(SUCESOR) + h'(SUCESOR)

Observaciones


Como se mentó previamente h'(x) es un estimador de h(x) que notifica la distancia al nodo objetivo, entonces


Si h'(x) hace un estimación perfecta de h(x), A* confluye de manera inmediata al objetivo.


Si h'(x) = 0, la función g(x) controla la busca.


Si h'(x) = 0 y g(x) =0 la busca va a ser azarosa.


Si h'(x) = 0 y g(x) =1 o bien incesante la busca va a ser Primero en Anchura.


Si h'(x) jamás sobrevalora a h(x) (o bien infravalora), se garantiza localizar el camino inmejorable, mas se desaprovecha esmero explorando otras sendas que parecieron buenas.


Si h'(x) sobrevalora a h(x), no puede garantizarse la consecución del camino del menor coste



  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Algoritmo de búsqueda A wiki: info, historia y vídeos

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas