El capitán y el tesoro

De algoritmos de búsquedas

“Mi capitán, mi capitán, la carta que robamos al gobernador no es un mapa, es una hoja blanca con una frase sola: ‘El tesoro está escondido en dos números: 37.16 y -3.58. Solo quien sabrá seguir las grandes estrellas a, llegará a él.’ Mi capitán era toda una trampa, y el gobernador es más embustero que nosotros ¿Qué hacemos ahora?”

El capitán salió al ponte del velero, cerró los ojos unos instantes y dijo: “¡El viejo truco de la estrella A*! Ay gobernador, estas chocheando…”, luego escupió y se rio a carcajadas: “Venga, un lápiz, dos folios, y un sextante que ya viene la noche, latitud 37.16, longitud -3.58 grados… ahí vamos, mi tesorito!”

El algoritmo A* es uno de los mejores métodos de búsqueda de camino para alcanzar un objetivo[1]. En cada coordenada en las que estemos A* decide el próximo movimiento n calculando dos distancias: la que damos hacia la siguiente ubicación en el océano, g(n), y la distancia de esta última al tesoro/objetivo, h(n). Al no tener un mapa detallado, sino solo las coordenadas del tesoro, h(n) será una función heurística que da solo una estimación de la distancia real[2].

Semanas después

“Capitán, mi capitán, necesitamos actualizar la lista de coordenadas…”

“Otra vez! Una y otra y otra… y OTRA MALDITA VEZ…”- El capitán reduce el ultimo pergamino a una pelota arrugada, con furia la lanza al mar…

“Quemad todas las listas”, dice con voz muy grave – “pero mi capitán llevamos dos lunas calculando coordenadas, ya van muchas hojas…” – “Me vais a explorar todo este charco de océano, TODO! Sacad todas las lanchas. Un equipo de ocho, cada uno con una tabla flotadora, en cada lancha: 15 millas en todas las direcciones de la brújula, y una vez ahí cada marinero con su tabla, otras 15 millas, cado uno en una dirección distinta… si no existe un mapa, lo vamos a dibujar a remos y nadando, mis hombres serán mis ojos, será el mejor mapa, el más detallado de siempre…”, el primer oficial tiene una cara pálida, y le tiembla un parpado “¿Que? Son 64 marineros casi toda la tripulación! Mi capitán…” – “TODAS LAS LANCHAS AL MAR! YA!”

En términos de performance en algunos casos los algoritmos el Best First Search (BFS)  y Depth First Search (DFS) pueden ganarle mucho tiempo al A*[3].

El algoritmo de búsqueda en anchura (en inglés BFS  o Breadth First Search)[4] es un algoritmo de búsqueda no informada utilizado para recorrer o buscar elementos en un grafo. Intuitivamente, se comienza por un elemento y se exploran todos los vecinos de este nodo. A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol. BFS expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución y no usa ninguna estrategia heurística.

“Mi capitán, y si (por un casual) encontráramos el tesoro… como podremos comunicárselo…” – “Palomas viajeras, cada marinero llevará sextante, prismático y una paloma viajera, para avisar el compañero de la lancha, que a su vez avisará con otra paloma mi nave…”- demasiados días aquí perdidos, escasea agua y comida, demasiado sol, esto pinta mal, la locura del capitán…

Una Búsqueda en Profundidad (en inglés DFS o Depth First Search)[5] es un algoritmo de búsqueda no informada utilizado para recorrer todos los nodos de un grafo de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.

“necesitaríamos mucha suerte mi capitán…” – “Para mí o para ustedes?” – “Para todos me temo…”[6]

BFS usa una lista simple mientras que A* usa una lista con prioridad. En general, las listas son mucho más rápidas que las listas prioritarias. La ventaja de A* es que normalmente expande muchos menos nodos que BFS, pero si ese no es el caso, BFS será más rápido. Eso puede suceder si la heurística utilizada es deficiente, o si el gráfico es muy escaso o pequeño, o si la heurística falla para un gráfico determinado.

Por su parte DFS puede ser más rápido de A* y BFS si el objetivo está en la primera rama, o primera iteración del grafo.

Meses después

