¿Qué es un algoritmo?

“Un algoritmo se puede definir como una secuencia de instrucciones que representan un modelo de solución para determinado tipo de problemas” (nordeste, 2006).

Un algoritmo es una lista de operaciones desarrolladas paso a paso. En la vida diaria se hace uso de algoritmo, en una receta de cocina, al leer un manual, bañarse y hasta hacer una limonada se hace uso de un algoritmo.

Algoritmo A*

A* es un algoritmo de búsqueda inteligente o informada que busca el camino más corto desde un estado inicial al estado meta a través de un espacio de problema, usando una heurística óptima. Como ignora los pasos más cortos (más «chatos») en algunos casos rinde una solución subestima. (López, 2007).

Para (Sebastian, 2011) el algoritmo A* se encuentra dentro de los algoritmos de búsqueda. Fue presentado en 1968 por Peter E. Hart, Nils  J. Nilsson y Bertram Raphael, con el objetivo que el algoritmo A*  pudiera ser usado para encontrar la ruta más cercana para ir de un lugar a otro.

Un algoritmo de búsqueda permite localizar un elemento desde un punto de inicio hasta el lugar de destino. A* es considerado una instancia del algoritmo primero el mejor. Su método es identificado como heurista de búsqueda.

¿Qué es una heurista de búsqueda?

La heurista es un método de lectura caracterizado por análisis de algoritmo de anchura y profundidad. El método de búsqueda de anchura o conocido comúnmente por amplitud es una estrategia para la búsqueda en un grafo que sostiene dos operaciones básicas:

  • La visita e inspección de un nodo de un gráfico.
  •  El acceso a visitar los nodos de los vecinos del nodo actualmente visitado.

La búsqueda por profundidad es el algoritmo que permite el desplazamiento de las estructuras de los datos iniciando desde la raíz o punto de inicio explorando a cada rama para poder realizar el siguiente paso  hasta llegar al punto destino  ( Intriago, 2014).

Estructura de datos auxiliares

(Malagón, 2013) considera que el algoritmo de A* sostiene dos mecanismos de datos auxiliares, las listas abiertas y las listas cerradas.

Los nodos de lista abierta son nodos que se les ha aplicado la función heurísta pero que aún están en espera de ser examinados.

Los nodos de lista cerrada son todos que ya han pasado por la fase de exploración, su papel principal es para verificar si ya han sido usado, de ser así buscar otro nodo de exploración.

¿Cuándo se debe parar en hacer una búsqueda?

Cuando se expanda el nodo correspondiente a la solución.

Fórmula:

F(n) = g(n) + h(n)

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.

Algoritmo en pseudocódigo

Ejercicio

El siguiente ejercicio explica de forma detalla la estructura de el algoritmo A*.

Ciclo 8: El nodo más prometedor de ABIERTA es Z, que es seleccionado para su expansión. ABIERTA: B (1+20) CERRADA: A, D, E, F, C, G, Z Al ser Z un nodo meta, finaliza el algoritmo. El camino encontrado es A → C → G → Z.

Video de retroalimentación



Bibliografía

Intriago, J. A. (09 de Octubre de 2014). Inteligencia artificial avanzada. Obtenido de https://advanceintelligence.wordpress.com/2014/10/09/heuristica/

López, B. (16 de Marzo de 2007). ALGORTIMO A*. Obtenido de http://www.itnuevolaredo.edu.mx/takeyas/Apuntes/Inteligencia%20Artificial/Apuntes/tareas_alumnos/A-Star/A-Star(2005-II-A).pdf

Malagón, C. (25 de Marzo de 2013). Búsqueda heurística. Obtenido de https://www.nebrija.es/~cmalagon/ia/transparencias/busqueda_heuristica.pdf

nordeste, U. n. (19 de Mayo de 2006). Obtenido de http://ing.unne.edu.ar/pub/informatica/Alg_diag.pdf

Sebastian. (14 de Agosto de 2011). Datos en abierto. Obtenido de https://datosenabierto.wordpress.com/2011/08/14/implementacion-algoritmo-a-estrella-definicion/

Fuente del ejercicio de ejemplo:

file:///F:/A%20estrella.pdf