Algoritmo A* Explicado | Ejemplo resuelto de búsqueda A*

Contenido

1. Introducción 🌟
2. ¿Qué es el algoritmo A*? 🧠
3. Ejemplo de búsqueda A* ✍️
4. Cálculo de la función F 📈
5. Listas de nodos abiertos y cerrados 📋
6. Selección del mejor nodo 💡
7. Obtener sucesores y cálculo de valores 🔄
8. Agregar sucesores a la lista abierta 📥
9. Verificar si el nodo objetivo ha sido encontrado 🎯
10. Retroceder y seguir el camino 🚶‍♂️

1. Introducción 🌟

En este video vamos a discutir el algoritmo de búsqueda A* en inteligencia artificial. Veremos cómo funciona utilizando un ejemplo resuelto. ¡Empecemos!

2. ¿Qué es el algoritmo A*? 🧠

El algoritmo A* es un algoritmo de búsqueda heurística utilizado para encontrar el camino más corto entre un nodo inicial y un nodo objetivo. Combina el costo real de llegar a un nodo (g) y una estimación heurística del costo restante hasta el objetivo (h). La función F se utiliza para evaluar y seleccionar los nodos a expandir.

3. Ejemplo de búsqueda A* ✍️

Consideremos el siguiente ejemplo. Tenemos un grafo con nodos etiquetados de la siguiente manera:

• S: Nodo inicial (costo real: 0, costo heurístico: 10)
• A, B, C, D, E, F, G, H: Nodos intermedios
• E: Nodo objetivo

El objetivo es encontrar el camino más corto desde S hasta E utilizando el algoritmo A*.

4. Cálculo de la función F 📈

En el algoritmo A*, la función F de un nodo (F(n)) se calcula como la suma del costo real para llegar al nodo (g(n)) y el costo heurístico desde el nodo hasta el objetivo (h(n)). Esto se expresa como F(n) = g(n) + h(n).

5. Listas de nodos abiertos y cerrados 📋

El algoritmo A* utiliza dos listas: una lista abierta (open) y una lista cerrada (closed). La lista abierta contiene los nodos visitados pero no expandidos, mientras que la lista cerrada contiene los nodos ya visitados. Inicialmente, la lista cerrada está vacía y la lista abierta contiene solo el nodo inicial.

6. Selección del mejor nodo 💡

En cada iteración, se selecciona el mejor nodo de la lista abierta para expandir. El mejor nodo es aquel que tiene el valor F más bajo. Si hay varios nodos con el mismo valor F, se selecciona el primero en la lista.

7. Obtener sucesores y cálculo de valores 🔄

Una vez seleccionado el mejor nodo, se generan sus sucesores. Para cada sucesor, se calcula el valor G sumando el costo real desde el nodo inicial hasta el sucesor. Luego, se calcula el valor F sumando G y el costo heurístico desde el sucesor hasta el objetivo.

8. Agregar sucesores a la lista abierta 📥

Los sucesores se agregan a la lista abierta si no están presentes ni en la lista abierta ni en la lista cerrada. Además, se marca el nodo padre para poder rastrear el camino al nodo objetivo.

9. Verificar si el nodo objetivo ha sido encontrado 🎯

Después de agregar los sucesores a la lista abierta, se verifica si alguno de ellos es el nodo objetivo. Si es el caso, se ha encontrado el camino más corto y se finaliza el algoritmo.

10. Retroceder y seguir el camino 🚶‍♂️

Si el nodo objetivo no ha sido encontrado y aún hay nodos en la lista abierta, se repiten los pasos anteriores. Una vez finalizado el algoritmo, se puede retroceder desde el nodo objetivo hasta el nodo inicial siguiendo los nodos padres marcados en cada iteración.

¡Y eso es todo! Ahora sabes cómo funciona el algoritmo de búsqueda A*. Es una herramienta poderosa para encontrar el camino más corto en problemas de búsqueda en inteligencia artificial. ¡Espero que este video haya sido útil y que lo hayas disfrutado!

¡No olvides darle like, compartirlo con tus amigos y suscribirte para obtener más videos como este! 🔔

Pros y contras del algoritmo A*

Pros:

• Encuentra el camino más corto
• Utiliza una función heurística para mejorar la eficiencia
• Puede ser utilizado en una amplia variedad de problemas de búsqueda

Contras:

• Requiere conocimiento previo del espacio de búsqueda y una heurística adecuada
• No garantiza encontrar el camino óptimo en todos los casos
• Puede ser lento en espacios de búsqueda muy grandes o complejos

Destacados

• El algoritmo A* es una búsqueda heurística utilizada en inteligencia artificial para encontrar el camino más corto desde un nodo inicial hasta un nodo objetivo.
• Combina el costo real de llegar a un nodo y una estimación heurística del costo restante hasta el objetivo.
• La función F se utiliza para evaluar y seleccionar los nodos a expandir.
• El algoritmo utiliza listas abiertas y cerradas para llevar un registro de los nodos visitados y los nodos por visitar.
• Los sucesores se generan para cada nodo y se calculan los valores G y F.
• Se selecciona el mejor nodo de la lista abierta en cada iteración.
• El algoritmo continúa expandiendo nodos hasta encontrar el nodo objetivo.
• Después de encontrar el nodo objetivo, se puede rastrear el camino desde el nodo objetivo hasta el nodo inicial siguiendo los nodos padres marcados en cada iteración.

Preguntas frecuentes

*P: ¿El algoritmo A siempre encuentra el camino más corto?* R: El algoritmo A es óptimo si la heurística utilizada es admisible y consistente. Sin embargo, en algunos casos puede devolver subóptimos o incluso no encontrar solución.

*P: ¿Cuándo se detiene el algoritmo A?* R: El algoritmo A se detiene cuando encuentra el nodo objetivo o cuando no hay más nodos en la lista abierta para expandir.

P: ¿Qué significa que un algoritmo de búsqueda sea heurístico? R: Un algoritmo de búsqueda heurístico utiliza información adicional para guiar la búsqueda hacia soluciones más prometedoras, en lugar de explorar todas las opciones posibles.

Recursos:

• [Link al video en YouTube](insertar aquí el enlace al video)
• [Referencia 1](insertar aquí la referencia 1)
• [Referencia 2](insertar aquí la referencia 2)