Algoritmo de Backtracking en C/C++, formalización e implementación

Inversor FX le da las herramientas y asesoramiento profesional en inversiones de alto rendimiento.

Veamos un ejemplo típico de algoritmo de Backtracking. Tenemos una serie de elementos únicos, cada uno con un peso o volumen ocupado, y cada elemento a su vez nos da cierta ganancia. Disponemos de una capacidad limitada por lo que debemos seleccionar de los elementos disponibles aquellos que nos den la mayor ganancia posible.

Supongamos que tenemos n elementos disponibles, numerados de 0 a n-1 y dos arreglos, uno p[n] que indica el peso de cada elemento y g[n] que indica la ganancia que nos da el elemento. M indica la carga máxima que podemos llevar. Debemos buscar elegir los elementos que nos den la mejor ganancia dado el espacio que ocupan.

Con estos datos pasemos a formalizar el problema.

Forma de la solución: Utilizaremos una tupla de largo n <x0,x1,…,xn-1>, donde cada elemento xi indica con 1 si llevamos el elemento i, o con 0 si no lo llevamos.

Reestricciones Explícitas: Cada elemento xi de la tupla se corresponde con un elemento i disponible.

Reestricciones Implícitas: La sumatoria de los pesos de los elementos seleccionados no superan la capacidad disponible M.

Función Objetivo: Maximizar la ganancia.

Predicados de Poda: Supongamos que en un momento dado encontramos una solución M_sol que es la mejor encontrada hasta el momento. Y supongamos que estamos construyendo una nueva solución parcial llamada sol. Dada esta solución parcial tendremos una poda si la suma de la ganancia que llevamos en la parcial, más las restantes que aún no hemos evaluado no llega a superar la ganacia de M_sol. Esto quiere decir que si la parcial tiene desde 0…k elementos, y nos quedan por analizar k…n-1, pero aunque eligieramos todos no llegamos a superar la ganancia de M_sol, no tiene sentido seguir con esta recorrida.

Terminada la conceptualización del problema, podemos pasar a construir la función que llamará al Backtracking:

int carga ( int* g, int* p, int* sol, int M) {
int pos = 0; // Posicion actual en la recorrida de elementos.
int ganancia = 0; // Ganancia parcial acumulada.
int m_ganancia = 0; // Mejor ganancia encontrada
int disponible = M; // Espacio disponible restante.
int restante = 0; // Ganancia restante disponible

int * parcial = new int[n]; // Marcaremos con 1 si llevamos al i, o con 0 en caso contrario
for (int i=0; i<n; i++) {
parcial[i] = 0; // Inicializamos en cero los eltos elegido.
restante += g[i]; // Ganancia de los elementos restantes, para la poda.
}

/* Llamamos a la función recursiva */
Back(g, p, parcial, ganancia, m_ganancia, disponible, restante, pos, sol);

delete[] parcial;
return m_ganancia;
}

Y veamos el código de la función recursiva:

void Back(int* g, int* p, int* parcial, int ganancia, int &m_ganancia, int disponible, int restante, int pos, int* sol) {
/* El primer paso es verificar que queda espacio disponible.
Ademas verificamos que podamos llegar a encontrar una mejor solución,
en caso contrario podamos. */
if ( (disponible > 0) && (ganancia + restante > m_ganancia)) {
/* Si ya pasamos por todos los elementos, terminamos */
if (pos == n) {
/* Ya sabemos que encontramos una mejor solucion que m_ganancia */
m_ganancia = ganancia;
for (int i=0; i<n; i++)
sol[i] = parcial[i];
/* Si no llegamos al final, probamos el elemento actual */
} else {
parcial[pos] = 1;
/* Probamos elegir el elemento y actualizamos los valores de ganancia y peso */
Back(g, p, parcial, ganancia, ganancia+g[pos], m_ganancia, disponible-p[pos], restante-g[pos], pos+1, sol);

parcial[pos] = 0;
/* O bien no lo llevamos y probamos seguir sin este elemento */
Back(g, p, parcial, ganancia, ganancia, m_ganancia, disponible, restante-g[pos], pos+1, sol);
}
}
}

