elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Guía actualizada para evitar que un ransomware ataque tu empresa


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Parejas
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Parejas  (Leído 2,969 veces)
HeXmiT


Desconectado Desconectado

Mensajes: 323


Ver Perfil
Parejas
« en: 30 Mayo 2011, 19:51 pm »

A ver si me podéis aportar alguna idea sobre cómo afrontar esto:
Resúmen del problema...
Citar
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í:
Citar
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
  1. 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
  1. do{
  2. genera(nivel,sol);
  3.  
  4. if(solucion(sol,nalum)){
  5. /* Sumar beneficios  y actualizar voa/soa */
  6.  
  7. }
  8.  
  9.  
  10. if(criterio(nivel,sol,nalum)==true){
  11. nivel++;
  12. }else {
  13. while((masHermanos(nivel,nalum)==false) && (nivel>0)) {
  14. retroceder(nivel,sol);
  15. nivel --;
  16. }
  17. }
  18.  
  19. }while(nivel!=0);
  20.  

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.


« Última modificación: 30 Mayo 2011, 20:06 pm por HeXmiT » En línea

Akai


Desconectado Desconectado

Mensajes: 823



Ver Perfil
Re: Parejas
« Respuesta #1 en: 30 Mayo 2011, 21:04 pm »

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.


En línea

HeXmiT


Desconectado Desconectado

Mensajes: 323


Ver Perfil
Re: Parejas
« Respuesta #2 en: 30 Mayo 2011, 21:19 pm »

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.
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Parejas
« Respuesta #3 en: 30 Mayo 2011, 23:02 pm »

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
  1.    vector<int> o(n);
  2.    for (int i = 0; i < n; ++i) o[i] = i;
  3.    int res = 0;
  4.    do {
  5.        int suma = 0;
  6.        for (int i = 0; i + 1 < n; i += 2) suma += valor(o[i], o[i + 1]);
  7.        res = max(res, suma);
  8.    } while (next_permutation(o.begin(), o.end()));
  9.    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.
En línea

HeXmiT


Desconectado Desconectado

Mensajes: 323


Ver Perfil
Re: Parejas
« Respuesta #4 en: 1 Junio 2011, 22:07 pm »

Para los curiosos, os dejo la funcion de backtrack ya resuelta.
Código
  1. void backtrack(int nalum){
  2. int voa = -1; /* valor optimo actual */
  3. int *soa; /* Solucion optima actual */
  4. int temp = 0;
  5. soa = new int[MAX+1];
  6. nivel = 1; /* Inicializa el nivel */
  7. hermanos[1] = nalum; /* Ramas */
  8.  
  9. do {
  10. generar(nalum);
  11. if (solucion(nalum)) {
  12. temp = beneficio(nalum);
  13. if (temp > voa) { /* Actualizamos el valor optimo y la solucion optima */
  14. voa = temp;
  15. for (int i = 1; i<=nalum; i++) soa[i] = sol[i];
  16. }
  17. }
  18.  
  19. if (criterio(nalum)) nivel++;
  20. else while((!masHermanos()) && (nivel > 0)) retroceso();
  21.  
  22.  
  23. } while (nivel!=0);
  24.  
  25. cout<< voa << endl;
  26. for (int i=1; i<nalum; i++)
  27. cout << soa[i]-1 << " ";
  28.  
  29. cout << soa[nalum]-1<< endl;
  30.  
  31.  
  32. delete [] soa;
  33. }
  34.  

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

Saludos y gracias por la ayuda.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Facebook refleja las parejas de hecho
Noticias
wolfbcn 0 1,727 Último mensaje 18 Febrero 2011, 22:25 pm
por wolfbcn
Crecen las redes sociales exclusivas para parejas infieles
Noticias
wolfbcn 0 2,714 Último mensaje 5 Marzo 2011, 13:35 pm
por wolfbcn
algoritmo para combinar parejas
.NET (C#, VB.NET, ASP)
diego_lp 2 3,726 Último mensaje 8 Abril 2011, 02:26 am
por seba123neo
Los estereotipos machistas perviven en las parejas de adolescentes
Foro Libre
wolfbcn 4 2,508 Último mensaje 27 Noviembre 2011, 20:05 pm
por ShotgunLogic
Avocado, aplicación colaborativa para parejas
Noticias
wolfbcn 0 1,027 Último mensaje 19 Abril 2013, 17:23 pm
por wolfbcn
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines