El problema de la sincronización del pelotón de fusilamiento es un problema de la informática y los autómatas celulares en el que el objetivo es diseñar un autómata celular que, partiendo de una sola célula activa, finalmente llegue a un estado en el que todas las células estén activas simultáneamente. Fue propuesto por primera vez por John Myhill en 1957 y publicado (con una solución de John McCarthy y Marvin Minsky ) en 1962 por Edward Moore .
Planteamiento del problema
El nombre del problema proviene de una analogía con los pelotones de fusilamiento del mundo real : el objetivo es diseñar un sistema de reglas según el cual un oficial pueda ordenar a un detalle de ejecución que dispare para que sus miembros disparen sus rifles simultáneamente.
Más formalmente, el problema concierne a los autómatas celulares , matrices de máquinas de estados finitos llamadas "células" dispuestas en una línea, de modo que en cada paso de tiempo cada máquina pasa a un nuevo estado en función de su estado anterior y los estados de sus dos vecinos. En la linea. Para el problema del pelotón de fusilamiento, la línea consta de un número finito de celdas, y la regla según la cual cada máquina pasa al siguiente estado debe ser la misma para todas las celdas del interior de la línea, pero las funciones de transición de las dos los puntos finales de la línea pueden diferir, ya que a estas dos celdas les falta un vecino en uno de sus dos lados.
Los estados de cada celda incluyen tres estados distintos: "activo", "inactivo" y "disparando", y la función de transición debe ser tal que una celda que esté inactiva y cuyos vecinos estén inactivos permanezca inactiva. Inicialmente, en el tiempo t = 0 , todos los estados están inactivos excepto la celda del extremo izquierdo (la general), que está activa. El objetivo es diseñar un conjunto de estados y una función de transición de modo que, no importa cuán larga sea la línea de celdas, existe un tiempo t tal que cada celda pasa al estado de activación en el tiempo t , y tal que ninguna celda pertenezca al estado de encendido antes del tiempo t .
Soluciones
La primera solución al FSSP fue encontrada por John McCarthy y Marvin Minsky y fue publicada en Sequential Machines por Moore . Su solución consiste en propagar dos ondas a lo largo de la línea de soldados: una onda rápida y una onda lenta que se mueve tres veces más lenta. La onda rápida rebota en el otro extremo de la línea y se encuentra con la onda lenta en el centro. Las dos ondas luego se dividen en cuatro ondas, una onda rápida y lenta que se mueve en cualquier dirección desde el centro, dividiendo efectivamente la línea en dos partes iguales. Este proceso continúa, subdividiendo la línea hasta que cada división tiene una longitud de 1. En este momento, todos los soldados disparan. Esta solución requiere 3 n unidades de tiempo para n soldados.
Eiichi Goto ( 1962 ) encontró por primera vez una solución que usa una cantidad mínima de tiempo (que es 2 n - 2 unidades de tiempo para n soldados ), pero su solución usó miles de estados. Waksman (1966) mejoró esto a 16 estados, y Balzer (1967) lo mejoró aún más a ocho estados, mientras afirmaba demostrar que no existe una solución de cuatro estados. Peter Sanders descubrió más tarde que el procedimiento de búsqueda de Balzer estaba incompleto, pero logró reafirmar el resultado de inexistencia de cuatro estados a través de un procedimiento de búsqueda corregido. Jacques Mazoyer ( 1987 ) introdujo la mejor solución conocida actualmente, utilizando seis estados . Aún se desconoce si existe una solución de cinco estados.
En las soluciones de tiempo mínimo, el general envía a las señales correctas S 1 , S 2 , S 3 , ..., S i a velocidades 1, 1/3, 1/7, ..., 1 / (2 i −1 - 1) . La señal S 1 se refleja en el extremo derecho de la línea y se encuentra con la señal S i (para i ≥ 2 ) en la celda n / 2 i −1 . Cuando S 1 refleja, también crea un nuevo general en el extremo derecho. Las señales S i se construyen utilizando señales auxiliares, que se propagan hacia la izquierda. Cada segunda vez que una señal se mueve (hacia la derecha), envía una señal auxiliar hacia la izquierda. S 1 se mueve por sí solo a la velocidad 1, mientras que cada una de las señales más lentas se mueve solo cuando recibe una señal auxiliar.
Generalizaciones
El problema de la sincronización del pelotón de fusilamiento se ha generalizado a muchos otros tipos de autómatas celulares, incluidas las matrices de células de dimensiones superiores ( Shinahr 1974 ). También se han considerado variantes del problema con diferentes condiciones iniciales ( Kobayashi y Goldstein 2005 ).
Las soluciones al problema del pelotón de fusilamiento también pueden adaptarse a otros problemas. Por ejemplo, Patrick Fischer ( 1965 ) diseñó un algoritmo de autómata celular para generar los números primos basándose en una solución anterior al problema de sincronización del pelotón de fusilamiento.
Referencias
- Balzer, Robert (1967), "Una solución de tiempo mínimo de 8 estados para el problema de sincronización del pelotón de fusilamiento", Información y control , 10 (1): 22–42, doi : 10.1016 / S0019-9958 (67) 90032-0.
- Fischer, Patrick C. (1965), "Generación de números primos mediante una matriz iterativa en tiempo real unidimensional", Journal of the ACM , 12 (3): 388–394, doi : 10.1145 / 321281.321290.
- Goto, Eiichi (1962), Una solución de tiempo mínimo del problema del pelotón de fusilamiento , Notas del curso de Dittoed para Matemáticas Aplicadas 298, Cambridge, MA: Universidad de Harvard, págs. 52–59. Como lo cita Waksman (1966) .
- Kobayashi, Kojiro; Goldstein, Darin (2005), "Sobre las formulaciones de los problemas de sincronización del pelotón de fusilamiento", Computación no convencional (PDF) , Lecture Notes in Computer Science, 3699 , Springer-Verlag, págs. 157-168, doi : 10.1007 / 11560319_15.
- Mazoyer, Jacques (1987), "Una solución de tiempo mínimo en seis estados para el problema de sincronización del pelotón de fusilamiento", Ciencias de la Computación Teórica , 50 (2): 183-238, doi : 10.1016 / 0304-3975 (87) 90124-1.
- Moore, FR; Langdon, GG (1968), "Un problema de pelotón de fusilamiento generalizado", Información y control , 12 (3): 212-220, doi : 10.1016 / S0019-9958 (68) 90309-4.
- Shinahr, Ilka (1974), "Problema de sincronización del pelotón de fusilamiento bidimensional y tridimensional", Información y control , 24 (2): 163–180, doi : 10.1016 / S0019-9958 (74) 80055-0.
- Waksman, Abraham (1966), "Una solución óptima al problema de sincronización del pelotón de fusilamiento", Información y control , 9 (1): 66–78, doi : 10.1016 / S0019-9958 (66) 90110-0.
enlaces externos
- Weisstein, Eric W. "Problema del pelotón de fusilamiento" . MathWorld .
- Una visualización y explicación de una de las soluciones .