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

editar

Sea el grafo

 

Lista Descripción operación a realizar
( )   es Max, luego insertar hijos
( ), ( )   es Min, luego insertar primer hijo
( ), ( )   es Max, luego insertar hijos
( ), ( ), ( )   es terminal, luego, cambiar estado
( ), ( ), ( )   es terminal, luego, cambiar estado
( ), ( ), ( )   es Min, luego, insertar primer hijo
( ), ( ), ( )   es Max, luego, insertar hijos
( ), ( ), ( ), ( )   es terminal, luego, cambiar estado
( ), ( ), ( ), ( )   es terminal, luego, cambiar estado
( ), ( ) ,( ), ( )   es min, terminal y estado= , luego, insertar padre y eliminar sucesores del padre
( ), ( ) , ( )   es max y estado= , luego, insertar hermano con estado= 
( ), ( ) , ( )   es Max, luego, insertar hijos
( ), ( ), ( ) , ( )   es terminal, luego, cambiar estado
( ), ( ) , ( ), ( )   es terminal, luego, cambiar estado
( ) , ( ), ( ) , ( )   es min, terminal y estado= , luego, insertar padre y eliminar sucesores del padre
( ) , ( ), ( )   es max y estado= , luego, insertar hermano con estado= 
( ) , ( ), ( )   es max, luego, insertar hijos
( ), ( ) , ( ), ( )   es terminal, luego, cambiar estado y quedarse con el mínimo valor
( ) , ( ), ( ), ( )   es terminal, luego, cambiar estado y quedarse con el mínimo valor
( ) , ( ), ( ), ( )   es min, terminal y estado= , luego, insertar padre y eliminar sucesores del padre
( ) , ( ), ( ) es Max y no hay más hermanos, luego, insertar padre
( ) , ( ), ( ) es Min y estado= , luego, insertar padre y eliminar sucesores del padre
( ) STOP

Véase también

editar

Enlaces externos

editar