Busqueda.c

#include <stdio.h>
#include <stdlib.h>
#include "estado.h"
#include "operadores.h"
#include "nodos.h"
#include "heuristica.h"
#include "busqueda.h"
 
 
 
#define min(a,b) ((a)<(b)) ? a : b
#define max(a,b) ((a)>(b)) ? a : b
#define MAXPROOF 100
#define MAXCOSTE 100
#define MAX_NODOS 30
 
operador listaOperadores[NUM_OPERADORES] =
{
 {aplicableMoverNorte, moverNorte},
 {aplicableMoverSur, moverSur},
 {aplicableMoverEste, moverEste},
 {aplicableMoverOeste, moverOeste}
};
 
 
heuristica listaHeuristicas[] =
{
 heuristicaDistancias,
 heuristicaAciertos,
 heuristicaAnchura
};
 
nodoLista *meterEnLista (nodoLista * lista, nodoGrafo * png);
coste calcularCosteSucesor (nodoGrafo * png);
coste calcularHeuristica (int nHeur, estado e, estado emeta);
nodoGrafo *obtenerElemento (nodoLista * lista, nodoGrafo * png);
movimiento *construirResultado (nodoGrafo * pnodo, int *);
 
 
/* 
* Introducimos en la lista una referencia a un nodo, bien haya sido
* tratado o no. El orden no es significativo, asi que lo introducimos
* siempre al principio.
*/
nodoLista *meterEnLista (nodoLista * lista, nodoGrafo * png) 
{
 nodoLista *pnuevoNodo;
 
 pnuevoNodo = crearNodoLista ();
 pnuevoNodo->pnodo = png; 
 pnuevoNodo->psiguiente = lista;
 lista = pnuevoNodo;
 return lista;
}
 
 
/*
* Calcula el nuevo coste para llegar de la raiz a cada un de sus
* sucesores
*/
coste calcularCosteSucesor (nodoGrafo * png)
{
 return (png->costeRaizNodo + 1);
}
 
 
/*
* Calcula el coste estimado para llegar desde el estado <e>
* al estado meta <emeta>
*/
coste calcularHeuristica (int nHeur,estado e, estado emeta)
{
 return listaHeuristicas[nHeur](e,emeta);
}
 
 
nodoGrafo *obtenerElemento (nodoLista * lista, nodoGrafo * png)
{
 nodoLista *pnactual = lista;
 
 while (pnactual != NULL)
 {
  if (compararEstados (*pnactual->pnodo->pestadoPuzzle, *png->pestadoPuzzle))
     return pnactual->pnodo;
  else
     pnactual = pnactual->psiguiente;
 }
 return NULL;
}
 
 
 
 
 
/***************************************************************************************/
/*				DFID						       */ 
/***************************************************************************************/ 
bool BLEP (nodoGrafo *nodo, nodoLista *lCerrados, estado emeta, int limite, 
           resultadoBusqueda *result)
{
 bool noMetaEncontrada;

 noMetaEncontrada = TRUE;
 if (nodo->costeRaizNodo <= limite) 
    if (compararEstados (*nodo->pestadoPuzzle, emeta))
    {
     (*result).numMovs = 0;
     (*result).movs = construirResultado (nodo, &(*result).numMovs);
     noMetaEncontrada = FALSE;
    }
    else 
    {
     lCerrados = meterEnLista (lCerrados, nodo);
     if (nodo->costeRaizNodo < limite)
      {
       int numHijo, numOp;
 
       for (numHijo = 0, numOp = 0; numOp < NUM_OPERADORES && noMetaEncontrada; numOp++)
       {
        if (listaOperadores[numOp].aplicable(*nodo->pestadoPuzzle))
        {
         nodoGrafo *pHijo;
         nodoGrafo *pngViejo; 

         pHijo = crearNodoGrafo ();
         pHijo->pestadoPuzzle = listaOperadores[numOp].aplicar (*nodo->pestadoPuzzle);
         nodo->listaHijos->hijos[numHijo] = pHijo;
         pHijo->pnodoPadre = nodo;
         pHijo->costeRaizNodo = calcularCosteSucesor (nodo);
         numHijo++;
         (*result).maxProfundidad = max (pHijo->costeRaizNodo, (*result).maxProfundidad); 
         pngViejo = obtenerElemento (lCerrados, pHijo);
         if (pngViejo != NULL) 
	 { 	 
          (*result).nodosRepetidos++;
          destruirNodoGrafo (pHijo);
          pHijo = pngViejo; 	 
         } 
         else 
         { 
          (*result).nodosGenerados++; 	 	
          noMetaEncontrada = BLEP (pHijo, lCerrados, emeta, limite, &(*result)); 
         }
        } 
       } 
      }
     } 
 if (lCerrados != NULL && lCerrados->psiguiente != NULL)
    destruirNodoGrafo (nodo);
 return noMetaEncontrada; 
}
 
