El problema de la serpiente en la caja en la teoría de grafos y la informática se ocupa de encontrar un cierto tipo de camino a lo largo de los bordes de un hipercubo . Este camino comienza en una esquina y viaja a lo largo de los bordes hasta tantas esquinas como pueda alcanzar. Después de llegar a una nueva esquina, la esquina anterior y todos sus vecinos deben marcarse como inutilizables. El camino nunca debe viajar 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, que no sea 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 verse como un caso especial del problema de isomorfismo de subgrafo inducido . Existe un problema similar de encontrar ciclos largos inducidos 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 correctores de errores . Los vértices de una solución a los problemas de la serpiente o la bobina en la caja se pueden usar 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 diseñar un código tan largo como sea posible para una dimensión determinada de hipercubo . Cuanto más largo sea el código, más efectivas serán sus capacidades.
Encontrar la serpiente o bobina 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 explosión combinatoria grave . Algunas técnicas para determinar los límites superior e inferior para el 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 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
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
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.
Las bobinas dobladas 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 dobladas 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 n- dimensional, asintóticamente a medida que n crece, y delimitada por arriba 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 valores más conocidos actuales. [1]
Notas
- ↑ Para límites inferiores asintóticos, ver 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) , Snefully (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 , 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), New Lower Bounds for the Snake-In-The-Box Problem: A Prolog Genetic Algorithm and Heuristic Search Approach (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 de 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 2005 sobre Computación evolutiva (CEC2005) , 3 , págs. 2499-2504
- Casella, DA (2005), Nuevos límites inferiores para los problemas de Snake-in-the-Box y Coil-in-the-Box (PDF) (tesis de maestría), Departamento de Ciencias de la Computación, Universidad de Georgia
- Danzer, L .; Klee, V. (1967), "Longitud de serpientes en cajas", Journal of Combinatorial Theory , 2 (3): 258-265, doi : 10.1016 / S0021-9800 (67) 80026-7
- Davies, DW (1965), "Rutas 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
- 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 8ª Conferencia sobre Computación Genética y Evolutiva , Seattle, Washington, EE. UU., Págs. 1409–1410, doi : 10.1145 /1143997.1144219
- Douglas, Robert J. (1969), "Límites superiores de la longitud de los 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 n- dimensional", Matematicheskie Zametki , 6 : 309–319
- Kautz, William H. (junio de 1958), "Códigos de verificación de errores de distancia unitaria", Transacciones IRE en computadoras electrónicas , EC-7 (2): 179–180, doi : 10.1109 / TEC.1958.5222529 , S2CID 26649532
- Kim, S .; Neuhoff, DL (2000), "Códigos Snake-in-the-box como asignaciones de índices cuantificadores robustos", Actas del Simposio Internacional IEEE sobre Teoría de la Información , p. 402, doi : 10.1109 / ISIT.2000.866700
- 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), "Monte-Carlo Search for Snakes and Coils", Actas de la sexta WS 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 d- dimensional?", American Mathematical Monthly , 77 (1): 63–65, doi : 10.2307 / 2316860 , JSTOR 2316860
- Kochut, KJ (1996), "Códigos Snake-in-the-box 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 circuito nuevos", IEEE Transactions on Information Theory , 44 (3): 1305–1309, doi : 10.1109 / 18.669420
- Potter, WD; Robinson, RW; Miller, JA; Kojut, KJ; Redys, DZ (1994), "Uso del 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 la Inteligencia Artificial y Sistemas Expertos , Austin, Texas, EE. UU., Págs. 421–426
- Snently, 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 longitud de un ciclo en un cubo de unidad n- dimensional", Metody Diskretnogo Analiza (en ruso), 45 : 71-76, 96-97
- Tuohy, DR; Potter, WD; Casella, DA (2007), "Búsqueda de códigos Snake-in-the-Box con modelos de poda evolucionados", Actas del 2007 Int. Conf. sobre métodos genéticos y evolutivos (GEM'2007) , Las Vegas, Nevada, EE. UU., págs. 3–9
- 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
- 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", Revista de la Universidad Tecnológica de Dalian , 40 (5): 509–511
- Zémor, Gilles (1997), "Un límite superior en el tamaño de la serpiente en la caja", Combinatorica , 17 (2): 287–298, doi : 10.1007 / BF01200911
- Zinovik, I .; Kroening, D .; Chebiryak, Y. (2008), "Computación de códigos grises combinatorios binarios a través de una 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
enlaces externos
- Kinny, David (2012). "Página de investigación de Snake-in-the-Box (Universidad de Kyoto)" .
- Potter, WD (2011). "Una lista de registros actuales para el problema de Snake-in-the-Box (UGA)" .
- Weisstein, Eric W. "Serpiente" . MathWorld .