Algoritmo SSS
# 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 |
