title: Algoritmo SSS
text: # Algoritmo SSS
  
  El algoritmo SSS* (SSS estrella) se clasifica dentro de los algoritmos de búsqueda basada en grafos, de manera similar a como lo hacen los algoritmo A* o minimax. Se diferencia del algoritmo alfa-beta en que utiliza una lista como estructura.
  
  Se genera un árbol en los que los nodos son de tipo MIN o MAX. Cada nodo del árbol es una tupla (N, s, h):
  
  * N: Nombre
  * s: Estado (vivo o solucionado)
  * h: Valor de la solución ( inicialmente menos infinito si se quiere maximizar la función)
  
  ## Ejemplo
  
  Sea el grafo
  
  | Lista | Descripción operación a realizar |
  | - | - |
  | ($\epsilon ,v,\infty$) | $\epsilon$ es Max, luego insertar hijos |
  | ($1,v,\infty$), ($2,v,\infty$) | $1$ es Min, luego insertar primer hijo |
  | ($1.1,v,\infty$), ($2,v,\infty$) | $1.1$ es Max, luego insertar hijos |
  | ($1.1.1,v,\infty$), ($1.1.2,v,\infty$), ($2,v,\infty$) | $1.1.1$ es terminal, luego, cambiar estado |
  | ($1.1.2,v,\infty$), ($2,v,\infty$), ($1.1.1,s,min(\infty ,3)$) | $1.1.2$ es terminal, luego, cambiar estado |
  | ($2,v,\infty$), ($1.1.2,s,min(\infty ,9)$), ($1.1.1,s,3$) | $2$ es Min, luego, insertar primer hijo |
  | ($2.1,v,\infty$), ($1.1.2,s,9$), ($1.1.1,s,3$) | $2.1$ es Max, luego, insertar hijos |
  | ($2.1.1,v,\infty$), ($2.1.2,v,\infty$), ($1.1.2,s,9$), ($1.1.1,s,3$) | $2.1.1$ es terminal, luego, cambiar estado |
  | ($2.1.2,v,\infty$), ($1.1.2,s,9$), ($1.1.1,s,3$), ($2.1.1,s,min(\infty ,2)$) | $2.1.2$ es terminal, luego, cambiar estado |
  | ($1.1.2,s,9$), ($2.1.2,s,min(\infty ,8)$) ,($1.1.1,s,3$), ($2.1.1,s,2$) | $1.1.2$ es min, terminal y estado=$s$, luego, insertar padre y eliminar sucesores del padre |
  | ($1.1,s,9$), ($2.1.2,s,8$) , ($2.1.1,s,2$) | $1.1$ es max y estado=$s$, luego, insertar hermano con estado=$v$ |
  | ($1.2,v,9$), ($2.1.2,s,8$) , ($2.1.1,s,2$) | $1.2$ es Max, luego, insertar hijos |
  | ($1.2.1,v,9$), ($1.2.2,v,9$), ($2.1.2,s,8$) , ($2.1.1,s,2$) | $1.2.1$ es terminal, luego, cambiar estado |
  | ($1.2.2,v,9$), ($2.1.2,s,8$) , ($1.2.1,s,min(9,7)$), ($2.1.1,s,2$) | $1.2.2$ es terminal, luego, cambiar estado |
  | ($2.1.2,s,8$) , ($1.2.1,s,7$), ($1.2.2,s,min(9,5)$) , ($2.1.1,s,2$) | $2.1.2$ es min, terminal y estado=$s$, luego, insertar padre y eliminar sucesores del padre |
  | ($2.1,s,8$) , ($1.2.1,s,7$), ($1.2.2,s,5$) | $2.1$ es max y estado=$s$, luego, insertar hermano con estado=$v$ |
  | ($2.2,v,8$) , ($1.2.1,s,7$), ($1.2.2,s,5$) | $2.2$ es max, luego, insertar hijos |
  | ($2.2.1,v,8$), ($2.2.2,v,8$) , ($1.2.1,s,7$), ($1.2.2,s,5$) | $2.2.1$ es terminal, luego, cambiar estado y quedarse con el mínimo valor |
  | ($2.2.2,v,8$) , ($1.2.1,s,7$), ($1.2.2,s,5$), ($2.2.1,s,min(8,1)$) | $2.2.2$ es terminal, luego, cambiar estado y quedarse con el mínimo valor |
  | ($2.2.2,s,min(8,9)$) , ($1.2.1,s,7$), ($1.2.2,s,5$), ($2.2.1,s,1$) | $2.2.2$ es min, terminal y estado=$s$, luego, insertar padre y eliminar sucesores del padre |
  | ($2.2,s,8$) , ($1.2.1,s,7$), ($1.2.2,s,5$) | es Max y no hay más hermanos, luego, insertar padre |
  | ($2,s,8$) , ($1.2.1,s,7$), ($1.2.2,s,5$) | es Min y estado=$s$, luego, insertar padre y eliminar sucesores del padre |
  | ($\epsilon ,s,8$) | STOP |
  