resultadoBusqueda DFID (estado einicial, estado emeta)
{
 nodoGrafo *pngInicial;
 resultadoBusqueda result;
 bool noMetaEncontrada;
 int limite;

 result.nodosGenerados = 1;
 result.maxProfundidad = 0;
 result.nodosRepetidos = 0;
 
 pngInicial = crearNodoGrafo ();
 pngInicial -> pestadoPuzzle = crearEstado ();
 pngInicial -> pnodoPadre = NULL;
 pngInicial -> costeRaizNodo = 0;
 
 copiarEstado (einicial, pngInicial -> pestadoPuzzle);
 noMetaEncontrada = TRUE;
 for (limite = 0; limite < MAXPROOF && noMetaEncontrada; limite ++)
 {
  nodoLista *listaCerrados; 
  listaCerrados = NULL;
  noMetaEncontrada = BLEP (pngInicial, listaCerrados, emeta, limite, &result); 
 } 
 return result; 
} 
/***************************************************************************************/
 
  
 
/***************************************************************************************/
/*				A*						       */ 
/***************************************************************************************/ 
 
/*
* Dado un nodo, generamos todos los sucesores posibles aplicando cada
* uno de los operadores disponibles al estado que representa dicho nodo
*/
void generarSucesores (nodoGrafo * png)
{
 int numHijo, numOp;
 
 for (numHijo = 0, numOp = 0; numOp < NUM_OPERADORES; numOp++)
 {
  if (listaOperadores[numOp].aplicable(*png->pestadoPuzzle))
  {
   nodoGrafo *pnuevoNodo;
 
   pnuevoNodo = crearNodoGrafo ();
   pnuevoNodo->pestadoPuzzle = listaOperadores[numOp].aplicar (*png->pestadoPuzzle);
   png->listaHijos->hijos[numHijo] = pnuevoNodo;
 
   numHijo++;
  }
 }
 
 png->listaHijos->numHijos = numHijo;
}
 
 
/*
* Sacamos de la lista de abiertos el nodo con el mejor valor
* de "f". En el caso de un empate, se escoge aquel con mayor
* valor de "g" (el que ya ha recorrido mas camino, tiene mas
* posibilidades de acabar antes).
*/
nodoGrafo *cogerListaAbiertos (nodoLista ** listaAbiertos)
{
 nodoLista *pnactual, *pnanterior, *pmejorNodo, *pantmejor;
 
 pnactual = pnanterior = *listaAbiertos;
 pmejorNodo = pantmejor = *listaAbiertos;
 
 while (pnactual != NULL)
 {
  int costeNodoMetaMejor;
  int costeNodoMetaActual;
 
  costeNodoMetaMejor = 1*pmejorNodo->pnodo->costeNodoMeta + 
                       1*pmejorNodo->pnodo->  costeRaizNodo;
  costeNodoMetaActual = 1*pnactual->pnodo->costeNodoMeta + 
                        1*pnactual->pnodo->costeRaizNodo;
 
  if (costeNodoMetaActual < costeNodoMetaMejor)
  {
   pantmejor=pnanterior;
   pmejorNodo=pnactual;
  }
  else
      if ((costeNodoMetaActual == costeNodoMetaMejor) &&
         (pnactual->pnodo->costeRaizNodo>pmejorNodo->pnodo->costeRaizNodo))
      {
       pantmejor=pnanterior;
       pmejorNodo=pnactual;
      }
  pnanterior = pnactual;
  pnactual = pnactual->psiguiente;
 }
 if (pmejorNodo==*listaAbiertos)
    (*listaAbiertos)=(*listaAbiertos)->psiguiente;
 else
    pantmejor->psiguiente=pmejorNodo->psiguiente;
 
 return pmejorNodo->pnodo;
}
 
 
void propagarMenorCosteASucesores (nodoGrafo * png)
{
 int numHijo;
 coste costeSucesor = calcularCosteSucesor(png);
 nodoGrafo** losHijos;

 losHijos = png->listaHijos->hijos;
 for (numHijo=0; numHijo < png->listaHijos->numHijos; numHijo++)
 {
  if (losHijos[numHijo]->costeRaizNodo > costeSucesor)
  {
   losHijos[numHijo]->costeRaizNodo = costeSucesor;
   losHijos[numHijo]->pnodoPadre = png;
   propagarMenorCosteASucesores(losHijos[numHijo]);
  }
 }
}
 
 
resultadoBusqueda A (estado einicial, estado emeta, int nHeur)
{
 nodoGrafo *pngInicial;
 bool noMetaEncontrada;
 nodoLista *listaAbiertos;
 nodoLista *listaCerrados;
 nodoGrafo *pngMejorNodo;
 resultadoBusqueda result;
  
 result.nodosGenerados = 1;
 result.maxProfundidad = 0;
 result.nodosRepetidos = 0;
  
 /* Creamos el nodo raiz */
 pngInicial = crearNodoGrafo ();
 pngInicial->pestadoPuzzle = crearEstado();
 pngInicial->pnodoPadre = NULL;	/* Condicion para ser el raiz */
 pngInicial->costeRaizNodo = 0;
 pngInicial->costeNodoMeta = calcularHeuristica(nHeur,einicial,emeta); 
 copiarEstado (einicial, pngInicial->pestadoPuzzle); 
 /* Inicializamos las listas */
 listaAbiertos = NULL;
 listaCerrados = NULL;
 listaAbiertos = meterEnLista (listaAbiertos, pngInicial);
 
 pngMejorNodo = pngInicial;
 noMetaEncontrada = TRUE;
 while ((listaAbiertos != NULL) && noMetaEncontrada)
 { 
  /* Sacamos el mejor nodo de la lista de abiertos */
  pngMejorNodo = cogerListaAbiertos (&listaAbiertos);
 
  listaCerrados = meterEnLista (listaCerrados, pngMejorNodo);
  /* Si es el estado buscado */
  if (compararEstados (*pngMejorNodo->pestadoPuzzle, emeta))
     noMetaEncontrada = FALSE;
  else
  {
   int nsuc;
   nodoGrafo **losHijos;
 
   generarSucesores (pngMejorNodo);
   losHijos = pngMejorNodo->listaHijos->hijos;
    
   /* Para cada sucesor ... */
   for (nsuc = 0; nsuc < pngMejorNodo->listaHijos->numHijos; nsuc++)
   {
    nodoGrafo *pngViejo;
 
    losHijos[nsuc]->pnodoPadre = pngMejorNodo;
    losHijos[nsuc]->costeRaizNodo = calcularCosteSucesor (pngMejorNodo);
    result.maxProfundidad = max(losHijos[nsuc]->costeRaizNodo,result.maxProfundidad);
 
    pngViejo = obtenerElemento (listaAbiertos, losHijos[nsuc]);
    if (pngViejo != NULL) /* Si esta en la lista de abiertos */
    {
     result.nodosRepetidos++;
     if (losHijos[nsuc]->costeRaizNodo < pngViejo->costeRaizNodo)
     {
      pngViejo->pnodoPadre = pngMejorNodo;
      pngViejo->costeRaizNodo = losHijos[nsuc]->costeRaizNodo;
     }
 
     destruirNodoGrafo (losHijos[nsuc]);
     losHijos[nsuc] = pngViejo;  
    }
    else
    {
     pngViejo = obtenerElemento (listaCerrados, losHijos[nsuc]);
     if (pngViejo != NULL) /* Si esta en la lista de cerrados */
      {
       result.nodosRepetidos++;
       if (losHijos[nsuc]->costeRaizNodo < pngViejo->costeRaizNodo)
       {
        pngViejo->pnodoPadre = pngMejorNodo;
        pngViejo->costeRaizNodo = losHijos[nsuc]->costeRaizNodo;
        propagarMenorCosteASucesores (pngViejo); 
       }
 
       destruirNodoGrafo (losHijos[nsuc]);
       losHijos[nsuc] = pngViejo; 
      }
      else
      /* No esta ni en Abiertos ni en Cerrados */
      {
       result.nodosGenerados++;
       losHijos[nsuc]->costeNodoMeta = 
                       calcularHeuristica (nHeur,*losHijos[nsuc]->pestadoPuzzle, emeta);
       listaAbiertos = meterEnLista (listaAbiertos, losHijos[nsuc]);
      }
     }
    }	 /* fin del for */
   }
  }	/* fin del while */
 
 
 /* Hemos encontrado la meta, ahora vamos a construir el resultado */
 result.numMovs = 0;
 if (noMetaEncontrada)
    result.movs = NULL; /* Nunca se va a dar, por la comprobacion inicial */
 else
    result.movs = construirResultado (pngMejorNodo, &result.numMovs);
 
 return result;
}
/***************************************************************************************/ 
 
 
 
