Algoritmo SSS

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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

Fia-sss.png

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[editar]

Enlaces externos[editar]