stringtranslate.com

Serpiente en la caja

Dibujo de una serpiente en un hipercubo tridimensional .

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

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 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

  1. ^ 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

Enlaces externos