El problema de la serpiente en la caja en la teoría de grafos y la ciencia de la computación trata de encontrar un cierto tipo de camino a lo largo de los bordes de un hipercubo . Este camino comienza en una esquina y recorre los bordes hasta tantos rincones como pueda alcanzar. Después de llegar a un nuevo rincón, el rincón anterior y todos sus vecinos deben marcarse como inutilizables. El camino nunca debe llegar a un rincón que haya sido marcado como inutilizable.
En otras palabras, una serpiente es un camino abierto conectado en el hipercubo donde cada nodo conectado con el camino, con la excepción de la cabeza (inicio) y la cola (final), tiene exactamente dos vecinos que también están en la serpiente. La cabeza y la cola tienen cada una solo un vecino en la serpiente. La regla para generar una serpiente es que un nodo en el hipercubo puede ser visitado si está conectado al nodo actual y no es vecino de ningún nodo visitado previamente en la serpiente, excepto el nodo actual.
En la terminología de la teoría de grafos, esto se denomina encontrar la ruta inducida más larga posible en un hipercubo ; puede considerarse un caso especial del problema de isomorfismo de subgrafos inducidos . Existe un problema similar de búsqueda de ciclos inducidos largos en hipercubos, llamado el problema de la bobina en la caja .
El problema de la serpiente en la caja fue descrito por primera vez por Kautz (1958), motivado por la teoría de los códigos de corrección de errores . Los vértices de una solución a los problemas de la serpiente o la bobina en la caja se pueden utilizar como un código Gray que puede detectar errores de un solo bit. Dichos códigos tienen aplicaciones en ingeniería eléctrica , teoría de codificación y topologías de redes informáticas . En estas aplicaciones, es importante idear un código lo más largo posible para una dimensión dada del hipercubo . Cuanto más largo sea el código, más efectivas serán sus capacidades.
Encontrar la serpiente o espiral más larga se vuelve notoriamente difícil a medida que aumenta el número de dimensión y el espacio de búsqueda sufre una grave explosión combinatoria . Algunas técnicas para determinar los límites superior e inferior del problema de la serpiente en la caja incluyen demostraciones que utilizan matemáticas discretas y teoría de grafos , búsqueda exhaustiva del espacio de búsqueda y búsqueda heurística utilizando técnicas evolutivas.
Longitudes y límites conocidos
La longitud máxima para el problema de la serpiente en la caja se conoce para las dimensiones uno a ocho; es
1, 2, 4, 7, 13, 26, 50, 98 (secuencia A099155 en la OEIS ).
Más allá de esa longitud, no se conoce la longitud exacta de la serpiente más larga; las mejores longitudes encontradas hasta ahora para las dimensiones nueve a trece son
190, 370, 712, 1373, 2687.
En el caso de los ciclos (el problema de la bobina en la caja), no puede existir un ciclo en un hipercubo de dimensión menor que dos. Las longitudes máximas de los ciclos más largos posibles son
0, 4, 6, 8, 14, 26, 48, 96 (secuencia A000937 en la OEIS ).
Más allá de esa longitud, no se conoce la longitud exacta del ciclo más largo; las mejores longitudes encontradas hasta ahora para las dimensiones nueve a trece son
188, 366, 692, 1344, 2594.
Las bobinas duplicadas son un caso especial: ciclos cuya segunda mitad repite la estructura de su primera mitad, también conocidas como bobinas simétricas . Para las dimensiones dos a siete, las longitudes de las bobinas duplicadas más largas posibles son
4, 6, 8, 14, 26, 46.
Más allá de eso, las mejores longitudes encontradas hasta ahora para las dimensiones ocho a trece son
94, 186, 362, 662, 1222, 2354.
Tanto para el problema de la serpiente como para el de la bobina en la caja, se sabe que la longitud máxima es proporcional a 2 n para una caja de dimensión n , de manera asintótica a medida que n aumenta, y limitada por encima por 2 n − 1 . Sin embargo, no se conoce la constante de proporcionalidad, pero se observa que está en el rango de 0,3 a 0,4 para los mejores valores conocidos actuales. [1]
Notas
^ Para límites inferiores asintóticos, véase Evdokimov (1969), Wojciechowski (1989) y Abbot & Katchalski (1991). Para límites superiores, véase Douglas (1969), Deimer (1985), Solov'eva (1987), Abbot & Katchalski (1988), Snevily (1994) y Zémor (1997).
Referencias
Abbot, HL; Katchalski, M. (1988), "Sobre el problema de la serpiente en la caja", Journal of Combinatorial Theory, Serie B , 45 : 13–24, doi : 10.1016/0095-8956(88)90051-2
Abbot, HL; Katchalski, M. (1991), "Sobre la construcción de códigos de serpiente en la caja", Utilitas Mathematica [fr] , 40 : 97–116
Allison, David; Paulusma, Daniel (2016), Nuevos límites para el problema de la serpiente en la caja , arXiv : 1603.05119 , Bibcode :2016arXiv160305119A
Bitterman, DS (2004), Nuevos límites inferiores para el problema de la serpiente en la caja: un algoritmo genético Prolog y un enfoque de búsqueda heurística (PDF) (tesis de maestría), Departamento de Ciencias de la Computación, Universidad de Georgia
Blaum, Mario; Etzion, Tuvi (2002), Uso de códigos de serpiente en la caja para la identificación confiable de pistas en campos servo de una unidad de disco , patente estadounidense 6.496.312
Casella, DA; Potter, WD (2005), "Uso de técnicas evolutivas para cazar serpientes y espirales", Congreso IEEE sobre computación evolutiva de 2005 (CEC2005) , vol. 3, págs. 2499–2504
Casella, DA (2005), Nuevos límites inferiores para los problemas de la serpiente en la caja y la bobina en la caja (PDF) (tesis de maestría), Departamento de Ciencias de la Computación, Universidad de Georgia
Danzer, L.; Klee, V. (1967), "Longitud de las serpientes en cajas", Journal of Combinatorial Theory , 2 (3): 258–265, doi : 10.1016/S0021-9800(67)80026-7
Davies, DW (1965), "Caminos y bucles 'separados' más largos en un cubo N ", IEEE Transactions on Electronic Computers , EC-14 (2): 261, doi :10.1109/PGEC.1965.264259
Deimer, Knut (1985), "Un nuevo límite superior para la longitud de las serpientes", Combinatorica , 5 (2): 109–120, doi :10.1007/BF02579373, S2CID 30303683
Diaz-Gomez, PA; Hougen, DF (2006), "El problema de la serpiente en la caja: conjetura matemática y un enfoque de algoritmo genético", Actas de la 8.ª Conferencia sobre Computación Genética y Evolutiva , Seattle, Washington, EE. UU., págs. 1409-1410, doi :10.1145/1143997.1144219, S2CID 19239490{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
Douglas, Robert J. (1969), "Límites superiores de la longitud de circuitos de dispersión uniforme en el cubo d ", Journal of Combinatorial Theory , 7 (3): 206–214, doi : 10.1016/S0021-9800(69)80013-X
Evdokimov, AA (1969), "Longitud máxima de una cadena en un cubo unitario de n dimensiones", Matematicheskie Zametki , 6 : 309–319
Kim, S.; Neuhoff, DL (2000), "Códigos Snake-in-the-box como asignaciones de índices de cuantificadores robustos", Actas del Simposio Internacional IEEE sobre Teoría de la Información , pág. 402, doi :10.1109/ISIT.2000.866700, ISBN 0-7803-5857-0, Número de identificación del sujeto 122798425
Kinny, D. (2012), "Un nuevo enfoque para el problema de la serpiente en la caja", Actas de la 20.ª Conferencia Europea sobre Inteligencia Artificial, ECAI-2012, págs. 462-467
Kinny, D. (2012), "Búsqueda de serpientes y espirales en Montecarlo", Actas de la 6.ª Semana Mundial Internacional sobre Tendencias Multidisciplinarias en Inteligencia Artificial, MIWAI-2012, págs. 271-283
Klee, V. (1970), "¿Cuál es la longitud máxima de una serpiente de dimensión d ?", American Mathematical Monthly , 77 (1): 63–65, doi :10.2307/2316860, JSTOR 2316860
Kochut, KJ (1996), "Códigos de serpiente en la caja para dimensión 7", Journal of Combinatorial Mathematics and Combinatorial Computing , 20 : 175–185
Lukito, A.; van Zanten, AJ (2001), "Un nuevo límite superior no asintótico para códigos de serpiente en la caja", Journal of Combinatorial Mathematics and Combinatorial Computing , 39 : 147–156
Paterson, Kenneth G.; Tuliani, Jonathan (1998), "Algunos códigos de circuitos nuevos", IEEE Transactions on Information Theory , 44 (3): 1305–1309, doi :10.1109/18.669420
Potter, WD; Robinson, RW; Miller, JA; Kochut, KJ; Redys, DZ (1994), "Uso del algoritmo genético para encontrar códigos de serpientes en la caja", Actas de la Séptima Conferencia Internacional sobre Aplicaciones Industriales y de Ingeniería de Inteligencia Artificial y Sistemas Expertos , Austin, Texas, EE. UU., págs. 421–426{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
Snevily, HS (1994), "El problema de la serpiente en la caja: un nuevo límite superior", Discrete Mathematics , 133 (1–3): 307–314, doi : 10.1016/0012-365X(94)90039-6
Solov'eva, FI (1987), "Un límite superior en la longitud de un ciclo en un cubo unitario de n dimensiones", Metody Diskretnogo Analiza (en ruso), 45 : 71–76, 96–97
Tuohy, DR; Potter, WD; Casella, DA (2007), "Búsqueda de códigos de serpiente en la caja con modelos de poda evolucionados", Actas de la Conferencia internacional de 2007 sobre métodos genéticos y evolutivos (GEM'2007) , Las Vegas, Nevada, EE. UU., págs. 3-9{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
Wojciechowski, J. (1989), "Un nuevo límite inferior para los códigos de serpiente en la caja", Combinatorica , 9 (1): 91–99, doi :10.1007/BF02122688, S2CID 9450370
Yang, Yuan Sheng; Sun, Fang; Han, Song (2000), "Un algoritmo de búsqueda hacia atrás para el problema de la serpiente en la caja", Journal of the Dalian University of Technology , 40 (5): 509–511
Zémor, Gilles (1997), "Un límite superior para el tamaño de la serpiente en la caja", Combinatorica , 17 (2): 287–298, doi :10.1007/BF01200911, S2CID 1287549
Zinovik, I.; Kroening, D.; Chebiryak, Y. (2008), "Cálculo de códigos Gray combinatorios binarios mediante búsqueda exhaustiva con solucionadores SAT", IEEE Transactions on Information Theory , 54 (4): 1819–1823, doi :10.1109/TIT.2008.917695, hdl : 20.500.11850/11304 , S2CID 2854180
Enlaces externos
Kinny, David (2012), Página de investigación sobre la serpiente en la caja (Universidad de Kioto)