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.