/***************************************************************************************/
/*				IDA*						       */ 
/***************************************************************************************/ 
int Contorno (nodoGrafo *nodo, int limitef, estado emeta, nodoLista *lCerrados, int nHeur, 
              resultadoBusqueda *result)
{
 int siguientef = MAXCOSTE;
 
 if (nodo->costeRaizNodo + nodo->costeNodoMeta > limitef)
    siguientef = nodo->costeRaizNodo + nodo->costeNodoMeta;
 else 
  if (compararEstados (*nodo->pestadoPuzzle, emeta))
  {
   (*result).numMovs = 0; 
   (*result).movs = construirResultado (nodo, &(*result).numMovs); 
   siguientef = -1; 
  }
  else 
  { 
   int numHijo, numOp;
   lCerrados = meterEnLista (lCerrados, nodo);
   for (numHijo = 0, numOp = 0; numOp < NUM_OPERADORES && siguientef != -1; numOp++)
   {
    if (listaOperadores[numOp].aplicable(*nodo->pestadoPuzzle))
    {
     nodoGrafo *pHijo;
     nodoGrafo *pngViejo; 
     
     pHijo = crearNodoGrafo ();
     pHijo->pestadoPuzzle = listaOperadores[numOp].aplicar (*nodo->pestadoPuzzle);
     nodo->listaHijos->hijos[numHijo] = pHijo;
     pHijo->pnodoPadre = nodo;
     pHijo->costeRaizNodo = calcularCosteSucesor (nodo);
     pHijo->costeNodoMeta = calcularHeuristica (nHeur, *pHijo->pestadoPuzzle, emeta);
     numHijo++;
     (*result).maxProfundidad = max (pHijo->costeRaizNodo, (*result).maxProfundidad); 
     pngViejo = obtenerElemento (lCerrados, pHijo);
     if (pngViejo != NULL) 
     { 	 
      (*result).nodosRepetidos++;
      destruirNodoGrafo (pHijo);
      pHijo = pngViejo; 	 
     }
     else 
     { 
      int nuevaf; 
      (*result).nodosGenerados++; 	
	 
      nuevaf = limitef; 	 
      nuevaf = Contorno (pHijo, nuevaf, emeta, lCerrados, nHeur, &(*result));
      siguientef = min (siguientef, nuevaf);
     }
    } 	 	 
  } 
 }
 if (lCerrados != NULL && lCerrados->psiguiente != NULL) 
    destruirNodoGrafo (nodo); 
 
 return siguientef;
}
 
 
 
