Solitario de rayas IX: Análisis del primer acotador

Para decirlo claro, el primer acotador no ha acelerado mucho la exploración del grafo. Comparemos el tiempo requerido para ir llegando a algunos puntos del árbol, los records, que son los datos que se guardan:

Record	Sin acotador	Primer acotador	Aceleración
82 líneas	141 s	170 s	-21%
89 líneas	390 s	456 s	-17%
anchura 16	1,45 h	1,51 h	-4%
98 líneas	10,26 h	10,06 h	2%
anchura 17	12,77 h	12,52 h	2%
110 líneas	2,09 días	2,09 días	0%

Es interesante ver cómo la aceleración va aumentando. Creo que lo que ocurre aquí es que cuando el récord es alto, prácticamente da igual qué cota se haya obtenido, va a servir para podar la rama. Veamos unos datos; en la siguiente tabla, las dos primeras columnas indican cuántas veces se había alcanzado un cota al llegar al récord de las 82 líneas (2,8 minutos), y el porcentaje de estas cotas que permitieron podar su rama. Las dos últimas indican lo mismo, pero al llegar al récord de 110 líneas (2,1 días).

cota	récord 82		récord 110
	n	% podas	n	%podas
0	570158	100%	729359516	100%
1	294770	100%	374383109	100%
2	91457	100%	146709781	100%
3	82384	93%	97683991	100%
4	54667	84%	58612396	100%
5	31394	75%	29856109	100%
6	11964	59%	13630824	99%
7	8677	58%	5863876	99%
8	5058	67%	2183517	99%
9	5943	50%	727533	97%
10	2032	37%	287890	97%
11	1992	18%	136358	95%
12	3117	16%	60526	92%
13	554	19%	9386	82%
14	163	10%	1496	63%
15	20	5%	76	38%
16	0	-	2	100%
966	311722	21% sobre total	426817220	23% sobre total
total	1476072	76%	1886323606	77%

Por ejemplo, antes de llegar al récord de las 82 líneas, hubo 20 ocasiones en que al calcular la cota se llegó a la conclusión de que se podían añadir como mucho 15 rayas más, y en sólo una de estas 20 ocasiones (el 5%) se pudo podar la rama. Pero después de explorar un número de vértices 1000 veces mayor, se obtuvo esta cota 76 veces, y de ellas el 38% permitieron podar su rama. Más llamativo todavía es el caso de la cota 16; sólo se obtuvo dos veces, pero ya avanzado el cálculo, y las dos cotas sirvieron para podar sus respectivas ramas. Vemos que todos los porcentages de podas aumentan, confirmando que, avanzada la búsqueda, la misma cota tiene mayor probabilidad de resultar en un poda, con lo cual aceleramos un poquito.

Pero si podamos tanto, ¿cómo es que no aceleramos muchísimo más? Bueno, es que en realidad no podamos tanto; el porcentaje de veces en que se poda una rama no sube apenas, pasa del 76% al 77%. Esto se debe a que en realidad aumenta el porcentaje de ocasiones en las que no se puede obtener una cota, en cuyo caso se devuelve la "cota de error" 966; este error pasa de ser un 21% del total de acotaciones a 23%.

Es decir, en el 23% de los casos el primer acotador pone demasiados puntos y acaba desbocándose. Nunca se han puesto 17 puntos sin que la cota se disparase hasta el infinito. Es verdad que no pasa gran cosa por no poder conseguir una cota ocasionalmente, pero es que este 23% es un desastre, y encima se produce con más frecuencia en las ramas gruesas, cuando hay más rayas que añadir. Éste es el problema, que en vez de podar ramas gruesas (digamos, de profundidad 40) lo que estamos haciendo es arrancar ramitas (cota 16 como mucho), y por esto no llegamos a acelerar de verdad.

