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

Véase también

• Algoritmo minimax

Enlaces externos

• Técnicas de Inteligencia Artificial: SSS* Búsqueda en juegos Archivado el 17 de diciembre de 2009 en Wayback Machine.

• Datos: Q3492668