resultadoBusqueda IDA (estado einicial, estado emeta, int nHeur)
{
 nodoGrafo *pngInicial;
 resultadoBusqueda result;
 int limitef;
 nodoLista *listaCerrados;
 
 result.nodosGenerados = 1;
 result.maxProfundidad = 0;
 result.nodosRepetidos = 0;
 
 pngInicial = crearNodoGrafo ();
 pngInicial->pestadoPuzzle = crearEstado();
 pngInicial->pnodoPadre = NULL;	/* Condicion para ser el raiz */
 pngInicial->costeRaizNodo = 0;
 pngInicial->costeNodoMeta = calcularHeuristica(nHeur,einicial,emeta); 
 copiarEstado (einicial, pngInicial->pestadoPuzzle); 
 limitef = pngInicial->costeRaizNodo + pngInicial->costeNodoMeta; 
 while (-1 < limitef)
 { 
  listaCerrados = NULL;
  limitef = Contorno (pngInicial, limitef, emeta, listaCerrados, nHeur, &result); 
 } 
 
 return result; 
}
/***************************************************************************************/
 
 
 
 
/***************************************************************************************/
/*				SMA*						 */ 
/***************************************************************************************/ 
bool Vuelta (nodoArbolSMA *ptr);
void QuitarHijo (nodoArbolSMA *ptr,nodoListaSMA **Abiertos, nodoListaSMA **Cerrados); 
 
nodoListaSMA *MeterEnCerrados(nodoListaSMA *Cerrados, nodoArbolSMA *ptr)
/* Introduce en la lista Cerrados el nodo ptr que ya ha sido tratado.
Como el orden no es significativo, se introduce siempre al principio. */
{
 nodoListaSMA *pnuevo;
 
 pnuevo = crearNodoListaSMA ();
 pnuevo->pnodo = ptr;
 pnuevo->psiguiente = Cerrados;
 Cerrados = pnuevo;
 return Cerrados;
 }
 
nodoArbolSMA *ObtenerElemento(nodoListaSMA *lista, nodoArbolSMA *ptr)
/* Busca en la lista Cerrados un nodo del arbol con el mismo estado que ptr.
Si lo encuentra lo devuelve y en caso contrario devuelve NULL.
La lista Cerrados no esta ordenada. */
{
 nodoListaSMA *pactual;
 
 pactual = lista;
 while (pactual != NULL)
 if (compararEstados(*pactual->pnodo->pestado, *ptr->pestado))
    return pactual->pnodo;
 else
    pactual = pactual->psiguiente;
 return NULL;
}
 
nodoListaSMA *QuitarNodo(nodoListaSMA *lista, nodoArbolSMA *ptr)
/* Quita de la lista el nodo del arbol ptr. */
{
 nodoListaSMA *pactual, *panterior;
 bool encontrado;
 
 pactual = panterior = lista;
 encontrado = FALSE;
 while ((!encontrado) && (pactual != NULL))
 if (pactual->pnodo == ptr)
    encontrado = TRUE;
 else
 {
  panterior = pactual;
  pactual = pactual->psiguiente;
 }
 if (encontrado)
 {
  if (panterior == pactual)
     lista = pactual->psiguiente;
  else
     panterior->psiguiente = pactual->psiguiente;
  destruirNodoListaSMA(pactual);
 }
 return lista;
}
 