“Mi capitán, ha llegado la última paloma, sin ningún mensaje, como las demás, me temo que perdimos a todos nuestros hombres… mi capitán?” El capitán, ebrio de whisky solo puede gruñir y en estado semiconsciente tiene un sueño:

Todos sus tripulantes se han transformado en gaviotas, formando una enorme bandada, una nube que explora todo el océano esquiva islas y rocas, entra ágilmente en cañones. Los pájaros con una simple mirada se comunican uno a otro, y la bandada cambia forma y velocidad a la ocasión: es uno único ser poderoso, incansable e indestructible. Y llegará a hallar el tesoro…

Desde la perspectiva de la modelización matemática, el «flocking» es el movimiento colectivo de un gran número de entidades autopropulsadas y es un comportamiento animal colectivo exhibido por muchos seres vivos como pájaros, peces, bacterias e insectos. Está considerado un comportamiento emergente que surge de reglas sencillas que siguen los individuos y no implica ningún tipo de coordinación central.

Los modelos básicos del comportamiento «flocking» se controlan a través de tres sencillas reglas:

  • Separación – evitar aglomeración de vecinos.
  • Alineación – dirigir hacia un rubro promedio de vecinos.
  • Cohesión – dirigir hacia la posición media de los vecinos.

Con estas tres reglas sencillas, a través del feedback que cada individuo tiene sobre posición y velocidad de sus vecinos, la bandada se mueve de una manera extremadamente realista, creando movimiento complejo y una interacción que sería extremadamente difícil de crear de otra manera[7].

Mediante los algoritmos de flockings es posible resolver problemas de búsquedas de caminos que no sería posible resolver con el algoritmo A*. Dos ejemplos son la búsqueda de la salida de emergencia de una muchedumbre en una situación de pánico, o bien la regulación del tráfico peatonal o de vehículos a motor: en ambos casos tenemos muchos agentes con el mismo objetivo, que tienen que moverse en un entorno con obstáculos fijos y móviles, i.e. los otros agentes.

Cuando el capitán Achab se asomó al puente de la nave lo vio, a menos de una milla: en la alucinación del último día de su vida el gran baúl estaba encima de una gran ballena plateada, que en realidad era el reflejo de la luz en una enorme nube a ras del mar. “¡Serás mío por fin! ¡No te escapes!” y se echó al mar nadando con todas sus fuerzas hacía el. No sabía que un solo capitán, aunque con mucha experiencia, nada puede para capturar una ballena.

En la resolución del problema de la captura en un laberinto mediante las ecuaciones de Hamilton Jacobi, un formalismo matemático que podría considerarse como la versión continua del algoritmo de Dijkstra, el padre del A*[8], se puede demonstrar que si hay solo un agente perseguidor y perseguidor y huyente tienen la misma velocidad, y por lo tanto no es posible la captura. Para mencionar un ejemplo curioso, aplicando el formalismo de Hamilton Jacobi a Pacman, el celebre videojuego de los años 80, Pacman (o la ballena) siempre conseguirá escaparse si hay un solo fantasma (o capitán), porqué ballena y capitán pueden entrar en un recorrido circular cerrado. Por otra parte a partir de dos perseguidores, la ballena será capturada[9].


[1] https://www.lanshor.com/pathfinding-a-estrella/

[2] Para la distancia real necesitaríamos el mapa, con la descripción de islas y rocas, i.e. los obstáculos, y de las corrientes de viento, que nos indican las trayectorias más rápidas.

[3] https://stackoverflow.com/questions/9511118/is-a-the-best-pathfinding-algorithm

[4] https://es.wikipedia.org/wiki/B%C3%BAsqueda_en_anchura

[5] https://es.wikipedia.org/wiki/B%C3%BAsqueda_en_profundidad

[6] https://stackoverflow.com/questions/49912983/in-what-cases-would-bfs-and-dfs-be-more-efficient-than-a-search-algorithm

[7] https://gamedev.stackexchange.com/questions/130114/reconciling-flocking-and-a-theory

[8] https://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra

[9] http://ricerca.matfis.uniroma3.it/users/cacace/PacmanHJ/ https://www.math.unipd.it/~motta/slides%20conv.%20PD%2017/cacace.pdf

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *