Parejas

[HeXmiT]

A ver si me podéis aportar alguna idea sobre cómo afrontar esto:
Resúmen del problema...

Agrupación alumnos de dos en dos maximizando la suma de los productos del grado de amistad y la compenetración en el trabajo de alumnos que se agrupan juntos. Se dispone para ello de una matriz de amistad y otra de trabajo, donde se guardan los grados de amistad y de compenetración, que pueden no ser recíprocos, por lo que las matrices no son simétricas.

Con lo cuál tengo 2 tablas tal que así:

Amistad     Trabajo
0 5 6          0 5 3
4 0 3          3 0 2
2 1 0          1 5 0

El beneficio del que se habla se genera de la siguiente forma:

Código (cpp) [Seleccionar] Expandir

amistad[i][j]+amistad[j][i])*(trabajo[i][j]+trabajo[j][i]

Tengo que seguir obligatoriamente un esquema de backtracking iterativo ( y es lo que me está matando )...
Llevo más o menos el siguiente esqueleto:
** Intento plantearme esto como un árbol permutacional sin repetición **

Código (cpp) [Seleccionar] Expandir


do{
genera(nivel,sol);

if(solucion(sol,nalum)){
/* Sumar beneficios  y actualizar voa/soa */

}


if(criterio(nivel,sol,nalum)==true){
nivel++;
}else {
while((masHermanos(nivel,nalum)==false) && (nivel>0)) {
retroceder(nivel,sol);
nivel --;
}
}

}while(nivel!=0);


Dónde las funciones:

Genera(nivel,sol) debería generar el siguiente hermano, o el
primero, para el nivel actual.

Criterio (nivel, sol): Debería comprobar si a partir de sol[0-nivel] se puede alcanzar una solución válida. En caso de que no, podar.

MasHermanos (nivel, sol): Devuelve true si hay más hermanos del nodo actual que todavía no han sido generados.

Retrocede(nivel,sol): Retrocede la solucion y hace nivel--
--------------------------------------------------------------

Hasta ahora, todos mis intentos han acabado en un bucle infinito o bien en un falso backtrack, ya que recorría malamente.
¿Podría tratar de hacerlo aprovechando STL algorithm con la función para permutaciones?


A ver si alguien me puede echar un cable, que estoy más perdido que un ciego en el océano.

*Cualquier idea, será bien recibida *

Gracias y perdón por la biblia.

[Akai]

Qué tal si primero realizas el programa que simplemente realice las permutaciones (sin maximizar) y cuando las haga correctamente y sin repeticiones, ya maximizas el resultado?

Backtracking suele hacerse fácil si vas poco a poco, si lo intentas todo de golpe, se complica demasiado. Y te lo digo por pura experiencia.

Por otro lado, plantéate primero desarrollarlo como algo recursivo, que es lo más cercano a la definición natural de backtracking que te va a facilitar el asunto, y una vez funcione, traducirlo a iterativo.

Te han dicho que el programa al final sea de X forma, pero no que desde un principio empiece así,e intentar backtraking iterativo me parece un suicidio de buenas a primeras.

PD: si no tienes recursividad, usa una pila, es lo que se consigue implícitamente con la recursividad.

[HeXmiT]

Um, es más o menos lo que llevo intentando todo el tiempo, reducir el problema primero a las permutas y/o parejas para luego maximizar, pero no había pensando en un planteamiento recursivo inicial y como dices, el planteamiento iterativo es la muerte a pellizcos. Me pondré a ello, a ver si saco algo en claro.

[ghastlyX]

Si puedes usar la STL, es mucho más simple usando la función next_permutation. Si consideras el conjunto de las posibles permutaciones, dada una permutación, puedes considerar el agrupamiento que junta sigma(2i) con sigma(2i + 1), siendo sigma la permutación. Es decir, coges la permutación y vas juntando de dos en dos. Esto claramente no es biyectivo, pero si exhaustivo, de forma que aunque repetirás casos, no te dejarás ninguno. Por lo tanto será bastante más lento que si no repites y lo haces con un backtracking haciendo podas antes de calcular toda la permutación, pero salen cuatro líneas de código, haciendo algo así:

Código (cpp) [Seleccionar] Expandir

    vector<int> o(n);
    for (int i = 0; i < n; ++i) o[i] = i;
    int res = 0;
    do {
        int suma = 0;
        for (int i = 0; i + 1 < n; i += 2) suma += valor(o[i], o[i + 1]);
        res = max(res, suma);
    } while (next_permutation(o.begin(), o.end()));
    cout << res << endl;

Como comentario, se puede resolver este problema en tiempo polinómico (aunque el algoritmo es bastante complicado). Concretamente, tu problema se reduce a uno de los subproblemas (el más difícil) que aparecen al tratar de resolver el conocido Chinese Postman Problem.

[HeXmiT]

Para los curiosos, os dejo la funcion de backtrack ya resuelta.

Código (cpp) [Seleccionar] Expandir


void backtrack(int nalum){
int voa = -1; /* valor optimo actual */
int *soa; /* Solucion optima actual */
int temp = 0;
soa = new int[MAX+1];
nivel = 1; /* Inicializa el nivel */
hermanos[1] = nalum; /* Ramas */

do {
generar(nalum);
if (solucion(nalum)) {
temp = beneficio(nalum);
if (temp > voa) { /* Actualizamos el valor optimo y la solucion optima */
voa = temp;
for (int i = 1; i<=nalum; i++) soa[i] = sol[i];
}
}

if (criterio(nalum)) nivel++;
else while((!masHermanos()) && (nivel > 0)) retroceso();


} while (nivel!=0);

cout<< voa << endl;
for (int i=1; i<nalum; i++)
cout << soa[i]-1 << " ";

cout << soa[nalum]-1<< endl;


delete [] soa;
}


* Generar(): Obtiene permutaciones posibles según el nº de alumnos.

Saludos y gracias por la ayuda.