Dibujo de una serpiente en un hipercubo tridimensional .
El problema de la serpiente en la caja en teoría de grafos e informática 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 tantas esquinas como pueda alcanzar. Después de llegar a una nueva esquina, la esquina anterior y todas sus vecinas deben marcarse como inutilizables. El camino nunca debe llegar a una esquina que haya sido marcada 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 un solo vecino en la serpiente. La regla para generar una serpiente es que se puede visitar un nodo en el hipercubo 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 llama encontrar el camino inducido más largo posible en un hipercubo ; Puede verse como un caso especial del problema del isomorfismo de subgrafos inducido . Existe un problema similar al encontrar ciclos inducidos largos en hipercubos, llamado 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. Estos 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 diseñar un código lo más largo posible para una dimensión determinada del hipercubo . Cuanto más largo sea el código, más efectivas serán sus capacidades.
Encontrar la serpiente o la espiral más larga se vuelve notoriamente difícil a medida que aumenta el número de dimensiones 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 pruebas que utilizan matemáticas discretas y teoría de grafos , búsqueda exhaustiva del espacio de búsqueda y búsqueda heurística que utiliza técnicas evolutivas.
Longitudes y límites conocidos
Longitudes máximas de serpientes ( L s ) y bobinas ( L c ) en el problema de las serpientes en la caja para dimensiones n de 1 a 4
La longitud máxima para el problema de la serpiente en la caja se conoce para las dimensiones del uno al ocho; es
1, 2, 4, 7, 13, 26, 50, 98 (secuencia A099155 en el OEIS ).
Más allá de esa longitud, se desconoce 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.
Para los ciclos (el problema de la bobina en la caja), un ciclo no puede existir 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 el OEIS ).
Más allá de esa duración, se desconoce la duración exacta del ciclo más largo; las mejores longitudes encontradas hasta ahora para las dimensiones nueve a trece son
188, 366, 692, 1344, 2594.
Un caso especial son las bobinas duplicadas : ciclos cuya segunda mitad repite la estructura de su primera mitad, también conocidas como bobinas simétricas . Para las dimensiones del dos al 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 los problemas de la serpiente como de la bobina en la caja, se sabe que la longitud máxima es proporcional a 2 n para una caja de n dimensiones, asintóticamente a medida que n crece y está acotada arriba por 2 n − 1 . Sin embargo, se desconoce la constante de proporcionalidad, pero se observa que está en el rango de 0,3 a 0,4 para los valores más conocidos actuales. [1]
Notas
^ Para límites inferiores asintóticos, consulte Evdokimov (1969), Wojciechowski (1989) y Abbot & Katchalski (1991). Para los límites superiores, véanse Douglas (1969), Deimer (1985), Solov'eva (1987), Abbot & Katchalski (1988), Snevily (1994) y Zémor (1997).
Referencias
Abad, 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
Abad, 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 de prólogo 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 de EE. UU. 6.496.312
Casella, DA; Potter, WD (2005), "Uso de técnicas evolutivas para cazar serpientes y bobinas", Congreso IEEE de 2005 sobre Computación Evolutiva (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
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
Díaz-Gómez, 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 octava 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 CS1: falta el editor de la ubicación ( enlace )
Douglas, Robert J. (1969), "Límites superiores de la longitud de los circuitos de dispersión uniforme en el d -cube", 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 de serpiente en la caja como asignaciones robustas de índices de cuantificadores", Actas del Simposio internacional IEEE sobre teoría de la información , p. 402, doi :10.1109/ISIT.2000.866700, ISBN 0-7803-5857-0, S2CID 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.
Kinny, D. (2012), "Monte-Carlo Search for Snakes and Coils", Actas de la sexta edición de la WS internacional sobre tendencias multidisciplinarias en inteligencia artificial, MIWAI-2012, págs.
Klee, V. (1970), "¿Cuál es la longitud máxima de una serpiente d -dimensional?", American Mathematical Monthly , 77 (1): 63–65, doi :10.2307/2316860, JSTOR 2316860
Kochut, KJ (1996), "Códigos de serpiente en la caja para la 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), "Utilizando el algoritmo genético para encontrar códigos de serpiente 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.{{citation}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace )
Snevily, HS (1994), "El problema de la serpiente en la caja: un nuevo límite superior", Matemáticas discretas , 133 (1–3): 307–314, doi : 10.1016/0012-365X(94)90039- 6
Solov'eva, FI (1987), "Un límite superior en la duración 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 tipo serpiente en la caja con modelos de poda evolucionados", Actas del informe internacional de 2007. Conf. sobre métodos genéticos y evolutivos (GEM'2007) , Las Vegas, Nevada, EE. UU., págs. 3–9{{citation}}: Mantenimiento CS1: falta el editor de la ubicación ( 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; Sol, Colmillo; Han, Song (2000), "Un algoritmo de búsqueda hacia atrás para el problema de la serpiente en la caja", Revista de la Universidad Tecnológica de Dalian , 40 (5): 509–511
Zémor, Gilles (1997), "Un límite superior del 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 grises 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 Snake-in-the-Box (Universidad de Kioto)