nodoArbolSMA *MejorNodo(nodoListaSMA *Abiertos)
/* Devuelve el nodo de m as bajo f-coste, m as profundo.
Se supone que la lista Abiertos no esta vacia */
{
 nodoListaSMA *pactual;
 nodoArbolSMA *mejor;
 int actualCosteF, mejorCosteF;
 
 mejor = Abiertos->pnodo;
 if (Vuelta(mejor)) 
    mejorCosteF = mejor->costeMinSucesoresOlvidados;
 else
    mejorCosteF = mejor->costeF;
 pactual = Abiertos->psiguiente;
 while (pactual != NULL)
 { 
  if (Vuelta(pactual->pnodo))
     actualCosteF = pactual->pnodo->costeMinSucesoresOlvidados;
  else
     actualCosteF = pactual->pnodo->costeF;
  if ((actualCosteF < mejorCosteF) || ((actualCosteF == mejorCosteF)
     && (pactual->pnodo->costeG > mejor->costeG)))
  {
   mejor = pactual->pnodo;
   mejorCosteF = actualCosteF;
  }
  pactual = pactual->psiguiente;
 }
 return mejor;
}
 
int InicializarSigSucesor(nodoArbolSMA *ptr)
/* Inicializa el campo sigSucesor del nodo ptr */
{
 bool encontrado = FALSE;
 int i = 0;

 while ((!encontrado) && (i < MAX_NUM_HIJOS))
  if ((ptr->listaHijos->hijos[i]->nodo == NULL)
     && (listaOperadores[i].aplicable(*ptr->pestado)))
     encontrado = TRUE;
  else
     i++;
 return i; 
}
 
nodoArbolSMA *SiguienteSucesor(nodoArbolSMA **ptr,int *nsuc)
/* Devuelve el psiguiente sucesor del nodo ptr y su posicion nsuc en
el array de punteros que apuntan a los sucesores del nodo ptr */
{
 nodoArbolSMA *sucesor;
 int i, posNuevoHijo;
 bool encontrado;
 
 if ((*ptr)->sigSucesor == MAX_NUM_HIJOS)
    return NULL;
 else
 {
  if (Vuelta(*ptr))
  {
   (*ptr)->vuelta = FALSE;
   (*ptr)->costeMinSucesoresOlvidados = INFINITO;
  }
  i = (*ptr)->sigSucesor;
  sucesor = crearNodoArbolSMA();
  sucesor->pestado = listaOperadores[i].aplicar(*(*ptr)->pestado);
  sucesor->sigSucesor = InicializarSigSucesor(sucesor);
  *nsuc = i;
  /* Calcular el campo sigSucesor de ptr */
  encontrado = FALSE;
  posNuevoHijo = i++;
  while ((!encontrado) && (i < MAX_NUM_HIJOS))
   if (((*ptr)->listaHijos->hijos[i]->nodo == NULL)
      && (!(*ptr)->listaHijos->hijos[i]->repetido)
      && (listaOperadores[i].aplicable(*(*ptr)->pestado)))
   {
    encontrado = TRUE;
    (*ptr)->sigSucesor = i;
   }
   else
      i++;
   if (!encontrado) /* Se han examinado todos los hijoSMA de ptr */
   {
    (*ptr)->vuelta = TRUE;
    i = 0;
    while ((!encontrado) && (i < posNuevoHijo))
     if (((*ptr)->listaHijos->hijos[i]->nodo == NULL)
        && (!(*ptr)->listaHijos->hijos[i]->repetido)
        && (listaOperadores[i].aplicable(*(*ptr)->pestado)))
     {
      encontrado = TRUE;
      (*ptr)->sigSucesor = i;
     }
     else
        i++;
    if (!encontrado)
       (*ptr)->sigSucesor = MAX_NUM_HIJOS;
   }
   return sucesor;
  }
}
 
void PonerHijo(nodoArbolSMA **padre, nodoArbolSMA **hijoSMA,int nsuc)
/* Pone hijoSMA como sucesor de padre. Utiliza nsuc como la posicion
en el array de hijoSMA que apunta a hijoSMA. */
{
 
 /* Pongo hijoSMA como sucesor de padre */
 (*padre)->listaHijos->hijos[nsuc]->nodo = *hijoSMA;
 (*padre)->listaHijos->numHijos++;
 /* Pongo padre como padre de hijoSMA */
 (*hijoSMA)->padre = *padre;
}
 
bool Vuelta (nodoArbolSMA *ptr)
/* Indica si se ha dado una vuelta examinando todos los sucesores de ptr */
{
 return (ptr->vuelta); 
}
 
bool SucesoresEnMemoria (nodoArbolSMA *ptr)
/* Indica si el nodo del arbol ptr tiene todos sus sucesores actualmente en
memoria. */
{
 if ((ptr->sigSucesor == MAX_NUM_HIJOS) && (ptr->listaHijos->numHijos != 0))
    return TRUE;
 else
    return FALSE;
}
 
coste CalcularCosteG_Sucesor(nodoArbolSMA *ptr)
/* Calcula el nuevo coste para llegar de la raiz a los sucesores de ptr */
{
 return (ptr->costeG + 1);
}
 
