Se entiende por emparejamiento bipartito esa tarea que realizan los sistemas que emparejan a los donantes de órganos con los candidatos a trasplantes, a los estudiantes de medicina con los programas de residencia y a los anunciantes con los espacios publicitarios. Por ello, es objeto de intensos estudios. "Este es probablemente uno de los 10 problemas más famosos en la informática", dice el profesor asociado del Laboratorio Cold Spring Harbor (Estados Unidos), Saket Navlakha.
Ahora, un nuevo trabajo del autor publicado en 'Actas de la Academia Nacional de Ciencias' ha encontrado una forma de hacerlo mejor siguiendo el ejemplo de la biología. En concreto, Navlakha ha reconocido un problema de correspondencia bipartita en el cableado del sistema nervioso. "Es un gran ejemplo de cómo el estudio de los circuitos neuronales puede revelar nuevos algoritmos para problemas importantes de IA", afirma el autor.
PUBLICIDAD
Según el trabajo, en los animales adultos, cada una de las fibras musculares del cuerpo está emparejada con exactamente una neurona que controla su movimiento. Sin embargo, en las primeras etapas de la vida, cada fibra es el objetivo de muchas neuronas. Para que un animal se mueva de manera eficiente, se deben eliminar las conexiones sobrantes. Entonces, ¿qué correspondencias están hechas para durar?
El sistema nervioso tiene una solución eficiente. Navlakha explica que las neuronas que inicialmente están conectadas a la misma fibra muscular compiten entre sí para mantener su correspondencia, utilizando neurotransmisores como recursos de "oferta". Las neuronas que pierden esta subasta biológica pueden tomar sus neurotransmisores y pujar por otras fibras. De esta manera, cada neurona y fibra termina teniendo una pareja.
En este contexto, Navlakha idea una forma de implementar esta estrategia de emparejamiento fuera del sistema nervioso. "Es un algoritmo simple", dice. "Sólo son dos ecuaciones. Una es la competencia entre neuronas conectadas a la misma fibra y la otra es la reasignación de recursos". Probado frente a los mejores programas de emparejamiento bipartito que existen, el algoritmo inspirado en la neurociencia funciona muy bien. Crea emparejamientos casi óptimos y deja menos partes sin emparejar. En aplicaciones cotidianas, eso podría significar tiempos de espera más cortos para los pasajeros de viajes compartidos y menos hospitales sin médicos residentes.
Navlakha señala otra ventaja: el nuevo algoritmo preserva la privacidad. La mayoría de los sistemas de emparejamiento bipartito requieren que la información pertinente se transmita a un servidor central para su procesamiento, pero en muchos casos (desde subastas en línea hasta emparejamiento de órganos de donantes) puede ser preferible un enfoque distribuido. Con innumerables aplicaciones potenciales, Navlakha espera que otros adapten el nuevo algoritmo para sus propias herramientas.
8,7 créditos