lunes, 15 de febrero de 2010

Solitario de rayas VI: Acotadores

La única esperanza de resolver el problema en un tiempo razonable es que no es necesario explorar todo el árbol, sino que a veces podremos podar algunas de sus ramas.

Por usar un poco de jerga; el algoritmo del que hemos hablado hasta ahora para recorrer todo el árbol (ver primero qué pasa si incluímos una raya, y ver luego qué pasa si la excluímos) es un ejemplo de Backtracking (Wikipedia lo traduce como "Vuelta atrás" pero a mí no me acaba de gustar esta traducción), y ahora queremos cambiarlo a Ramificación y poda, también llamado Ramificación y acotación, o Branch and bound.

Aunque en la Wikipedia lo explican de forma general y abstracta, la idea es sencilla: si tenemos un récord con 200 rayas, estamos en un vértice con 50 rayas, y sabemos que como mucho podremos añadir 50 rayas más, entonces no tenemos que explorar la rama que empieza en ese vértice, porque hagamos lo que hagamos no batiremos el récord. Si podamos muchas ramas y son grandes, podemos ahorrarnos cantidades enormes de trabajo.

El problema está, obviamente, en estimar el número máximo de rayas que se podrán añadir; en la jerga, "acotar el número de rayas".

En muchos problemas hay alguna forma relativamente sencilla de acotar algo; con frecuencia simplemente se calcula una fórmula matemática. En nuestro caso no tenemos tanta suerte; tendremos que usar un programa (una función en realidad) algo complicadillo al que llamaremos acotador.

Un acotador ideal tendría estas dos cualidades:

  1. rapidez
  2. precisión (la cota proporcionada debería estar muy cerca del máximo)

Desgraciadamente, las dos cosas son mutuamente excluyentes. Un extremo: como sabemos que ninguna figura tendrá más de 966 rayas, podríamos escribir un acotador velocísimo que, sin mirar siquiera a la figura, dijese que como mucho se le pueden añadir 966 rayas, y sería correcto, pero nada preciso, y absolutamente inútil, porque nunca serviría para podar una rama. El otro extremo sería escribir un acotador muy preciso que explorase toda la rama y devolviese el máximo exacto de rayas que se pueden añadir, pero entonces sería absurdamente lento; mucho más lento que usar el programa sin acotador. De hecho, no tiene sentido usar un acotador que dé la respuesta exacta y que sea rápido, porque entonces lo usaríamos directamente para resolver el problema. La gracia está en encontrar un punto medio, una forma fácil de encontrar una cota que pode mucho.

En nuestro caso, las llamadas al acotador costarán bastante tiempo, así que, para empezar, lo usaremos sólo cuando el número de rayas incluidas sea mayor que 20 y múltiplo de cinco. Lo más probable es que en el futuro decidamos cambiar esta condición.

No hay comentarios:

Publicar un comentario