¿Qué hay detrás de los algoritmos de búsqueda de Game of Life de Conway?

He estado viendo un programa gfind, que busca naves espaciales en el Juego de la vida de Conway. La documentación dice un montón de cosas sobre la búsqueda de gráficos De-Bruijin. No pude encontrar ninguna información útil sobre estos en Internet, no pude averiguar cómo podrían buscarse y estoy demasiado arruinado para obtener un libro. También revisé el artículo de David Eppstein [1] sobre el tema, pero todavía era demasiado críptico. Solo necesito una explicación a nivel de secundaria (aunque estoy en secundaria O_O) de cómo funciona el algoritmo.

[1] Buscando naves espaciales, David Eppstein http://arxiv.org/abs/cs/0004003

¿Escuela intermedia? Los términos de servicio de StackExchange requieren que tenga 13 años o más.
Tengo 13 años. Además, el artículo de Eppstein está aquí: arxiv.org/abs/cs/0004003
Tu perfil dice que has sido miembro durante un año y un mes... bueno, supongo que está bien ahora.
Todavía no entiendo por qué tanta gente piensa que la edad es una buena medida de la madurez, cuando en realidad es lo peor que existe...
@Qiaochu: ¡Esperó hasta ahora para publicar algo! :-PAG
@DariusGoad: hay diferentes tipos de madurez, algunos de los cuales (como la madurez física) están más correlacionados con la edad que otros. La correlación, por supuesto, no excluye la posibilidad de casos poco frecuentes que parecen contradecir una relación dominante entre factores.
@DariusGoad: No es lo que mucha (o poca) gente piensa sino lo que dice la Ley. Los Términos de servicio se escribieron principalmente teniendo en cuenta la ley. Y aunque puede o no ser una buena medida de madurez, es muy precisa y demostrable.
De todos modos, ¿qué pasa con el tema? La respuesta a eso es un poco lo que estaba buscando.
@Darius: la edad no es una buena medida de la madurez, pero es mucho más fácil de medir que cualquier otra cosa que pueda nombrar, por lo que es mucho más fácil hacer políticas y escribir documentos legales. Según tengo entendido, existen leyes sobre los jóvenes que usan Internet y StackExchange podría tener problemas legales (si no ahora, posiblemente en algún momento en el futuro) si no tuvieran una política de edad. Hay otras preocupaciones aquí además de si la edad es una buena medida de la madurez.

Respuestas (1)

No sé acerca de los algoritmos de búsqueda, pero aquí hay un ejemplo de una secuencia de deBruijn:

1110100011
Tiene la propiedad de que si lees todas las corridas de tres símbolos consecutivos, obtienes
111 110 101 010 100 000 001 011
lo que quiere decir que obtienes todos los triples posibles de símbolos. Más generalmente, una secuencia de orden de deBruijn k por una lengua de s símbolos es una cadena de símbolos de un alfabeto de s símbolos tales que las carreras de k los símbolos consecutivos le dan todas las cadenas posibles de k símbolos de ese alfabeto.

Los gráficos entran en él de la siguiente manera (por cierto, estos son los gráficos que se estudian en combinatoria, no los gráficos que se estudian en geometría analítica): haz un gráfico cuyos vértices sean todas las cadenas de k − 1 símbolos (entonces, en nuestro ejemplo, los vértices son 00, 01, 10 y 11) y tienen una arista con la etiqueta X une dos vértices si puedes pasar de un vértice al otro poniendo X al final y borrando el primer símbolo. Por ejemplo, puede pasar del 01 al 10 poniendo un 0 al final de 01 y luego eliminando el 0 al principio, de modo que dibuje un borde del 01 al 10 y etiquételo como 0; puede obtener del 01 al 11 poniendo un 1 al final y eliminando el 0 desde el principio, por lo que hay un borde de 01 a 11 etiquetado como 1. Tenga en cuenta que hay un borde de 00 a sí mismo, etiquetado como 0, y uno de 11 a mismo, etiquetado como 1.

Ahora puedes probar que el gráfico que obtienes es euleriano, lo que significa que hay una manera de comenzar en cualquier vértice y viajar alrededor del gráfico, usando cada borde exactamente una vez. En nuestro ejemplo, comenzando en 11, puede usar bordes etiquetados como 1, 0, 1, 0, 0, 0, 1, 1 para hacer esto. Ahora observe que si juntamos el 11 inicial con esa secuencia de aristas, obtenemos exactamente 1110100011, nuestra secuencia de deBruijn.

Bueno, siempre obtienes secuencias de deBruijn de esta manera, por lo que puedes llamar a la gráfica gráfica de deBruijn.

Gracias. Esto no era todo lo que estaba buscando, pero al menos es un comienzo.
Ahora que he visto el artículo de Eppstein, no estoy seguro de que haya una relación entre las gráficas que he descrito y las de las que está hablando. ¿Te diste cuenta de que cuando comienza a discutir los gráficos de deBruijn, da un par de referencias, [16] y [17]? ¿Seguiste con eso?
No, intentaré ver de qué está hablando.
¿Qué hay detrás de los algoritmos de búsqueda de Game of Life de Conway?
RespuestasAquíPolítica de privacidad1y, 0v