Algoritme SSS

L'algoritme SSS* (SSS estrela) es classifica dins dels algoritmes de busca basada en grafos, de manera similar a com ho fan els algoritme A* o minimax. Es diferencia del algoritme alfa-beta en que utilisa una llista com a estructura.

Es genera un arbre en els que els nodos són de tipo MIN o MAX. Cada nodo de l'arbre és una tupla (N, s, h):

N: Nomene
s: Estat (viu o solucionat)
h: Valor de la solució ( inicialment menys infinit si es vol maximizar la funció)

Eixemple

Siga el grafo

Llista	Descripció operació a realisar
( $ϵ, v, \infty$ )	$ϵ$ és Max, despuix insertar fills
( $1, v, \infty$ ), ( $2, v, \infty$ )	$1$ és Min, despuix insertar primer fill
( $1.1, v, \infty$ ), ( $2, v, \infty$ )	$1.1$ és Max, despuix insertar fills
( $1.1.1, v, \infty$ ), ( $1.1.2, v, \infty$ ), ( $2, v, \infty$ )	$1.1.1$ és terminal, despuix, canviar estat
( $1.1.2, v, \infty$ ), ( $2, v, \infty$ ), ( $1.1.1, s, m i n (\infty, 3)$ )	$1.1.2$ és terminal, despuix, canviar estat
( $2, v, \infty$ ), ( $1.1.2, s, m i n (\infty, 9)$ ), ( $1.1.1, s, 3$ )	$2$ és Min, despuix, insertar primer fill
( $2.1, v, \infty$ ), ( $1.1.2, s, 9$ ), ( $1.1.1, s, 3$ )	$2.1$ és Max, despuix, insertar fills
( $2.1.1, v, \infty$ ), ( $2.1.2, v, \infty$ ), ( $1.1.2, s, 9$ ), ( $1.1.1, s, 3$ )	$2.1.1$ és terminal, despuix, canviar estat
( $2.1.2, v, \infty$ ), ( $1.1.2, s, 9$ ), ( $1.1.1, s, 3$ ), ( $2.1.1, s, m i n (\infty, 2)$ )	$2.1.2$ és terminal, despuix, canviar estat
( $1.1.2, s, 9$ ), ( $2.1.2, s, m i n (\infty, 8)$ ) ,( $1.1.1, s, 3$ ), ( $2.1.1, s, 2$ )	$1.1.2$ és min, terminal i estat= $s$ , despuix, insertar pare i eliminar successors del pare
( $1.1, s, 9$ ), ( $2.1.2, s, 8$ ) , ( $2.1.1, s, 2$ )	$1.1$ és max i estat= $s$ , despuix, insertar germà en estat= $v$
( $1.2, v, 9$ ), ( $2.1.2, s, 8$ ) , ( $2.1.1, s, 2$ )	$1.2$ és Max, despuix, insertar fills
( $1.2.1, v, 9$ ), ( $1.2.2, v, 9$ ), ( $2.1.2, s, 8$ ) , ( $2.1.1, s, 2$ )	$1.2.1$ és terminal, despuix, canviar estat
( $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$ és terminal, despuix, canviar estat
( $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$ és min, terminal i estat= $s$ , despuix, insertar pare i eliminar successors del pare
( $2.1, s, 8$ ) , ( $1.2.1, s, 7$ ), ( $1.2.2, s, 5$ )	$2.1$ és max i estat= $s$ , despuix, insertar germà en estat= $v$
( $2.2, v, 8$ ) , ( $1.2.1, s, 7$ ), ( $1.2.2, s, 5$ )	$2.2$ és max, despuix, insertar fills
( $2.2.1, v, 8$ ), ( $2.2.2, v, 8$ ) , ( $1.2.1, s, 7$ ), ( $1.2.2, s, 5$ )	$2.2.1$ és terminal, despuix, canviar estat i quedar-se en el mínim 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$ és terminal, despuix, canviar estat i quedar-se en el mínim 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$ és min, terminal i estat= $s$ , despuix, insertar pare i eliminar successors del pare
( $2.2, s, 8$ ) , ( $1.2.1, s, 7$ ), ( $1.2.2, s, 5$ )	és Max i no hi ha més germans, despuix, insertar pare
( $2, s, 8$ ) , ( $1.2.1, s, 7$ ), ( $1.2.2, s, 5$ )	és Min i estat= $s$ , despuix, insertar pare i eliminar successors del pare
( $ϵ, s, 8$ )	STOP

Vore també

Algoritme minimax

Este artícul conté una traducció derivada de «Algoritmo SSS» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.