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
() 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]