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:
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 **
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.
Mostrar Temas