coste CalcularCosteF(nodoArbolSMA *padre,nodoArbolSMA *hijoSMA)
/* Calcula el f-coste de hijoSMA teniendo en cuenta PATHMAX */
{
 return (max(padre->costeF, hijoSMA->costeG + hijoSMA->costeH));
}
 
void PropagarMejora(nodoListaSMA **Abiertos, nodoArbolSMA **ptr)
/* Propaga la mejora en el coste de ptr a sus sucesores */
{
 int i;
 coste costeG_Sucesor = CalcularCosteG_Sucesor(*ptr);
 hijoSMA** losHijos;
 
 losHijos = (*ptr)->listaHijos->hijos;
 for (i=0; i < MAX_NUM_HIJOS; i++)
 {
  if ((losHijos[i]->nodo != NULL) 
     && (losHijos[i]->nodo->costeG > costeG_Sucesor))
  {
   losHijos[i]->nodo->costeG = costeG_Sucesor;
   losHijos[i]->nodo->costeF = CalcularCosteF(*ptr, losHijos[i]->nodo);
   losHijos[i]->nodo->padre = *ptr;
   if (losHijos[i]->nodo->listaHijos->numHijos != 0) /* Tiene hijoSMA */
      PropagarMejora(Abiertos, &losHijos[i]->nodo);	 
  }
 }
}
 
int MinCosteF_Sucesores(nodoArbolSMA *ptr)
/* Devuelve menor f-coste de todos sus sucesores */
{
 int i=0, menor;
 
 menor = ptr->costeMinSucesoresOlvidados;
 if (ptr->listaHijos->numHijos != 0) /* no hace falta */
  while (i < MAX_NUM_HIJOS)
  {
   if ((ptr->listaHijos->hijos[i]->nodo != NULL)
      && (ptr->listaHijos->hijos[i]->nodo->costeF < menor)) 
      menor = ptr->listaHijos->hijos[i]->nodo->costeF;
   i++;
  }
 return menor;
}
 
nodoArbolSMA *Backup(nodoArbolSMA *ptr)
/* Actualiza ptr f-coste y aquellos de sus antepasados si es necesario */
{
 int anterior;
 
 if (Vuelta(ptr))
 {
  anterior = ptr->costeF;
  ptr->costeF = MinCosteF_Sucesores(ptr);
  if ((anterior!=ptr->costeF) && (ptr->padre != NULL))
  ptr->padre = Backup(ptr->padre); 
 }
 return ptr;
}
 
void BorrarPeorNodo(nodoListaSMA **Abiertos, nodoListaSMA **Cerrados)
/* Borra el nodo de m as alto f-coste, m as superficial.
Se supone que la lista Abiertos no esta vacia.
Ese nodo lo quita de la lista de sucesores de su padres e inserta sus
padres en Abiertos si es necesario (si estan en Cerrados) */
{
 nodoListaSMA *pactual, *antactual,
 *peor, *antpeor;
 int actualCosteF, peorCosteF;
 
 pactual = antactual = *Abiertos;
 peorCosteF = 0;
 while (pactual != NULL)
 {
  if (pactual->pnodo->listaHijos->numHijos == 0) /* Solo nodos hojas */
  { 
   if (Vuelta(pactual->pnodo))
      actualCosteF = pactual->pnodo->costeMinSucesoresOlvidados;
   else
      actualCosteF = pactual->pnodo->costeF;
   if ((actualCosteF > peorCosteF) || ((actualCosteF == peorCosteF)
      && (pactual->pnodo->costeG < peor->pnodo->costeG)))
   {
    antpeor = antactual;
    peor = pactual;
    peorCosteF = actualCosteF;
   }
  }
  antactual = pactual;
  pactual = pactual->psiguiente;
 }
 if (antpeor == peor)
    *Abiertos = peor->psiguiente;
 else
    antpeor->psiguiente = peor->psiguiente;
 QuitarHijo(peor->pnodo, Abiertos, Cerrados);
 destruirNodoArbolSMA(peor->pnodo);
 destruirNodoListaSMA(peor);
}
 
void QuitarHijo(nodoArbolSMA *ptr,nodoListaSMA **Abiertos, nodoListaSMA **Cerrados)
/* Quitar el nodo ptr de la lista de sucesores de su padre e inserta
sus padres en Abiertos si es necesario. Actualiza los campos sigSucesor y
costeMinSucesoresOlvidados. */
{
 int i, costeF_sucesor;
 bool encontrado;
 
 if (Vuelta(ptr)) 
    costeF_sucesor = ptr->costeMinSucesoresOlvidados;
 else
    costeF_sucesor = ptr->costeF;
 /* Borro ptr como hijoSMA de su padre */
 encontrado = FALSE;
 i = 0;
 while (!encontrado)
  if (ptr->padre->listaHijos->hijos[i]->nodo == ptr)
  {
   /* Actualizar el campo costeMinSucesoresOlvidados */
   if (ptr->padre->costeMinSucesoresOlvidados > costeF_sucesor)
      ptr->padre->costeMinSucesoresOlvidados = costeF_sucesor; 
   ptr->padre->listaHijos->hijos[i]->nodo = NULL;
   if (SucesoresEnMemoria(ptr->padre))
   {
    *Cerrados = QuitarNodo(*Cerrados, ptr->padre);
    *Abiertos = MeterEnCerrados(*Abiertos, ptr->padre);
    ptr->padre->sigSucesor = i;
   }
   else
    if (Vuelta(ptr->padre) && (ptr->padre->sigSucesor > i))
       ptr->padre->sigSucesor = i;
   ptr->padre->listaHijos->numHijos--;
   encontrado = TRUE;
  }
 else 
    i++;
}
 
