Tengo que empezar admitiendo que medio he hecho trampas al poner este título; en realidad, ya he probado el primer acotador, así que ahora ya sé que habrá (al menos) un segundo acotador.
La idea es simple; este acotador funcionará en dos etapas:
- añadir todos los puntos que se pueda.
- averiguar el número máximo de rectas que pueden cubrir los puntos.
Ese "todos los puntos que se pueda" se complica un poquito. En realidad, el criterio que usa este acotador no es para añadir puntos, sino para añadir rayas; lo que pasa es que en cuanto decida añadir una raya, se va a olvidar de ella y va a añadir sus puntos. Éste es el criterio exacto:
- Las rayas añadidas no pueden "pisar" las rayas que había puestas antes de llamar al acotador (sí pueden pisar las rayas puestas por el acotador)
- Si la raya que se va a añadir tenía exactamente cuatro puntos marcados anteriormente, ninguno de estos puntos puede satisfacer:
- haber sido añadido por el acotador;
- tener todos sus enlaces usados en la dirección de la raya (en cualquiera de los dos sentidos);
- y tener al menos uno de esos enlaces pisado por la raya.
Como siempre, un ejemplo dejará claro qué quiere decir esto. Imaginemos que tenemos que acotar el número de rayas que se pueden añadir a esta figura:
Podríamos añadir una raya que cogiese el punto de la derecha, o otra que cogiese el de la izquierda, pero no ambas rayas. Bueno, pues este acotador en realidad no recuerda si ha añadido una raya o no, lo que ve es que podría añadir cualquiera de ellas, y va a añadir los dos puntos.
Hay que aclarar una cosa; si vemos sólo los puntos, ahora parecería que podríamos añadir dos rayas más, y luego otras dos, y luego otras dos... pero claro, esto haría que añadiésemos infinitos puntos, y no sería muy útil que nuestro acotador dijera siempre "como mucho puedes añadir infinitas rayas". Así que el acotador tiene que recordar cuándo no debe continuar añadiendo puntos. El criterio retorcido de arriba impide esto (si fuésemos a añadir una nueva raya, nos encontraríamos con que tendría 4 puntos marcados previamente y los puntos ahora en los extremos habrían sido añadidos por el acotador, tendrían su único enlace usado en la misma dirección de la nueva raya, y este enlace sería pisado por la nueva raya).
Entonces viene la segunda etapa del acotador. Tenemos seis puntos en fila; ¿cuántas rayas puede haber ahí? Obviamente, sólo una. Para poder poner dos rayas tendría que haber 9 puntos en fila.
Y ya hemos acabado; la cota es uno.
Lo bonito de este algoritmo es que hemos acotado el número de rayas que podemos añadir sin haber decidido qué rayas añadir. Lo malo es que a veces esta estimación va a ser muy mala. Veamos un ejemplo en que el acotador nos cuela una raya de propina; empezamos con esta figura:
El primer punto que añadiremos será S; de hecho, podemos hacerlo de dos formas, uniendo P-R o Y-N. Supongamos que unimos los puntos P-R, y por tanto el acotador recuerda (por el criterio) que no puede continuar añadiendo puntos en esa dirección, así que, de momento, U no se puede añadir.
Una vez hemos añadido S, resulta que podemos añadir T, uniendo Z-S.
Y sorpresa, ahora el criterio nos deja añadir U, porque resulta que ahora no todos los enlaces usados de S están en la misma dirección. Es decir; mientras conocíamos una única forma de llegar a S, el criterio nos impedía continuar en esa dirección; pero una vez hemos llegado a S en dos direcciones (desde N y R), como no se puede saber cual es "la primera", tenemos que dejar continuar en las dos direcciones.
Total, estamos en que el acotador ha descubierto que puede llegar a los puntos S, T y U. Esto es correcto, salvo por el detalle de que por las incompatibilidades entre rayas, se puede añadir o bien T o bien U, pero no ambos. Da igual, este acotador no recuerda incompatibilidades entre rayas. Así que a continuación decide que también puede añadir X; lo único que hay que hacer es añadir la raya T-X. Lo cual es falso...
Y entonces el acotador llega a su segunda etapa; estos son los puntos alcanzables:
que pueden albergar como mucho tres rayas; una horizontal (que se podría escoger de dos formas), una vertical, y una diagonal (que se podría escoger de dos formas). De forma que el acotador dirá que se pueden añadir como mucho 3 rayas cuando, en realidad, el máximo son dos rayas.
¿Es esto muy malo? Bueno, ya sabemos que un acotador rápido no puede ser muy preciso, así que si este acotado nos clavase sólo una raya de más estaríamos muy contentos. El problema es que una vez que empieza a añadir rayas incorrectamente se desboca y acaba añadiendo infinitas rayas incorrectas. Veamos un ejemplo "real"; empezamos con esta figura:
* *
|\ /|
| \ / |
*--#--#--#--#
| \/ |
| /\ |
# * * #
| / \ |
|/ \|
# #
/| |\
/ | | \
# # # # # # # #
# #
# #
# # # # # # # #
# #
# #
# # # #
(Perdón por volver a los gráficos en ASCII, pero es que la salida del acotador no la preparado para matlab...)
Vale, el acotador hace una primera pasada y encuentra que podría añadir 37 puntos:
B B
|\ /|
| \ / |
B--#--#--#--#
| / \/ \ |
|/ /\ \|
@--#--B--B--#--@
/| / \ |\
/ |/ \| \
@ B # # B @
| / /| |\ \ |
| / / | | \ \ |
@--#--#--#--#--B--B--#--#--#--#--B
| / \ | /
|/ \|/
# #
/| /|\
/ | / | \
@ # @ B--B--B--#--B
|\ | | / /|
| \ | | / / |
@--#--#--#--#--B--B--#--#--#--#--@
| \ | | | / / |
| \ | | |/ / |
@ B--#--B--B--#--B--B--B--@
\ | | /| /
\| |/ |/
# B #
|\ /| /|
| \ / |/ |
@--#--#--#--#--@
| / \/| |
|/ /\| |
@--B--B--B--B--@
Pero claro, una vez ha añadido estos puntos, podría usarlos para añadir nuevas rectas; en la segunda pasada, el acotador cree que puede añadir estos 132 puntos:
B B @ B B
|\/|\ \/|\/|
|/\| \ /\|/\|
B--#--#--#--# @
/| |\/ \/|\/|\ |
/ | |/\ /\|/\| \|
B--B--B--B--#--B--B--#--B--B B B @
\ | / |\/|\/ \/|\/|\/|\/| /| /| /
\|/ |/\|/\ /\|/\|/\|/\|/ |/ |/
@ B--B--B--#--B--B--#--B--B--B--B--B
\ /|\ |\/|\/|\/|\/|\/|\/|\/|\/| /| /
\ / | \|/\|/\|/\|/\|/\|/\|/\|/\|/ |/
@--B--#--#--#--#--B--B--#--#--#--#--B--B
/ \ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/| /
/ \|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/
B--B--#--B--B--B--B--B--B--B--B--#--B--B
\ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/| /|
\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/ |
B--B--#--B--B--B--B--B--B--B--B--#--B--B
\ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--#--#--#--#--B--B--#--#--#--#--B--B
\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--B--B--B--#--B--B--#--B--B--B--B--B
|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--B--B--B--#--B--B--#--B--B--B--B--B
| /|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\ |
|/ |/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\| \|
B--B--B--B--B--#--#--#--#--B--B--B--B--B
| /| /|\/|\/|\/|\/|\/|\/|\/|\/|\/|\ |\ |
|/ |/ |/\|/\|/\|/\|/\|/\|/\|/\|/\| \| \|
B--B--B--B--B--B--B--B--B--B--B--B--B--B
| /| /| /|\/|\/|\/|\/|\/|\/|\/|\ |\ |\ |
|/ |/ |/ |/\|/\|/\|/\|/\|/\|/\| \| \| \|
B--B--B--B--B--B--B--B--B--B--B--B--B--B
La razón por la que esto tiene forma cuadrada es que el acotador busca nuevas rectas dentro de un cuadrado, que va ampliando según sea necesario. Como hace la búsqueda de arriba abajo y de izquierda a derecha, las nuevas rayas aparecen "barridas" hacia abajo a la izquierda. En las siguientes pasadas el cuadrado se va ampliando y las rayas acaban invadiendo todo el plano, así que cuando el acotador cree que puede añadir más de 200 rayas nuevas abandona y en vez de devolver una cota sobre el número de rayas devuelve un -1, que viene a decir "NPI".
Bueno, el que el acotador no acote ocasionalmente no es un problema demasiado grave; simplemente exploraremos ramas del árbol que quizás nos podríamos haber ahorrado. El problema sería que no consiguiese acotar con mucha frecuencia.
¿Pero cómo funciona en la práctica? Continuará...
No hay comentarios:
Publicar un comentario