Realizando una práctica de la asignatura de programación 3, de la Universidad Nacional de Educación a Distancia (UNED), he podido comprobar la diferencia, en coste computacional y rendimiento, que supone realizar un algoritmo mediante un algoritmo heurístico, como puede ser el de vuelta atrás (backtracking) y un algoritmo voraz (reducción).
El problema consiste en resolver, dar las posibles soluciones, de un tablero de shikaku. Se trata de un juego japonés que consiste en resolver un tablero, con unos números, mediante el uso de rectángulos que tengan un área igual al número que encierran, no pudiendo solaparse. Es decir, un número 4 en el tablero, puede formar rectángulos de 1x4, 2x2 y 4x1, y mientras tenga al número en cualquiera de las casillas que ocupa, es una combinación correcta. Un ejemplo gráfico:
Al principio, la solución más fácil, consiste en tomar todas las posibles combinaciones de los rectángulos, e ir probando combinaciones hasta dar con todas las combinaciones de solución. El problema, es que el costo computacional de la solución es muy alto cuantos más números haya y, sobre todo, cuantos más números con muchas combinaciones existan. Esto supone un coste exponencial e imposible de calcular en muchos casos.
Una solución, es el uso de un algoritmo voraz de reducción, que elimine muchas de las combinaciones posibles, antes de la aplicación de la solución. En sí no es complicado, ya que solo consta de tomar una de las combinaciones y comprobar si es posible su aplicación en el tablero, respecto a los números que hay colocados y que no se salga del propio tablero. Esto reduce mucho las probabilidades, pero aún no lo suficiente.
Otra reducción que se puede llevar a cabo es, si una combinación no es posible de encajarla en el tablero con ninguna de las combinaciones posibles de otro número, entonces esa combinación no es posible. Se puede eliminar.
Estas reducciones suelen ser rápidas, puesto que su coste computacional es muy bajo, y realizan una criba de elementos muy alta, de forma que rebajan mucho el coste que supondría ejecutar el algoritmo de vuelta atrás sin reducciones.
En la práctica, programado en Java y con tableros de la página de Nikoli, he comprobado que no se tarda más de 6 segundos en resolver los tableros más complejos, mientras que, sin reducciones, podría tardarse horas.
Por lo tanto, la elección del algoritmo sí importa.