(Podar ramas de cota 16 podría parecer mucho, porque así a ojo podría pensarse que contienen del orden de 2¹⁶ vértices; el problema es que incluso si siempre podásemos estas ramas, podríamos acelerar el programa en un factor de "sólo" 2¹⁶=65536, con lo cual no tardaríamos 25.000 millones de años sino sólo 381.000 años. Hombre, sería un progreso, pero no va a ser suficiente para resolver el problema en un tiempo razonable. Hay que podar ramas gruesas, y para ello el acotador tiene que ser capaz de calcular cotas grandes, y para ello no puede desbocarse cuando añada un número pequeño de puntos. Este es precisamente el fallo del primer acotador.)

¿Cuánto cuesta el acotador?

Usaré para comparar el récord de 110 rayas. Sin usar acotador, en 180.247 segundos se llegó a este récord, explorando 15.900.563.680 vértices, luego explorar un vértice cuesta 11,34 millonésimas de segundo. Usando el acotador, en 180.195 segundos se exploraron 10.201.449.392 vértices y se hicieron 1.886.323.606 acotaciones, luego una acotación cuesta en promedio 34,20 millonésimas de segundo. Así pues, una acotación cuesta tanto como explorar tres vértices.

La noticia buena es que el uso del acotador redujo el número de vértices explorados en un 36%. La noticia mala es que el 36% del tiempo se invirtió en calcular acotaciones.

Cada acotación eliminó un promedio de 3,02 vértices. Si nos pudiésemos olvidar de las acotaciones que produjeron cotas de 0 o 1 raya, que siempre son exactas pero representan una pérdida de tiempo, y también de las acotaciones que no consiguieron producir ninguna cota y que por tanto no eliminaron ningún vértice, nos encontraríamos con que las 355.763.761 cotas útiles eliminaron 5.699.114.288 vértices. No es mucho; esto quiere decir que por el coste de 3 vértices nos ahorraríamos 16. Esto podría parecer bueno, pero de nuevo no nos sirve; en el mejor de los casos esto nos permitiría acelerar el programa en un factor 16/3, con lo cual bajaríamos de 25.000 millones de años a 4.700 millones.

¿Qué precisión tiene el acotador?

Cuando el acotador nos dice que a una figura se le pueden añadir como mucho n rayas, ¿hasta qué punto está lejos del máximo real? Bueno, pues mucho. La siguiente tabla, generada tras unas 24 horas de CPU, viene a confirmar que este acotador no es muy preciso. Las columnas profundidad y vértices indican el tamaño de la rama podada. Los datos se refieren únicamente a las ramas podadas, de aquí que parezcan un poco raros.

cota	máximo real	profundidad	vértices
0	0	0	0
1	1	1.14249	2.2850
2	1.95974	2.30487	5.4617
3	2.50155	3.04756	9.4554
4	3.11749	3.93441	15.5819
5	3.52629	4.48573	22.7194
6	3.70997	4.77245	29.2670
7	4.02461	5.31142	39.1521
8	4.25367	5.80146	54.8526
9	4.43245	6.09479	69.5210
10	4.80206	6.83219	97.9958
11	4.07557	6.80793	93.4930
12	3.92569	7.14832	124.9150
13	3.66041	7.48019	102.2030
14	3.17198	5.63476	49.2213

Los datos para cotas mayores son completamente ridículos, en parte porque hay pocas ramas y al hacer la media puede salir cualquier cosa. Es un poco triste ver que el máximo real no llega a 5; y eso de que cuando la cota sea de 14 rayas en promedio sólo se puedan añadir 3 es para deprimirse. Pero al menos el número de vértices en las ramas podadas crece de forma parecida a 2^profundidad.

El lado bueno es que un acotador que acotase relativamente bien hasta el nivel de 10 rayas aceleraría el programa en un factor de al menos 100.

Conclusiones

1. El primer acotador es caro en términos de tiempo, pero no demasiado; falla por el lado de la precisión en vez de por el tiempo.
2. El problema no es exactamente que sea pesimista, sino más bien que con demasiada frecuencia no llega a producir una cota útil.
3. El segundo acotador debe evitar la posibilidad de pasarse poniendo puntos, y puede ser bastante más caro.