void QuitarHijoRepetido(nodoArbolSMA *ptr, nodoListaSMA **Abiertos 
, nodoListaSMA **Cerrados)
/* Quitar el nodo ptr de la lista de sucesores de su padre e inserta
sus padres en Abiertos si es necesario. */
{
 int i;
 bool encontrado;
 
 encontrado = FALSE;
 i = 0;
 while (!encontrado)
  if (ptr->padre->listaHijos->hijos[i]->nodo == ptr)
  {
   ptr->padre->listaHijos->hijos[i]->repetido = TRUE; 
   ptr->padre->listaHijos->hijos[i]->nodo = NULL;
   if ((SucesoresEnMemoria(ptr->padre))&& (ptr->padre->listaHijos->numHijos == 1))
   {
    *Cerrados = QuitarNodo(*Cerrados, ptr->padre);
    *Abiertos = MeterEnCerrados(*Abiertos, ptr->padre);
    ptr->padre->costeF = INFINITO;
    ptr->padre->costeMinSucesoresOlvidados = INFINITO;
   }
   ptr->padre->listaHijos->numHijos--;
   encontrado = TRUE;
  }
  else 
     i++;
}
 
movimiento *construirResultadoSMA(nodoArbolSMA * pnodo, int *pnumMovs)
/* Construye el camino de la solucion de la busqueda */
{
 movimiento *movs;
 
 if (pnodo->padre == NULL)
 {
  /* Obtenemos memoria */
  movs = (movimiento *) malloc ((*pnumMovs) * sizeof (movimiento));
 }
 else
 {
  int n = *pnumMovs; 
  
  (*pnumMovs)++; 
  movs = construirResultadoSMA(pnodo->padre, pnumMovs); 
  n = (*pnumMovs) - n - 1;
  if (pnodo->pestado->filaEspacioBlanco == pnodo->padre->pestado->filaEspacioBlanco)  
   if (pnodo->pestado->colEspacioBlanco == pnodo->padre->pestado->colEspacioBlanco+1)
      movs[n] = ESTE; 
   else
      movs[n] = OESTE;  
  else
  {
   if (pnodo->pestado->filaEspacioBlanco == pnodo->padre->pestado->filaEspacioBlanco+1)
      movs[n] = SUR;
   else
      movs[n] = NORTE; 
  } 
 }
 return movs;
}
 
/* Busca la solucion segun el algoritmo SMA para ir de un estado
inicial einicial hasta un estado emeta siguiendo una heuristica nHeur.
El resultado de dicha busqueda se devuelve en una estructura
tipo resultadoBusqueda. En caso de no encontrar solucion se pone
el campo movs de dicha estructura a nulo, y si adem as eso se produce
por no existir memoria suficiente se pone el campo booleano
memInsuficiente a TRUE. Asi distinguimos el caso de no encontrar la
solucion por no tener memoria al de no encontrarla por no existir
(el campo memInsuficiente estara a FALSE). */

