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
(${\displaystyle \epsilon ,v,\infty }$)	${\displaystyle \epsilon }$ es Max, luego insertar hijos
(${\displaystyle 1,v,\infty }$), (${\displaystyle 2,v,\infty }$)	${\displaystyle 1}$ es Min, luego insertar primer hijo
(${\displaystyle 1.1,v,\infty }$), (${\displaystyle 2,v,\infty }$)	${\displaystyle 1.1}$ es Max, luego insertar hijos
(${\displaystyle 1.1.1,v,\infty }$), (${\displaystyle 1.1.2,v,\infty }$), (${\displaystyle 2,v,\infty }$)	${\displaystyle 1.1.1}$ es terminal, luego, cambiar estado
(${\displaystyle 1.1.2,v,\infty }$), (${\displaystyle 2,v,\infty }$), (${\displaystyle 1.1.1,s,min(\infty ,3)}$)	${\displaystyle 1.1.2}$ es terminal, luego, cambiar estado
(${\displaystyle 2,v,\infty }$), (${\displaystyle 1.1.2,s,min(\infty ,9)}$), (${\displaystyle 1.1.1,s,3}$)	${\displaystyle 2}$ es Min, luego, insertar primer hijo
(${\displaystyle 2.1,v,\infty }$), (${\displaystyle 1.1.2,s,9}$), (${\displaystyle 1.1.1,s,3}$)	${\displaystyle 2.1}$ es Max, luego, insertar hijos
(${\displaystyle 2.1.1,v,\infty }$), (${\displaystyle 2.1.2,v,\infty }$), (${\displaystyle 1.1.2,s,9}$), (${\displaystyle 1.1.1,s,3}$)	${\displaystyle 2.1.1}$ es terminal, luego, cambiar estado
(${\displaystyle 2.1.2,v,\infty }$), (${\displaystyle 1.1.2,s,9}$), (${\displaystyle 1.1.1,s,3}$), (${\displaystyle 2.1.1,s,min(\infty ,2)}$)	${\displaystyle 2.1.2}$ es terminal, luego, cambiar estado
(${\displaystyle 1.1.2,s,9}$), (${\displaystyle 2.1.2,s,min(\infty ,8)}$) ,(${\displaystyle 1.1.1,s,3}$), (${\displaystyle 2.1.1,s,2}$)	${\displaystyle 1.1.2}$ es min, terminal y estado=${\displaystyle s}$, luego, insertar padre y eliminar sucesores del padre
(${\displaystyle 1.1,s,9}$), (${\displaystyle 2.1.2,s,8}$) , (${\displaystyle 2.1.1,s,2}$)	${\displaystyle 1.1}$ es max y estado=${\displaystyle s}$, luego, insertar hermano con estado=${\displaystyle v}$
(${\displaystyle 1.2,v,9}$), (${\displaystyle 2.1.2,s,8}$) , (${\displaystyle 2.1.1,s,2}$)	${\displaystyle 1.2}$ es Max, luego, insertar hijos
(${\displaystyle 1.2.1,v,9}$), (${\displaystyle 1.2.2,v,9}$), (${\displaystyle 2.1.2,s,8}$) , (${\displaystyle 2.1.1,s,2}$)	${\displaystyle 1.2.1}$ es terminal, luego, cambiar estado
(${\displaystyle 1.2.2,v,9}$), (${\displaystyle 2.1.2,s,8}$) , (${\displaystyle 1.2.1,s,min(9,7)}$), (${\displaystyle 2.1.1,s,2}$)	${\displaystyle 1.2.2}$ es terminal, luego, cambiar estado
(${\displaystyle 2.1.2,s,8}$) , (${\displaystyle 1.2.1,s,7}$), (${\displaystyle 1.2.2,s,min(9,5)}$) , (${\displaystyle 2.1.1,s,2}$)	${\displaystyle 2.1.2}$ es min, terminal y estado=${\displaystyle s}$, luego, insertar padre y eliminar sucesores del padre
(${\displaystyle 2.1,s,8}$) , (${\displaystyle 1.2.1,s,7}$), (${\displaystyle 1.2.2,s,5}$)	${\displaystyle 2.1}$ es max y estado=${\displaystyle s}$, luego, insertar hermano con estado=${\displaystyle v}$
(${\displaystyle 2.2,v,8}$) , (${\displaystyle 1.2.1,s,7}$), (${\displaystyle 1.2.2,s,5}$)	${\displaystyle 2.2}$ es max, luego, insertar hijos
(${\displaystyle 2.2.1,v,8}$), (${\displaystyle 2.2.2,v,8}$) , (${\displaystyle 1.2.1,s,7}$), (${\displaystyle 1.2.2,s,5}$)	${\displaystyle 2.2.1}$ es terminal, luego, cambiar estado y quedarse con el mínimo valor
(${\displaystyle 2.2.2,v,8}$) , (${\displaystyle 1.2.1,s,7}$), (${\displaystyle 1.2.2,s,5}$), (${\displaystyle 2.2.1,s,min(8,1)}$)	${\displaystyle 2.2.2}$ es terminal, luego, cambiar estado y quedarse con el mínimo valor
(${\displaystyle 2.2.2,s,min(8,9)}$) , (${\displaystyle 1.2.1,s,7}$), (${\displaystyle 1.2.2,s,5}$), (${\displaystyle 2.2.1,s,1}$)	${\displaystyle 2.2.2}$ es min, terminal y estado=${\displaystyle s}$, luego, insertar padre y eliminar sucesores del padre
(${\displaystyle 2.2,s,8}$) , (${\displaystyle 1.2.1,s,7}$), (${\displaystyle 1.2.2,s,5}$)	es Max y no hay más hermanos, luego, insertar padre
(${\displaystyle 2,s,8}$) , (${\displaystyle 1.2.1,s,7}$), (${\displaystyle 1.2.2,s,5}$)	es Min y estado=${\displaystyle s}$, luego, insertar padre y eliminar sucesores del padre
(${\displaystyle \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.