ANTECEDENTES

Este problema era el más complejo de la competencia. La solución óptima implica programación dinámica en la que el problema era identificar claramente que variables se deben guardar en la tabla y determinar la forma de llenado.

APROXIMACIONES

Uno de los primeros algoritmos que puede probarse es una búsqueda recursiva que pruebe las posibles codificaciones en cada animal. En cada uno de ellos existen tres posibilidades: continuar con la familia del animal anterior, cambiar de familia a partir de este animal o cambiar de familia solo por este animal y volver a la familia anterior.

La parte recursiva del algoritmo podría bosquejarse de la siguiente manera:

ConstruirCadena ( costoActual, familiaActual, animalActual )

        si animalActual == n

             Mirar si el costoActual es mejor que el que se tenía

        costoSeguir = costoActual + Codificar en FamiliaActual

        ConstruirCadena ( costoSeguir, familiaActual , animalActual+1 )

        Para cada familia f

             // Cambiar de familia permanente

             costoNuevaFamilia = costoActual + costoCambiofamilia + Codificar en f

             ConstruirCadena ( costoNuevaFamilia, f, animalActual+1 )

             // Cambiar solo por este animal

             costoCambioUnicoFamilia = costoActual+costoCambiofamilia + Codificar en f

             ConstruirCadena ( costoCambioUnico, familiaActual, animalActual+1 )

Teniendo siempre en cuenta que el animal se pueda codificar en cada familia considerada y anexando recortes a la recursión cuando costoActual sea mayor que el que se tenía como mejor, el anterior algoritmo prueba todas las posibilidades de construcción de codificaciones.

El problema es que para la cantidad de animales dada el número de posibles combinaciones sería aproximadamente 100000^2+nf, donde nf es el número de familias, aunque este es un estimativo grueso pues no todos los animales se pueden codificar en todas las familias (un estimativo más razonable es el mayor número de familias en las que se puede codificar algún animal particular). Sin embargo de una u otra forma este número es muy alto y definitivamente el problema no podrá resolverse en los 3 segundos que se tenían como tiempo límite de respuesta.

SOLUCIÓN

Partiendo del anterior algoritmo puede notarse que existen casos que se prueban una y otra vez, por ejemplo la codificación de los últimos 10 animales en la familia 6 se probará una y otra vez y si lo óptimo es codificarlos a todos en esa misma familia no vale la pena revisar una y otra vez las combinaciones de esos últimos animales que ya sabemos que dan un costo mayor.

El hecho de ver que existen cosas que se calculan una y otra vez sugiere una solución dinámica. En este caso vemos que la lista de animales se codifica secuencialmente, lo que implica que la solución óptima para codificar hasta el animal i viene de alguna codificación óptima hasta el animal i-1. Ahora, debido a que cada animal puede codificarse en diferentes familias, vemos que esa codificación óptima depende de la familia en que estaba el anterior animal y de la familia que se elija para este animal.

Entonces se crea una tabla en la que la posición (i, j) va a guardar el tamaño de la codificación óptima para el animal j finalizando en la familia i. De esta forma para calcular la posición (i, j+1) se miran las tres posibilidades: seguir en la misma familia, cambiar de familia de aquí en adelante, o cambiar de familia solo por este animal. En la última opción debe notarse que la elección debe hacerse para cambiar a la familia en la que el animal se codifique con el mínimo costo.

De esta forma se llena la tabla por columnas (es decir, probando todas las familias para cada animal antes de pasar al siguiente) y al final se busca cual es el mínimo valor en la columna del animal n.

CÓDIGO

Dentro del código la función que resuelve el problema es

procesar( )

Realiza un recorrido por filas para determinar la codificación óptima de cada animal en cada familia. En el momento de considerar una familia mira si es posible codificar al animal en esa familia. Si es posible, entonces considera los costos de seguir en esa misma familia (incluyendo al animal anterior) y el costo de cambiar de familia a partir de este animal. Si no es posible, considera el costo de cambiar de familia solo por este animal. Como estimado inicial se mira si lo óptimo es cambiar de familia solo por este animal.

MEJORAS AL ALGORITMO

En la implementación actual se guarda toda la tabla con el propósito de reconstruir la codificación. Debido a que en el problema esto no era necesario, solo se necesitaba mantener en memoria los costos para el animal anterior y un arreglo para el cálculo de los costos del animal actual. Podría entonces guardarse solamente estas dos tablas o vectores en memoria y no toda la tabla. Aunque esto no representaría una mejora respecto a tiempo si haría el algoritmo más eficiente en cuanto a requerimientos de memoria.

Duvier Alexander Zuluaga Mora

duvier@softhome.net