No me acordaba yo de lo obsesivo que puede llegar a ser este problema. No llega al extremo del Tetris, que hacía que fueses viendo fichas cayendo mientras caminabas por la calle, pero después de unas horas haciendo solitarios, cuando miro al teclado del ordenador empiezo a trazar mentalmente rayas uniendo las letras. Es especialmente hipnótico el barrer con la mirada un solitario casi acabado, cuando no tienes que aplicar ninguna estrategia, ni tienes que decidir qué rayas pones antes que otras, sino que simplemente debes buscar huecos donde añadir una nueva raya.
Ayer acabé mi primer programa y lo puse en marcha. El pobrecito era mera carne de cañón, estaba destinado a estrellarse sin posibilidad de victoria contra un enemigo muy superior numéricamente.
La noticia buena es que, a pesar de sus limitaciones, este programita ha sido capaz de encontrar una solución con 98 rayas en 11 horas:
*
|\
| \
*--*--*--*--* * *
|\ |\/|\/| |\/|\/|\
| \|/\|/\| |/\|/\| \
* * *--#--#--#--#--*--*--*--*
\ |\/|\/|\/|\/|\/|\ |\ |\ /|
\|/\|/\|/\|/\|/\| \| \| \ / |
* *--#--*--*--#--*--*--*--*
/|\/|\/|\/|\/|\/|\ |\/|\/ \/|
/ |/\|/\|/\|/\|/\| \|/\|/\ /\|
* * *--#--*--*--#--*--*--*--*
/|\/|\/|\/|\/ \/|\/|\/|\/|\/|\/|\
/ |/\|/\|/\|/\ /\|/\|/\|/\|/\|/\| \
*--#--#--#--# * *--#--#--#--# * *
\ |\/|\ |\/ \/ \/| / \/|\/|\/|\/| |
\|/\| \|/\ /\ /\|/ /\|/\|/\|/\| |
#--*--*--*--*--*--*--*--*--#--*--*--*
|\ |\/|\/ \/|\/|\/ \/|\/|\/| |\ |
| \|/\|/\ /\|/\|/\ /\|/\|/\| | \|
*--#--*--*--*--*--*--*--*--*--#--*--*
\ |\/|\ |\/|\ |\/|\/|\/|\/|\/|\/| /|\
\|/\| \|/\| \|/\|/\|/\|/\|/\|/\|/ | \
#--#--#--#--*--*--#--#--#--#--*--*--*
/ \ |\ |\ |\/|\/|\/|\/|\/|\/|\/|\/| /
/ \| \| \|/\|/\|/\|/\|/\|/\|/\|/\|/
* *--*--#--*--*--#--*--*--* * *
\ |\/|\/|\/|\/|\/|\/|\/|\/| /
\|/\|/\|/\|/\|/\|/\|/\|/\|/
*--#--*--*--#--*--*--*--*
|\/|\/ \/|\/|\/|\/| /| /
|/\|/\ /\|/\|/\|/\|/ |/
*--#--#--#--#--*--*--*--*
| / / |\ \ |\/|\/|
|/ / | \ \|/\|/\|
* * *--*--*--*--*
| / | \ |\ |
|/ | \| \|
* * * *
|
|
*
En cuanto a la anchura, lo mejor que ha encontrado tenía 16 puntos de lado a lado; me parece poco, tendré que echarle un ojo al programa a ver si tiene algún error.
La noticia mala es que durante veinte horas ha explorado 5.500 millones de figuras, y esto ha resultado ser una fracción ridículamente insignificante del problema. Echemos unas cuentas.
Para entender lo que significan los datos que pondré después, tendré que explicar lo que significan las ristras de unos y ceros. Lo que hace este programa para analizar una figura es dividirla en dos casos:
- buscar una raya que pueda ser añadida
- añadir esta raya (esto se representa con un 1) y analizar la figura obtenida
- quitar la raya (esto es un 0) y analizar la figura, recordando no volver a añadir nunca más esa raya
- acabar; volver al análisis anterior, de donde venimos.
A cada caso analizado, el programa escribe una secuencia de unos y ceros, indicando dónde está en este procedimiento; por ejemplo, la cadena "101..." quiere decir que todavía está analizando el caso en que pone la primera raya, no pone la segunda, pone la tercera,...
Un ejemplo; empezamos con estos puntos marcados:
Obviamente sólo podemos añadir cuatro rayas, que supongamos que el programa va encontrando en este orden: rojo, verde, azul, marrón.
Sólo hay 9 posibilidades, porque si decidimos poner la línea roja, entonces no podremos poner la marrón, y si decidimos poner la verde, no podremos poner la azul. Estas nueve posibilidades son exploradas mientras se recorre este árbol:
Bueno, pues esta tabla resume la búsqueda hasta ahora.
| Récord | Tiempo | Posición en el árbol |
|---|---|---|
| 67 rayas | 1 seg | 1111111111111111111111111 1111101111110111111111111 111111111111100111111 |
| 75 rayas | 4 seg | 1111111111111111111111111 1111101111110111111111111 1110111011101111100111111 1111111 |
| 77 rayas | 20 seg | 1111111111111111111111111 1111101111110111111111111 0011110110001100110111111 1100110111111111 |
| 82 rayas | 2,5 min | 1111111111111111111111111 1111101111110111111111101 0011111010111011111011101 11111111111111 |
| anchura 16 | 1,5 horas | 1111111111111111111111111 1111101111110111111110100 1111011111111110111110011 101111111011101110111 |
| 98 rayas | 11 horas | 1111111111111111111111111 1111101111110111111011100 1100110111001101111101110 1101111111111111111110111 11111011111111 |
| - | 20 horas | 1111111111111111111111111 1111101111110111111010001 1011001000110110100010110 11110101101110 |
Una cosa que me llama mucho la atención son esos dos bits que aparecen puestos a 0, el 31 y el 38, los marcados en verde. ¿Qué narices habrá pasado ahí para que el ordenador se haya podido dar cuenta de que esas dos rayas no deben incluirse? Han estado ahí desde el primer segundo. Tengo curiosidad, esto habrá que investigarlo.
Pero el caso es que seguimos trabajando en el bit número 44; todas las secuencias empiezan con la misma ristra de 44 unos y ceros (marcada en rojo). Vale que como hay dos bits inútiles podemos decir que estamos trabajando en el bit efectivo número 42, pero de todas formas esto sugiere que en 20 horas hemos hecho la 2-42-ava parte del trabajo. En otras palabras, este programa podría acabar dentro de unas 20*242 horas, es decir, dentro de 10.000 millones de años. Tampoco es para tanto; si hubiésemos empezado a calcular cuando el Big Bang, ya habríamos acabado (sería una forma como otra cualquiera de darle un propósito al universo).
¿Nos habremos metido con un problema demasiado grande? Al escribir esto me estoy rascando la barbilla con aire preocupado. Bueno, parece claro que nos lo vamos a tener que currar, pero nos quedan unos cuantos trucos en la manga. Por ejemplo, considerando que debido a las simetrías del problema encontraremos casi todas las soluciones por octuplicado, debería ser fácil rebajar el tiempo a unos 1.250 millones de años. Pero lo que tenemos que hacer con nuestro árbol es podarlo a lo bestia. Próximamente en este blog: branch and bound.
No hay comentarios:
Publicar un comentario