Algoritmo SSS

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, 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

( $\epsilon , s , 8$ ) STOP

Véase también

Algoritmo minimax

Enlaces externos

Tecnicas de Inteligencia Artificial: SSS* Busqueda en juegos

Categoría:
Algoritmos de búsqueda

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, 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
( $\epsilon , s , 8$ )	STOP