Cantos de rana y planificación de horarios

Algoritmos basados en animales (III)

Rana arborícola japonesa sobre caracol. Autor: Harfian Herdi.
Rana arborícola japonesa sobre caracol. Autor: Harfian Herdi.

Imaginemos que trabajamos en un aeropuerto y somos los encargados de distribuir la salida de aviones asignándoles puertas de embarque. Queremos utilizar el menor número de puertas posibles para no malgastar recursos, pero hemos de tener en cuenta que los diversos vuelos pueden solaparse (obviamente, esta no sería la situación de aeropuertos como el de Castellón). En la siguiente figura tenemos una posible configuración de vuelos en una franja horaria concreta.

gates

Observa que hay vuelos que coinciden en algún momento concreto; por ejemplo, en el instante marcado por la línea roja los vuelos K429, MI440 y J43 necesitarían una puerta de embarque distinta para no coincidir. Podemos identificar estos solapes con un grafo como el siguiente, en el que dos vuelos se conectan con una línea si coinciden sus necesidades de puertas de embarque en algún momento. Comprueba que este gráfico se corresponde con la figura anterior.

grafo

Para adjudicar puertas de embarque basta con que tengamos en cuenta que a dos nodos cualesquiera de este grafo que estén unidos por una arista no puede asignarse la misma puerta. En lugar de utilizar números para cada puerta de embarque, vamos a identificar estas con colores. De esta forma, nuestro problema se reduce a pintar con el mínimo número de colores (puertas de embarque) el grafo anterior evitando que nodos contiguos (aviones con horarios solapados) tengan el mismo color. Una posible solución sería la siguiente.

grafo2

Este es un problema matemático que se conoce como coloreado de grafos y sus aplicaciones son muy variadas: planificación de horarios, gestión de registros en compilación, organización de rondas de eventos deportivos… Algunas de esas aplicaciones curiosas las ha explicado Clara Grima en algunos de sus artículos, como la distribución de frecuencias en emisoras de radio, coloreado de mapas y la resolución de sudokus.

El problema general de la coloración de grafos no es nada sencillo. De hecho, es lo que se conoce como un problema NP-completo (mira este vídeo de Fernando Cuartero si te interesa entender qué significa esto), así que se han diseñado varios algoritmos que permiten resolverlo con distinta eficiencia.

Pero, al igual que ocurría en los ejemplos de los dos artículos anteriores de la serie, también la evolución ha encontrado una solución a este problema.

Machos de rana ligando

La rana arborícola japonesa (Hyla japonica) habita en algunas zonas de Japón, Mongolia, China y el sureste de Rusia. Las ranas arborícolas suelen vivir en arbustos y árboles, y han desarrollado ventosas en sus patas para poder adherirse a troncos y tallos. Varios ejemplares de esta especie tuvieron el honor de participar en experimentos sobre comportamiento en microgravedad en la estación espacial MIR.

361px-tree_frog

La reproducción de esta especie tiene lugar en el agua de las charcas y estanques cuando esta está relativamente caliente, por lo que los apareamientos ocurren entre mayo y agosto. Los machos entran primero en el agua y emiten llamadas a las hembras con notas que duran una o dos décimas de segundo a intervalos de 0.2-0.5 segundos. Las hembras se basan en este sonido para elegir al macho con que aparearse.

ranas1
Dos machos emiten señales sonoras con distintas características (las ondas son ficticias).

En el siguiente vídeo puede escucharse el croar de apareamiento de los machos de esta especie.

Pero los machos se encuentran con un problema a la hora de hacerse oír por las hembras: si hay varios individuos cercanos entre sí y emiten sus cantos en la misma fase, las hembras son incapaces de distinguir entre los machos ya que los sonidos se solapan total o parcialmente.

ranas2

La evolución ha encontrado una solución a este problema, dotando a los machos de la capacidad de separar las fases de sus cantos de los machos vecinos, de forma que las hembras sí que son capaces de diferenciarlos y localizar al macho con el que les interesa aparearse. En términos físicos se dice que han logrado «desincronizar» sus cantos. De hecho, existe un modelo que predice esta desincronización basándose en osciladores acoplados .

ranas3

Si dibujáramos un grafo en el que cada nodo fuera un macho de rana arborícola japonesa y conectáramos con aristas los machos que están lo suficientemente cerca como para que las hembras confundieran sus croares, podríamos decir que cada macho ha aprendido a  «pintarse de un color» (cambiar la fase de su canto) distinto del de sus vecinos, por lo que estarían resolviendo el problema del coloreado de grafos.

Un equipo de investigadores de la Universidad de País Vasco y la Universidad Politécnica de Cataluña ha desarrollado recientemente un algoritmo para colorear grafos basándose en la desincronización de los machos de las ranas arborícolas japonesas. Para ello, asignan a cada nodo del grafo un «oscilador» acoplado con los nodos a los que está enlazado, y se varía la fase del oscilador en sucesivas iteraciones. Al final, se converge a una situación en la que cada nodo tiene una fase distinta a la de sus vecinos, y el número de fases utilizado es mínimo. Basta con asignar un color a cada una de las fases y problema resuelto.

Una modificación de este algoritmo por parte de los mismo autores también se ha aplicado a la resolución del conjunto independiente maximal de un grafo, cuya resolución utilizando el desarrollo del sistema nervioso de la mosca de la fruta se explicó en el anterior artículo de la serie.

Más información

2 Comentarios

Participa Suscríbete

DinoperturbadoDinoperturbado

Interesante pero corto artículo ;P
Algo que corregir, cuando dices “Pero, al igual que ocurría en los ejemplos de los dos artículos anteriores de la serie, también la evolución ha encontrado una solución a este problema” deberías poner: La evolución YA lo resolvió y los humanos le copiamos XD
Aparte de todos los nombres rocambolescos de osciladores desincronizados acoplados blah blah ¿esto no sería un ejemplo de multiplexación en el tiempo?.

Guillermo Peris Ripollés

Algo que corregir, amigo Dinoperturbado. Cuando dices “La evolución YA lo resolvió y los humanos le copiamos” te ha faltado añadir “…y lo mejoramos”.

La pregunta de la multiplexación se la paso a Francis XDD

1 Trackback

Información Bitacoras.com

Valora en Bitacoras.com: Algoritmos basados en animales (III) Rana arborícola japonesa sobre caracol. Autor: Harfian Herdi. Imaginemos que trabajamos en un aeropuerto y somos los encargados de distribuir la salida de aviones asignándoles puertas de…

Deja un comentario

Tu email nunca será mostrado o compartido. No olvides rellenar los campos obligatorios.

Obligatorio
Obligatorio

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>