resultadoBusqueda SMA (estado einicial, estado emeta, int nHeur)
{
 nodoListaSMA *Abiertos, *Cerrados;
 nodoArbolSMA *inicial, *mejor, *sucesor, *viejo;
 int usados = 1, nsuc, x;
 resultadoBusqueda result;
 
 result.nodosGenerados = 1;
 result.nodosRepetidos = 0;
 result.maxProfundidad = 0;
 inicial = crearNodoArbolSMA();
 inicial->pestado = crearEstado();
 inicial->padre = NULL;	/* Nodo raiz */
 inicial->costeG = 0;
 inicial->costeH = calcularHeuristica(nHeur,einicial,emeta);
 inicial->costeF = inicial->costeG + inicial->costeH;
 copiarEstado(einicial, inicial->pestado);
 inicial->sigSucesor = InicializarSigSucesor(inicial);
 /* Inicializamos las listas */
 Abiertos = NULL;
 Cerrados = NULL;
 Abiertos = MeterEnCerrados(Abiertos, inicial);
  
 mejor = inicial;
 for (;;) /* Bucle infinito */
 {
  if (Abiertos == NULL) /* Solucion no encontrada */
  {
   result.movs = NULL;
   return result;
  }
  else
  {
   mejor = MejorNodo(Abiertos);        /* la 1 vez no hace falta */
   if (mejor->costeF == INFINITO)      /* Solucion no encontrada */
   {                                   /* con la memoria existente */
    result.movs = NULL;
    return result;
   }
   else
    if (compararEstados (*mejor->pestado, emeta))
    {                                  /* Solucion encontrada */
     result.numMovs = 0;
     result.movs = construirResultadoSMA(mejor, &result.numMovs);
     return result;
    }
    else
    {
     sucesor = SiguienteSucesor(&mejor, &nsuc);
     sucesor->costeG = CalcularCosteG_Sucesor(mejor);
     if ((viejo = ObtenerElemento(Abiertos, sucesor)) != NULL)
     {
      if (sucesor->costeG < viejo->costeG)
      {
       QuitarHijoRepetido(viejo, &Abiertos, &Cerrados);
       PonerHijo(&mejor, &viejo, nsuc);
       viejo->costeG = sucesor->costeG;
       viejo->costeF = CalcularCosteF(mejor, viejo);
       if (viejo->listaHijos->numHijos != 0) /* Tiene hijoSMA */
          PropagarMejora(&Abiertos, &viejo);
      }
      else
	  mejor->listaHijos->hijos[nsuc]->repetido = TRUE;
      destruirNodoArbolSMA(sucesor);
      result.nodosRepetidos++;
     }
     else
      if ((viejo = ObtenerElemento(Cerrados, sucesor)) != NULL)
      {
       if (sucesor->costeG < viejo->costeG)
       {
        QuitarHijoRepetido(viejo, &Abiertos, &Cerrados);
        PonerHijo(&mejor, &viejo, nsuc);
        viejo->costeG = sucesor->costeG;
        viejo->costeF = CalcularCosteF(mejor, viejo);
        PropagarMejora(&Abiertos, &viejo);
       }
       else
          mejor->listaHijos->hijos[nsuc]->repetido = TRUE;
       destruirNodoArbolSMA(sucesor);
       result.nodosRepetidos++;
      }
    else
     {		
      PonerHijo(&mejor, &sucesor, nsuc);
      sucesor->costeH = CalcularHeuristica(nHeur,*sucesor->pestado,emeta);
      if (!compararEstados (*sucesor->pestado, emeta) && 
	 (sucesor->costeG + 1 == MAX_NODOS)) /* maxima profundidad */
	 sucesor->costeF = INFINITO;
      else
	 sucesor->costeF = CalcularCosteF(mejor, sucesor);
      Abiertos = MeterEnCerrados(Abiertos, sucesor);
      result.maxProfundidad = max(sucesor->costeG,
      result.maxProfundidad);
      result.nodosGenerados++;
      usados++;
     }
     x = 1;
     if (Vuelta(mejor))                 /* Se han examinado todos sus sucesores */
        mejor = Backup(mejor);
     if (SucesoresEnMemoria(mejor)) 
     {                                   /* Todos sus sucesores en memoria */
      Abiertos = QuitarNodo(Abiertos, mejor);
      Cerrados = MeterEnCerrados(Cerrados, mejor);
     }
     if (usados > MAX_NODOS) /* Memoria llena */
     {
      BorrarPeorNodo(&Abiertos, &Cerrados);
      usados--;
     }
    }
  }
 }
}
 
/***************************************************************************************/ 
 
 
resultadoBusqueda busqueda (estado einicial, estado emeta, int nAlg, int nHeur) 
{
 resultadoBusqueda res;
 
 switch (nAlg) {
   case 0: res = DFID (einicial,emeta); 
	 break;
   case 1: res = A (einicial,emeta, nHeur);
  	 break; 
   case 2: res = IDA (einicial,emeta, nHeur);
	 break; 
   case 3: res = SMA (einicial,emeta, nHeur);
	 break; 
 } 	 
 return res;
} 	 
 
 
movimiento* construirResultado (nodoGrafo * pnodo, int *pnumMovs)
{
 movimiento *movs;
 
 
 if (pnodo->pnodoPadre == NULL)
 {
  /* Obtenemos memoria */
  movs = (movimiento *) malloc ((*pnumMovs) * sizeof (movimiento));
 }
 else
 {
  int n = *pnumMovs; 
 
  (*pnumMovs)++; 
  movs = construirResultado (pnodo->pnodoPadre, pnumMovs);
  n = (*pnumMovs) - n - 1;
  if (pnodo->pestadoPuzzle->filaEspacioBlanco == 
      pnodo->pnodoPadre->pestadoPuzzle->filaEspacioBlanco)
  {
   if (pnodo->pestadoPuzzle->colEspacioBlanco ==
       pnodo->pnodoPadre->pestadoPuzzle->colEspacioBlanco+1)
      movs[n] = ESTE; 
   else
      movs[n] = OESTE; 
  } 
  else
  {
   if (pnodo->pestadoPuzzle->filaEspacioBlanco ==
       pnodo->pnodoPadre->pestadoPuzzle->filaEspacioBlanco+1)
      movs[n] = SUR;
   else
      movs[n] = NORTE; 
  } 
 }
 return movs;
}