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

Posted: Febrero 25th, 2009 | Author: | Filed under: Algoritmos, C/C++ | Tags: , , , , , | 4 Comments »

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.


4 Comments on “Algoritmo de Backtracking en C/C++, formalización e implementación”

  1. 1 carlos said at 3:03 pm on Abril 14th, 2009:

    me podrias ayudar a realizar un algoritmo q dada una cadena de datos, las separe por medio de un backtraking y genere una matriz, dado q los dos primeros numeros de esa cadena de datos son las filas y las columnas, despues tendriamos como el nombre de cada columna y despues el de las filas y seguido los datos q rellenaran esa matriz, es como formar una tabla de clientes x compras.. gracias de antemano

  2. 2 admin said at 9:39 am on Abril 15th, 2009:

    Carlos, no estoy seguro de que backtracking sea la mejor opcion para tu problema, o por lo menos lo que entiendo de tu descripcion. El problema que describis es secuencial, no tenes un espacio de soluciones posibles, si no que tenes que rellenar una matriz en determinado orden.

    Backtracking funciona tomando un problema con una gran cantidad de soluciones posibles y combinando las mismas en busqueda de optimizar.

    Se me ocurre que si tu problema esta en una vez creada la matriz buscar la mejor forma de rellenar la misma, ahi si se podria aplicar backtracking, probando poner cada cliente en la primera posicion, y luego todos los demas en la siguiente, y marcando los que vas usando en cada paso para no repetir.

  3. 3 leonardo said at 10:30 pm on Diciembre 14th, 2009:

    me podrian ayudar con un algoritmo que resuelva lo siguiente:
    los horarios de vuelo de una aerolinea definen un grafo natural, donde los vertices son los aeropuertos y hay arcos entre los aeropuertos con vuelos directos entre ellos cuyo peso es proporcional a la distancia suponga q queremos salir de un aeropuerto A a uno B en un tiempo T a una importante reunion programada. se debe encontrar el tiempo mas tarde q se pude dejar el aeropuerto A para llegar a tiempo a la reunion programada.
    nota:los aeropuertos cuentan con varios horarios de vuelo y hay n aeropuertos
    gracias.

  4. 4 Miguel said at 1:53 pm on Julio 10th, 2011:

    Hola me podriasdar ideas para realizar un backtracking en el cual me dan una palabra, luego debo eliminar una letra de esa palabra y ordenar dicha palabra de manera tal de buscar si alguna de las combinaciones de palabras, se encuentra en un diccionario que me dan anteriormente. Gracias