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
( $ϵ, v, \infty$ )	$ϵ$ 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, m i n (\infty, 3)$ )	$1.1.2$ es terminal, luego, cambiar estado
( $2, v, \infty$ ), ( $1.1.2, s, m i n (\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, m i n (\infty, 2)$ )	$2.1.2$ es terminal, luego, cambiar estado
( $1.1.2, s, 9$ ), ( $2.1.2, s, m i n (\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, m i n (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, m i n (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, m i n (8, 1)$ )	$2.2.2$ es terminal, luego, cambiar estado y quedarse con el mínimo valor
( $2.2.2, s, m i n (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
( $ϵ, s, 8$ )	STOP