18 episodios
01:49:52Habla: Juan Carlos Gil
↗

Búsqueda · 19 momentos en 9 episodios

Sara RobiscoJuan Carlos GilHéctor SocasGastón Giribetmétodos sistemáticos laberintos mano derechaalgoritmo mano izquierda para laberintoslaberinto conexo salida exteriorbúsqueda profundidad encrucijadabúsqueda anchura encrucijadamétodos heurísticos estrategia predefinidaolfato gandalf moriaalgoritmos búsqueda árboles juan carlosbúsqueda en profundidad árbolesbúsqueda en anchura árbolesfabio bueno método olfatométodo heurístico para laberintosevaluar esfuerzo en laberinto gilsumar pasos en laberinto gildistancia euclídea en videojuegoslaberintos cartesianos distancia manhattanpersonajes videojuegos camino óptimonavegación autónoma laberintonavegación autónoma vehículosrobots laberinto pacmandrones repartos mercancíaalgoritmos videojuegos laberintosalgoritmo fantasma personalidadprogramar estrella a mayúscula asteriscolaberintos coleccion artículos referenciasmétodos algorítmicos analógicos laberintosbacterias sara y quimiotaxisgradiente de presión partículas difundenlaberinto bacterias gradiente temperaturabacterias huyendo de sustancia tóxicapropagación de ondas en laberintointerferencia de ondas en encrucijadaonda recorriendo caminos sin salidaJuan Carlos GilPac-ManFabio BuenoMaríaJaguaraEgiptoAmnet Emhat IIIMinotauroEvernoteGandalfMoriaHéctor Socasfigura 4Physical Review Lettersdistancia ManhattanSara RobiscoGran Nube de MagallanesCiclo SolarHeliosismologíaBiblioteca de AlejandríaAbenhacán, el bojarí muerto en su laberintoJorge Luis BorgesYouTubeDavid BowieDentro del laberinto

Métodos algorítmicos analógicos laberintos

Ep499: Quimiotaxis; Laberintos; Heliosismología; Agujeros Negros

13 de febrero de 2025
11 momentos
Con
0:000:301:001:302:002:303:003:18

Juan Carlos Gil menciona su afición por los laberintos y cómo colecciona artículos y referencias sobre ellos, incluyendo métodos algorítmicos y analógicos para resolverlos.

…más pegado; ¿tú sabes dónde está? A ver cómo me explico: la estación de lave, pues pegadito, entonces ahí aún no llega ya el tajo, a no ser que sea una inundación muy muy gorda, no sube, pero sí, es zona de peligro en caso de... ¿Asunto resolver laberintos? Pues hay métodos sistemáticos, quizás los conozcáis, como el de la mano derecha o izquierda, una de las dos, que consiste en colocar la mano sobre una pared del laberinto y avanzar sin despegarla, metiéndote por todos los recovecos; lo cual asegura es un algoritmo que asegura encontrar la salida. Tardará más o menos, siempre que el laberinto sea decente, siempre que sea conexo y que la salida esté en el exterior, no en el medio con un túnel que te salga, porque entonces pues está dando vueltas toda la eternidad. Luego hay métodos como el de la búsqueda en profundidad, que consiste en coger un camino hasta que te estrellas y entonces volver por donde has ido hasta la última encrucijada, marcar un camino y seguir por el siguiente. Y luego la búsqueda en anchura, que no es irte muy lejos de una encrucijada, sino explorar un ratito por cada una e irte cada vez más lejos, algo así parecido. Y luego están los métodos heurísticos, en los que en cada encrucijada eliges un camino basado en una estrategia predefinida, en eso, en una heurística. Hay un método que llaman el del olfato, que se puede usar si tienes conocimiento de hacia dónde está la salida y si tienes acceso al sol. Es el que usó Gandalf en Moria. ¿Ah, sí? Qué chulo. Ante la duda, usa siempre tu nariz, el mediador. De hecho, Juan Carlos, acabas de nombrar los algoritmos de búsqueda en árboles, búsqueda en profundidad, búsqueda en archura y búsqueda turística Y ahora me meto con la estrella, que es mi Fabio Bueno, este del olfato, si sabes que está hacia el norte la salida, pues intenta ir hacia el norte, básicamente No garantiza encontrar la salida, pero si tienes suerte es bastante eficiente Y la estrella, que consiste en usar una heurística, consiste en evaluar todo el laberinto sumando el tiempo o los pasos o el esfuerzo o la cantidad de bocadillos que te has tomado hasta llegar, más una estimación, o sea, hasta cada punto sumas lo que te ha costado, más Una estimación de lo que te queda. Y esa estimación, aunque sea razonablemente mala, garantiza que exploras el laberinto de forma bastante buena. Si sabes dónde está la salida, cosa que ocurre en videojuegos muy a menudo, pues la mera distancia euclídea, así a lo recto, o Manhattan, tipo ya sabéis, los laberintos suelen ser cartesianos, pues es muy buena. La utilizan todos los videojuegos para mover a los personajes, vamos, porque eso, bajo determinadas condiciones bastante poco complicadas garantizan encontrar el camino óptimo. Porque eso, una cosa es salir de un laberinto y otra cosa es encontrar el camino óptimo. Y este tipo de cosas, pues ya os imagináis, no solamente sirve para laberintos, sino para navegación autónoma de Vehículos, como coches, rovers espaciales o incluso robots y, como decía en videojuegos, para ir de un punto a otro, evitando al malo que está en el centro. Para hacer repartos automáticos de mercancía con drones que vayan repartiendo mercancía y tal, la forma óptima. Me estaba preguntando, fíjate que es antiguo ese juego que llevas en la camiseta y los fantasmas tienen que navegar un laberinto para ir hacia ti. Y no es trivial, no es que vayan siguiendo... De eso puedo hablar horas; soy muy friki, de eso puedo hablar horas. Hay un algoritmo ahí de Pac-Man. ¿No? Cada fantasma tiene su algoritmo, tiene su personalidad. Es precioso, pero me lo dejamos para otro día. Otro día, vale, lo apuntamos. Bueno, si sois un poquito friki de la programación, programar en la estrella se suele denotar como una A mayúscula con un asterisco, es súper chulo, es muy bonito y muy agradecido, vamos, que lo ves enseguida. Que soy un poquito friki de los laberintos y que atesoro artículos, referencias, menciones, charlas, cosas sobre laberintos, formas de resolverlo, tanto algorítmicas como analógicas porque hay formas raritas, analógicas, tipo, de resolver estos laberintos. Se pueden clasificar en tres formas. Primero, las que siguen algún tipo de gradiente; por ejemplo, partículas que se difunden siguiendo un gradiente de presión o de temperatura. O nuestras amigas, las bacterias, Sara, que gracias a su quimiotaxis pueden navegar un laberinto; era parecido a lo que explicaba, parecido. Siguiendo gradientes de nutrientes o huyendo, también lo comentabas del estudio anterior: huyendo de una sustancia tóxica o lo que sea. Otra forma analógica es mediante algún tipo de propagación de ondas que recorren el laberinto y van chocando con los caminos sin salida; pueden interferir al irse por dos caminos y volver a confluir en una encrucijada, pueden interferir con otras ondas que se han ido por otros caminos y bueno, pues así acaban encontrando la salida con ondas. Un ejemplo muy chulo que he encontrado preparando este programa es un paper de 1995 en el que usan ondas químicas producidas por la famosa reacción oscilante de Beulosev-Zabotinsky, menos trabalenguamente conocida como la reacción BZ; así alguno es mejor la…
Significado #1 · Palabras #1