src/backtracking.cpp

   1 #include "backtracking.h"
   2
   3 BackTracking::
   4 BackTracking(size_type capacidad) : Susanita(capacidad)
   5 {}
   6
   7 /* Llamada recursiva: Ensaya una alternativa desde el hombre iH hasta el final de la lista */
   8 void BackTracking::Ensayar(personas_type::iterator iH)
   9 {
  10         /* Recorro todas las mujeres de este hombre */
  11         for (personas_type::iterator iM = (*iH)->prefs.begin(); iM != (*iH)->prefs.end(); ++iM)
  12         {
  13                 /* Si la mujer está soltera y la pareja es estable*/
  14                 if (((*iM)->estado == Persona::SOLTERO) && ParejaEstable(iM, iH))
  15                 {
  16                         /* Se comprometen */
  17                         (*iM)->comprometer_con_bt(**iH);
  18
  19                         /* Si quedan hombres solteros */
  20                         if (!(*iH == *(hombres.rbegin())))
  21                         {
  22                                 /* Sigo armando parejas estables */
  23                                 Ensayar(iH+1);
  24                         }
  25                         else
  26                         {
  27                                 /* Si este es el último hombre entonces tengo una configuración estable */
  28                                 Parser p(*this);
  29                                 p.output();
  30                                 //this->mostrar_estado();
  31                         }
  32
  33                         /* Rompo el compromiso */
  34                         (*iM)->romper_compromiso(**iH);
  35                 }
  36
  37         }
  38 }
  39
  40 bool BackTracking::ParejaEstable(personas_type::iterator Mujer, personas_type::iterator Hombre)
  41 {
  42         /* Una pareja (Mujer,Hombre) es estable si no existe: */
  43         /* 1) ninguna mujer iM por la que Hombre tenga más preferencia que Mujer, y que a su vez iM prefiera más a Hombre que a su actual pareja */
  44         /* 2) ningún hombre iH por el que Mujer tenga más preferencia que Hombre, y que a su vez iH prefiera más a Mujer que a su actual pareja */
  45
  46
  47         bool Estable = true;
  48
  49         /* Tomo la primer mujer de la lista de preferencias del hombre */
  50         personas_type::iterator iM = (*Hombre)->prefs.begin();
  51
  52
  53         /* Mientras no encuentre a la mujer actual (o sea, voy viendo a las que prefiero más que a la candidata) */
  54         while((iM<Mujer) && Estable)
  55         {
  56                 /* Si la mujer no está soltera */
  57                 if ((*iM)->estado != Persona::SOLTERO)
  58                 {
  59                         /* Me fijo si me prefiere más que al que tiene ahora */
  60                         Estable = (std::find((*iM)->prefs.begin(),(*iM)->prefs.end(),*Hombre) > std::find((*iM)->prefs.begin(),(*iM)->prefs.end(),(*iM)->pareja));
  61                 }
  62
  63                 iM++;
  64         }
  65
  66         /* Calculo dónde está el hombre actual en la lista de preferencias de la mujer */
  67         personas_type::iterator iHombre = std::find((*iM)->prefs.begin(),(*iM)->prefs.end(),*Hombre);
  68
  69         /* Tomo el primer hombre de la lista de preferencias de la mujer */
  70         personas_type::iterator iH = (*Mujer)->prefs.begin();
  71
  72         /* Mientras no encuentre a la mujer actual (o sea, voy viendo a las que prefiero más que a la candidata) */
  73         while((iH<iHombre) && Estable)
  74         {
  75                 /* Si el hombre no está soltero */
  76                 if ((*iH)->estado != Persona::SOLTERO)
  77                 {
  78                         /* Me fijo si me prefiere más que a la que tiene ahora */
  79                         Estable = (std::find((*iH)->prefs.begin(),(*iH)->prefs.end(),*Mujer) > std::find((*iH)->prefs.begin(),(*iH)->prefs.end(),(*iH)->pareja));
  80                 }
  81
  82                 iH++;
  83         }
  84
  85         return Estable;
  86 }
  87
  88 void BackTracking::casamentear()
  89 {
  90         /* Entrada a la llamada recursiva con el primer hombre de la lista */
  91         Ensayar(hombres.begin());
  92 }