De esta forma la función recursiva hace todas las combinaciones posibles de llevar ciertos elementos guardando el mejor resultados posible. Cada vez que se llega a pos == n es que recorrimos toda la secuencia, por lo que llegamos al final de la rama de decisiones del algoritmo. En ese momento y como el if que verifica que el espacio disponible sea sufuciente y que obtuvimos una mejor solución a la previa encontrada, podemos copiar el resultado obtenido.

Estructuras de datos y algoritmos en C/C++: Backtracking, formalización y ejemplos

Continuando con la serie de artículos sobre C/C++, vamos a ver la técnica de programación conocida como Backtracking. Esta técnica se basa en generar todo el espacio de soluciones posibles a un problema dado, pudiendo filtrarse o seleccionar las soluciones que cumplan con ciertas características. Backtracking funciona en forma recursiva, genera árboles de soluciones posibles, recorriendo todo el espectro de posibilidades.

En un primer vistazo Backtracking funciona como un algoritmo de fuerza bruta, que prueba todas las combinaciones posibles, aunque podemos optimizar y mejorar el rendimiento analizando el problema que queremos resolver.Los algoritmos de backtracking suele ser ineficientes, aunque mediante estas optimizaciones se puede moderar la misma, la repetición de cálculos hace que sean ampliamente inferiores a los algoritmos construídos sobre Programación Dinámica. En la próxima entrada analizaremos las diferencias, ahora volvamos a Backtracking :).

Por ejemplo, supongamos que tenemos un conjunto de colores y un mapa dado y queremos colorearlo, de forma que dos países adyacentes no tengan el mismo color. Podemos pensar en este problema como si fuera un grafo, donde los vértices conectados son los países limítrofes.

Este problema puede solucionarse de varias formas, por ejemplo buscando una solución cualquiera, o bien buscar todas las soluciones que existen, o bien la solución óptima que utiliza la menor cantidad de colores.

Lo primero que debemos hacer es formalizar el problema, así logramos identificar los elementos del mismo y se simplifica la tarea de construir el algoritmo. La formalización requiere definir:

Forma de la Solución: Cómo presentaremos la solución al problema. En este caso utilizaremos una tupla de largo fijo N formada por elementos xN, donde N es la cantidad de países que debemos colorear. En la posición 1 colocaremos el color asignado al país 1, en la posición 2 el color del país 2 y así sucesivamente.

Reestricciones Explícitas: El espacio de soluciones, o las soluciones posibles al problema, involucra a un único elemento de la tupla. En este caso indica que cada elemento xi es uno de los países a colorear.

Reestricciones Implícitas: Define las relaciones entre los elementos de la tupla, involucra a varios o todos los elementos de la tupla. En este caso debemos aplicar la reestricción que si dos países son adyacentes no deben tener el mismo color. Por lo que si 1 y 2 son adyacentes en el grafo, entonces los elementos x1 y x2 deben ser distintos.

Función Objetivo: Define lo que queremos maximizar o minimizar en las soluciones generadas. Puede ser la mínima o máxima cantidad de colores por ejemplo.

Predicados de Poda: Nos permite evitar buscar soluciones que es evidente no van a generar una solución útil. Por ejemplo supongamos que buscamos el mínimo de colores, entonces una vez que obtenemos una solución posible al problema sabemos que cualquier solución parcial que se esté construyendo puede ser descartada si la cantidad de colores supera a la ya encontrada.

Con estos elementos definidos podemos pasar a implementar el algoritmo con una idea general de como representar cada elemento. Lo primero que haremos será crear una estructura para nuestra tupla solución:

struct tupla {
int* colores; // Arreglo de colores asignados a los pasies
int* cantVeces; // Cantidad de veces que se usa cada color
int cantColores; // Cantidad total de colores usados
}

