fuentes_backtracking

diff --git a/src/backtracking.cpp b/src/backtracking.cpp
new file mode 100644 (file)
index 0000000..69f43da
--- /dev/null
+++ b/src/backtracking.cpp
@@ -0,0 +1,92 @@
+#include "backtracking.h"
+
+BackTracking::
+BackTracking(size_type capacidad) : Susanita(capacidad)
+{}
+
+/* Llamada recursiva: Ensaya una alternativa desde el hombre iH hasta el final de la lista */
+void BackTracking::Ensayar(personas_type::iterator iH) 
+{
+       /* Recorro todas las mujeres de este hombre */
+       for (personas_type::iterator iM = (*iH)->prefs.begin(); iM != (*iH)->prefs.end(); ++iM)
+       {
+               /* Si la mujer está soltera y la pareja es estable*/
+               if (((*iM)->estado == Persona::SOLTERO) && ParejaEstable(iM, iH))
+               {
+                       /* Se comprometen */
+                       (*iM)->comprometer_con_bt(**iH);
+
+                       /* Si quedan hombres solteros */
+                       if (!(*iH == *(hombres.rbegin())))
+                       {
+                               /* Sigo armando parejas estables */
+                               Ensayar(iH+1);
+                       }
+                       else
+                       {
+                               /* Si este es el último hombre entonces tengo una configuración estable */
+                               Parser p(*this);
+                               p.output();
+                               //this->mostrar_estado();
+                       }
+                       
+                       /* Rompo el compromiso */
+                       (*iM)->romper_compromiso(**iH);
+               }
+               
+       }
+}
+
+bool BackTracking::ParejaEstable(personas_type::iterator Mujer, personas_type::iterator Hombre)
+{
+       /* Una pareja (Mujer,Hombre) es estable si no existe: */
+       /* 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 */
+       /* 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 */
+       
+       
+       bool Estable = true;
+       
+       /* Tomo la primer mujer de la lista de preferencias del hombre */
+       personas_type::iterator iM = (*Hombre)->prefs.begin();
+       
+       
+       /* Mientras no encuentre a la mujer actual (o sea, voy viendo a las que prefiero más que a la candidata) */
+       while((iM<Mujer) && Estable)
+       {
+               /* Si la mujer no está soltera */
+               if ((*iM)->estado != Persona::SOLTERO)
+               {
+                       /* Me fijo si me prefiere más que al que tiene ahora */
+                       Estable = (std::find((*iM)->prefs.begin(),(*iM)->prefs.end(),*Hombre) > std::find((*iM)->prefs.begin(),(*iM)->prefs.end(),(*iM)->pareja));
+               }
+       
+               iM++;
+       }
+       
+       /* Calculo dónde está el hombre actual en la lista de preferencias de la mujer */
+       personas_type::iterator iHombre = std::find((*iM)->prefs.begin(),(*iM)->prefs.end(),*Hombre);
+       
+       /* Tomo el primer hombre de la lista de preferencias de la mujer */
+       personas_type::iterator iH = (*Mujer)->prefs.begin();
+       
+       /* Mientras no encuentre a la mujer actual (o sea, voy viendo a las que prefiero más que a la candidata) */
+       while((iH<iHombre) && Estable)
+       {
+               /* Si el hombre no está soltero */
+               if ((*iH)->estado != Persona::SOLTERO)
+               {
+                       /* Me fijo si me prefiere más que a la que tiene ahora */
+                       Estable = (std::find((*iH)->prefs.begin(),(*iH)->prefs.end(),*Mujer) > std::find((*iH)->prefs.begin(),(*iH)->prefs.end(),(*iH)->pareja));
+               }
+               
+               iH++;
+       }       
+       
+       return Estable;
+}
+
+void BackTracking::casamentear()
+{
+       /* Entrada a la llamada recursiva con el primer hombre de la lista */
+       Ensayar(hombres.begin());
+}

diff --git a/src/backtracking.h b/src/backtracking.h
new file mode 100644 (file)
index 0000000..2a84d49
--- /dev/null
+++ b/src/backtracking.h
@@ -0,0 +1,33 @@
+#ifndef _BACKTRACKING_H_
+#define _BACKTRACKING_H_
+
+#include "persona.h"
+#include "susanita.h"
+#include "parser.h"
+#include <map>
+#include <deque>
+#include <string>
+
+#ifdef __VC++__
+/* find_if está en <algorithm> en VC++ */
+#include <algorithm>
+#endif
+
+struct BackTracking : Susanita
+{
+       /// Constructor
+       BackTracking(size_type capacidad);
+
+       /// Empieza a emparejar gente
+       void casamentear();
+
+       private:
+       
+       /* Llamada recursiva: Ensaya una alternativa con el N-ésimo hombre */
+       void Ensayar(personas_type::iterator iH);
+       
+       /* Determina si la pareja es estable */
+       bool ParejaEstable(personas_type::iterator Mujer, personas_type::iterator Hombre);
+};
+
+#endif /* _BACKTRACKING_H_ */