Lo malo de la aproximación rápida para resolver un problema de algoritmia

El otro día contaba un caso donde los años de experiencia te hace ver pronto una solución a un problema. Hoy voy con el caso contrario: a veces la experiencia y lo que yo llamo resultismo o búsqueda de eficacia de muchos años de trabajo pueden ser contraproducentes. Sobre todo, si además se le añade el conocido error de no leer hasta el final los requerimientos. A veces la experiencia es mala consejera.

Hace unas semanas uno de mis hijos me pide ayuda. Está preparando una práctica para clase donde le piden resolver un problema de optimización mediante un algoritmo. Debe desarrollar el algoritmo en cuatro fases, desde una recursiva simple hasta una con programación dinámica. Pero no acaba de encontrar la forma de hacerlo. Me pasa el problema y le digo que se parece mucho al problema de la mochila (en inglés Knapsack) concretamente se trataba de una variante 0/1 con repetición de ítems y con restricciones con el número de ítems. Le digo si sabe hacer la práctica para un Knapsack. Me contesta que cree que si porque en clase el profesor usó ese problema en varias explicaciones. Se pone manos a la obre y obtiene el programa que resolvía el problema de la mochila en C++ en las cuatro versiones que le pedían.

Pero no lograba un resultado correcto. No se aclaraba con la parte del algoritmo que tenía que usar las restricciones sobre el número de artículos. Me vuelve a preguntar. Me pongo a pensar y doy con una solución: usar las restricciones de los números de artículos para crear tantos artículos iguales como el máximo de artículos iguales permitidos para el artículo en concreto. Le habían dado varios casos de prueba, así que cogemos uno fácil y a mano construimos las nuevas cargas para el programa… y funcionaba. De hecho, busco en la teoría y hay varios autores que dicen que es tal vez la solución más eficiente. Mi hijo prepara una función que transforma los datos de entrada que le proporcionan en tantos artículos diferentes del mismo tipo para poder usar su rutina de la mochila 0/1.

Sigue con las pruebas y se da cuenta que en los casos de prueba donde hay muchos artículos al multiplicar el número de artículos con su función el tiempo de ejecución sube mucho. Sobre todo, en las versiones menos eficientes del algoritmo. Vuelve a comentármelo. Aquí yo ya empiezo a darme cuenta del error que cometí al irme a buscar una solución rápida tirando por la calle de en medio. Es la costumbre de buscar resultados pronto y rápido. Vuelvo a la teoría y encuentro una solución. Se trata de aplicar una fórmula para crear los nuevos artículos usando sumas de potencias de 2 y promediando el valor y el peso. De esta manera un artículo que debíamos repetir 1.500 veces según los datos de entrada, se convertía solo en 7 artículo. A pesar de la demostración matemática mi retoño no lo veía claro. Así que tuve que repasar lo que sabía de C++ y cambié su rutina por la nueva. Hicimos las pruebas y los resultados eran correctos. Además ahora el tiempo de ejecución bajaba muchísimo.

Pero en la práctica en el último punto pedían que mostrásemos una lista con los artículos escogidos por el algoritmo y cuando de ellos habíamos seleccionado. Al hacerlo sobre una lista de artículos nueva (los creados por nosotros para poder usar un algoritmo 0/1 básico) los resultados que obteníamos no encajaban con los datos que se pedían.

Al final seguí con el C++ sobre todo porque me sentía culpable. Yo había marcado el camino mal con mi primer consejo. Entre los dos montamos otro juego de funciones que eran capaces de reconvertir las soluciones con el grupo de artículos nuevos y convertirlas a los artículos originales. Y todo funcionaba bien, menos mal.

Pero me puse a calcular el tiempo que habíamos invertido en todas las funciones accesorias que habíamos programado para no modificar el primer algoritmo de la mochila 0/1 y me di cuenta del gran error. Si hubiese leído todas las especificaciones y hubiese revisado los casos de pruebas habría empezado de otra forma y no habría usado una función de mochila 0/1 cambiando los datos de entrada. Pero es lo malo de estar acostumbrado a ir deprisa solucionando problemas.

De todas formas, no me ha parecido una experiencia negativa. Por un lado, yo he vuelto a programar en C++ y a pelearme con algoritmos y problemas abstractos. Por otro lado, mi hijo ha aprendido una lección doble: pensar bien las soluciones rápidas que le da su padre antes de implementarlas y la importancia de pensar, razonar, leer todas las especificaciones, ver con atención los casos de pruebas y hacer muchos diagramas antes de ponerse a codificar. Y por cierto las funciones para decodificar la solución que teníamos y convertirla en los artículos buscados fueran también buenas prácticas de algoritmia y eficiencia…

Así que esta semana está con otra práctica que también se parece mucho al problema de la mochila… pero esta vez lo ha enfocado de forma diferente… y con la décima parte de código su programa funciona bien. Por lo menos va aprendiendo la lección de que muchas veces es mejor pensar que ponerse rápidamente a resolver el problema a pesar de que tenemos una idea que nos parece muy buena y que está apoyada por autores de renombre.