Búsqueda A*: pinta muros y mira pensar la frontera
Dibuja un laberinto, desliza de Dijkstra a A* y observa cómo el conjunto abierto persigue la meta hasta que brilla el camino más corto.
La semana pasada un filtro Naive Bayes contó palabras y tiró dados. Esta semana la máquina hace algo más viejo y más afilado: buscar. Sin aprender de datos, sin charlar; solo expandir una frontera de posibilidades hasta que aparece un camino.
A* es el caballo de batalla de mapas de juegos, robótica y puzzles. Mantienes un conjunto abierto de celdas que merece la pena revisitar, puntuadas por distancia recorrida más una heurística hacia la meta. Con una subestimación segura (Manhattan en la cuadrícula) el camino sigue siendo el más corto, pero visitas muchas menos celdas que en una búsqueda a ciegas. Heurística a cero: Dijkstra, óptimo, paciente, un poco derrochador. Eso es IA simbólica clásica: estados explícitos, costes explícitos, un planificador como un agente cuyo razonamiento puedes ver.
Cómo jugar:
- Laberinto genera un mapa aleatorio nuevo en cada clic, o pinta muros (clic otra vez en la misma celda para quitar).
- Mueve Inicio y Meta con los chips de editar.
- Pulsa Buscar y mira abierto vs cerrado; Paso expande un nodo.
- Arrastra Peso heurístico de 1 (A*) a 0 (Dijkstra) y repite en el mismo mapa.
Prueba esto:
- En el mapa por defecto (inicio al centro, meta arriba a la derecha), busca con heurística 1,00: la frontera tira hacia la meta; anota Nodos expandidos (a menudo unos 40).
- Sin mover muros, heurística 0 y otra búsqueda: la ola llena más la cuadrícula; Nodos expandidos suben mucho (a menudo 100+) y Pasos del camino se mantienen.
- Carga Laberinto y compara 1,00 vs 0: Dijkstra debería expandir bastantes más celdas que A* (a menudo ~1,5×).
- Encierra la meta con muros: debe decir que no hay camino.
Por qué importa
Deep Blue ganó al ajedrez buscando millones de posiciones; los sistemas expertos codificaron planificadores en reglas antes de que las redes fueran moda. AlphaGo mezcla aprendizaje y búsqueda (Monte Carlo), pero la intuición empieza aquí: mundo como grafo, puntuar movimientos, expandir lo prometedor. A* es la versión educada que no desperdicia trabajo cuando hay brújula hacia la meta.
¿Perdiste las ediciones anteriores? Perceptrón, Markov, tres en raya, convolución, Q-learning, BPE, gradiente, k-means, red neuronal, atención, bandit, ELIZA, Hopfield o spam Naive Bayes.