El próximo paso es preparar la invocación del algoritmo recursivo, al cual le pasaremos esta tupla para que trabaje:

void invocacion(int n, int k) {
/* La primera tupla será sobre la que se trabajará, en t solo guardamos la mejor solución obtenida */
tupla t, sol;
t.colores = new int[n];
sol.colores = new int[n]; // Colores asignados a los paises, n países
t.cantVeces = new int[k];
sol.cantVeces = new int[k]; // Cantidad de veces de cada color, k colores

for (int i=0; i<n; i++) {
t.colores[i] = 0;
sol.colores[i] = 0; // Inicializamos en cero los colores asignados a países
}
for (int i=0; i<k; i++) {
t.cantVeces[i] = 0;
sol.cantVeces[i] = 0; // Inicializamos en cero la cantidad de veces usada de cada color
}
t.cantColores = 0;
sol.cantColores = 0; // Cantidad de colores usados

colorear(t,sol,0,n); // Invocación al algoritmo
}

Esta función invocación prepara el terreno y luego llama a la función recursiva, pasándole una tupla t donde ir armando las soluciones posibles y sol para guardar la mejor solución encontrada. Esta misma tupla sol se usará para comparar con las tuplas que se van encontrando, de forma de saber si encontramos una mejor solución o no. El tercer parámetro es el primer país sobre el cual comenzar a trabajar, n la cantidad de países total, de forma que el algoritmo puede saber en que momento llega a asignar colores a todos los países y debe detenerse, y k la cantidad de colores para realizar las pruebas con los colores disponibles.

Veamos un ejemplo de la función recursiva colorear:

/* Noten que la tupla sol es pasada por referencia, de modo que cualquier estado de la recurrencia puede modificarla y es visible para todos los demás estados. */
void colorear(tupla t, tupla &sol, int i, int n, int k) {
/* Reestriccion implicita, verificamos que al colocar el color en esta posición
no queden dos paises adyacentes con el mismo color. */
if (Factible(t,i))
if (EsMejor(t,sol))
if (EsSolucion(t,i)) {
Copiar(sol, t)
} else {
for (int color=1; color <= k, color++)
colorear(AsignarColor(t,i,color),sol, i+1, n, k);
}
}

Utilizamos una seria de funciones auxiliares.

Factible: Indica si la tupla t, con colores asignados hasta la posición i no contiene países adyacentes con el mismo color.

EsMejor: Indica si la cantidad de colores utilizados en t es menor que los de sol.

EsSolucion: Indica si se completo la cantidad de países a colorear. Si es así (y como antes vimos que era mejor esta solución que la de sol) procedemos a copiar la misma en sol.

AsignarColor: Como todavía no completamos la cantidad de países debemos asignar un color de los k disponbles al país i, y continuar con la recursión.

Los detalles importantes a tener en cuenta son algunos como que la tupla sol puede ser modificada copiando el contenido de t sobre ella por cualquier paso recursivo que encuentre una mejor solución que la que tenemos hasta el momento. Claro que cuando sol es vacía debemos tener cuidado para no tener una solución vacía como la mejor encontrada. Otro detalle importante es no perder soluciones posibles, por eso en cada paso intentamos asignar todos los colores a cada país, para luego en la nueva llamada verificar la adyacencia.

Una posible implementación de AsignarColor, teniendo en cuenta la estructura de tupla que definimo podría ser:

tupla Asignarcolor(tupla t, int, i, int color) {
t.colores[i] = color;
t.cantVeces[color] = t.cantVeces[color]+1; // Incrementamos la cantidad de veces que usamos el color
if (t.cantVeces[color] == 1)
t.cantColores = t.cantColores +1; // Si el color asignado no habia usado aun, incrementamos cantColores
return t;
}

Este algoritmo construido con Backtracking nos permite generar todas las combinaciones posibles de colores asignados, optimizando de forma que podemos detener la recursión en un paso intermedio al encontrar dos países adyacentes con el mismo color.

En la próxima entrada veremos otro ejemplo de Backtracking similar implementado.