SSS * se basa en la noción de árboles de soluciones . Informalmente, se puede formar un árbol de solución a partir de cualquier árbol de juego arbitrario podando el número de ramas en cada nodo MAX a uno. Tal árbol representa una estrategia completa para MAX, ya que especifica exactamente una acción MAX para cada secuencia posible de movimientos realizados por el oponente. Dado un árbol de juego, SSS * busca a través del espacio de árboles de solución parcial, analizando gradualmente subárboles cada vez más grandes, y finalmente produce un árbol de solución único con el mismo valor raíz y Minimax que el árbol de juego original. SSS * nunca examina un nodo que poda alfa-betapodría podar, y puede podar algunas ramas que alfa-beta no. Stockman especuló que SSS *, por lo tanto, puede ser un mejor algoritmo general que alfa-beta. Sin embargo, Igor Roizen y Judea Pearl han demostrado [1] que el ahorro en el número de posiciones que SSS * evalúa en relación con alfa / beta es limitado y generalmente no es suficiente para compensar el aumento de otros recursos (por ejemplo, el almacenamiento y la clasificación de una lista de nodos necesarios por la mejor naturaleza del algoritmo). Sin embargo, Aske Plaat , Jonathan Schaeffer, Wim Pijls y Arie de Bruin han demostrado que una secuencia de llamadas alfa-beta de ventana nula es equivalente a SSS * (es decir, expande los mismos nodos en el mismo orden) cuando se usa alfa-beta con una tabla de transposición , como es el caso en todos los programas de juego para ajedrez, damas, etc. Ahora ya no era necesario almacenar y ordenar la lista ABIERTA. Esto permitió la implementación de (un algoritmo equivalente a) SSS * en programas de juegos con calidad de torneo. Los experimentos demostraron que en realidad funcionó mejor que Alpha-Beta en la práctica, pero que no superó a NegaScout . [2]
La reformulación de un algoritmo best-first como una secuencia de llamadas de profundidad primero impulsó la formulación de una clase de algoritmos alfa-beta de ventana nula, de los cuales MTD-f es el ejemplo más conocido.
Algoritmo [ editar ]
Hay una cola de prioridad ABIERTA que almacena estados
o los nodos, donde 
- identificador de nodo ( la notación de Dewey se usa para identificar nodos,
es una raíz) 
- estado del nodo (L: el nodo está activo, lo que significa que aún no está resuelto y S: el nodo está resuelto), 
- valor del nodo resuelto. Los elementos en la cola ABIERTA se ordenan descendiendo por su
valor. Si más de un nodo tiene el mismo valor de, se elige un nodo más a la izquierda en el árbol.
ABIERTO: = {(e, L, inf)}
while (verdadero) // repetir hasta que se detenga
pop un elemento p = (J, s, h) desde el encabezado de la cola ABIERTA
si J == e y s == S
DETENGA el algoritmo y devuelva h como resultado
más
aplicar operador gamma para p
operador para 
se define de la siguiente manera:
si s == L
si J es un nodo terminal
(1.) agregue (J, S, min (h, valor (J))) a ABRIR
si J es un nodo MIN
(2.) agregue (J.1, L, h) a ABRIR
más
(3.) para j = 1..número_de_niños (J) agregue (Jj, L, h) a ABRIR
más
si J es un nodo MIN
(4.) agregar (padre (J), S, h) a ABRIR
eliminar de ABRIR todos los estados asociados con los hijos de los padres (J)
de lo contrario, si is_last_child (J) // si J es el último hijo del padre (J)
(5.) agregar (padre (J), S, h) a ABRIR
más
(6.) add (parent (J). (K + 1), L, h) to OPEN // agrega el estado asociado con el próximo hijo del padre (J) a OPEN
algoritmo Bron-Kerbosch es un algoritmo de enumeración para encontrar camarillas máximas en un gráfico no dirigido . Es decir, enumera todos los subconjuntos de vértices con las dos propiedades de que cada par de vértices en uno de los subconjuntos enumerados está conectado por un borde, y ningún subconjunto enumerado puede agregarle vértices adicionales al tiempo que conserva su conectividad completa . El algoritmo Bron-Kerbosch fue diseñado por los científicos holandeses Coenraad Bron y Joep Kerbosch , quienes publicaron su descripción en 1973. Aunque otros algoritmos para resolver el problema de la camarillatienen tiempos de ejecución que, en teoría, son mejores en las entradas que tienen pocos conjuntos independientes máximos, el algoritmo Bron-Kerbosch y las mejoras posteriores se informan con frecuencia como más eficientes en la práctica que las alternativas. [1] Es bien conocido y ampliamente utilizado en áreas de aplicación de algoritmos gráficos, como la química computacional . [2]
Un algoritmo contemporáneo de Akkoyunlu (1973) , aunque presentado en términos diferentes, puede verse como el mismo algoritmo Bron-Kerbosch, ya que genera el mismo árbol de búsqueda recursiva.
Sin pivotar [ editar ]
La forma básica del algoritmo Bron-Kerbosch es un algoritmo de retroceso recursivo que busca todas las camarillas máximas en un gráfico G dado . Más en general, dado tres conjuntos disjuntos de vértices R , P , y X , que encuentra la máxima camarillas que incluyen todos los vértices en R , algunos de los vértices en P , y ninguno de los vértices en X . En cada llamada a la algoritmo, P y X son conjuntos disjuntos cuya unión consiste en aquellos vértices que forman camarillas cuando se añade a R . En otras palabras, P ∪ Xes el conjunto de vértices que están unidas a cada elemento de R . Cuando P y X están vacíos, no hay más elementos que se puedan agregar a R , por lo que R es una camarilla máxima y el algoritmo genera R.
La recursividad se inicia configurando R y X como el conjunto vacío y P como el conjunto de vértices del gráfico. Dentro de cada llamada recursiva, el algoritmo considera los vértices en P a su vez; si no existen tales vértices, informa R como una camarilla máxima (si X está vacía) o retrocede. Para cada vértice v elegido de P , realiza una llamada recursiva en la que v se agrega a R y en la que P y X están restringidos al conjunto vecino N (v) de v, que busca e informa todas las extensiones de camarillas de R que contienen v . Entonces, se mueve v de P a X para excluirlo de consideración en las futuras camarillas y continúa con el siguiente vértice en P .
Es decir, en pseudocódigo, el algoritmo realiza los siguientes pasos:
BronKerbosch1 (R, P, X):
si P y X están ambos vacíos:
informar R como una camarilla máxima
para cada vértice v en P:
BronKerbosch1 (R ⋃ {v}, P ⋂ N (v), X ⋂ N (v))
P: = P \ {v}
X: = X ⋃ {v}
Con pivote [ editar ]
La forma básica del algoritmo, descrita anteriormente, es ineficiente en el caso de gráficos con muchas camarillas no máximas: hace una llamada recursiva para cada camarilla, máxima o no. Para ahorrar tiempo y permitir que el algoritmo retroceda más rápidamente en las ramas de la búsqueda que no contienen camarillas máximas, Bron y Kerbosch introdujeron una variante del algoritmo que involucra un "vértice pivote" u , elegido de P (o más generalmente, como investigadores posteriores). realizado, [4] de P ⋃ X ). Cualquier camarilla máxima debe incluir u u uno de sus no vecinos, ya que de lo contrario la camarilla podría aumentarse agregándole u . Por lo tanto, solo túy sus no vecinos necesitan ser probados como las opciones para el vértice v que se agrega a R en cada llamada recursiva al algoritmo. En pseudocódigo:
BronKerbosch2 (R, P, X):
si P y X están ambos vacíos:
informar R como una camarilla máxima
elija un vértice de pivote u en P ⋃ X
para cada vértice v en P \ N (u):
BronKerbosch2 (R ⋃ {v}, P ⋂ N (v), X ⋂ N (v))
P: = P \ {v}
X: = X ⋃ {v}
Si se elige el pivote para minimizar el número de llamadas recursivas realizadas por el algoritmo, el ahorro en tiempo de ejecución en comparación con la versión no pivotante del algoritmo puede ser significativo. [5]
Con ordenamiento de vértices [ editar ]
Un método alternativo para mejorar la forma básica del algoritmo Bron-Kerbosch implica renunciar al pivote en el nivel más externo de recursión y, en su lugar, elegir cuidadosamente el orden de las llamadas recursivas para minimizar el tamaño de los conjuntos P de vértices candidatos dentro de cada recursivo llamada.
La degeneración de un gráfico G es el número más pequeño d, de modo que cada subgrafo de G tiene un vértice con grado d o menos. Cada gráfico tiene un orden de degeneración , un orden de los vértices de tal manera que cada vértice tiene d o menos vecinos que vienen más tarde en el orden; Se puede encontrar un orden de degeneración en el tiempo lineal seleccionando repetidamente el vértice de grado mínimo entre los vértices restantes. Si el orden de los vértices v que recorre el algoritmo Bron-Kerbosch es un orden de degeneración, entonces el conjunto Pde los vértices candidatos en cada llamada (los vecinos de v que se encuentran más adelante en el pedido) se garantizarán que tengan tamaño como máximo d . El conjunto X de vértices excluidos constará de todos los vecinos anteriores de v , y puede ser mucho mayor que d . En las llamadas recursivas al algoritmo por debajo del nivel más alto de la recursión, la versión pivotante todavía se puede usar. [6] [7]
En pseudocódigo, el algoritmo realiza los siguientes pasos:
BronKerbosch3 (G):
P = V (G)
R = X = vacío
para cada vértice v en un orden de degeneración de G:
BronKerbosch2 ({v}, P ⋂ N (v), X ⋂ N (v))
P: = P \ {v}
X: = X ⋃ {v}
Se puede demostrar que esta variante del algoritmo es eficiente para gráficos de pequeña degeneración [6], y los experimentos muestran que también funciona bien en la práctica para grandes redes sociales dispersas y otros gráficos del mundo real. [7]
Un gráfico con cinco camarillas máximas: cuatro aristas y un triángulo
En el gráfico de ejemplo que se muestra, el algoritmo se llama inicialmente con R = Ø, P = {1,2,3,4,5,6} y X = Ø. El pivote u debe elegirse como uno de los vértices de grado tres, para minimizar el número de llamadas recursivas; por ejemplo, suponga que u se elige como vértice 2. Luego hay tres vértices restantes en P \ N ( u ): vértices 2, 4 y 6.
La iteración del bucle interno del algoritmo para v = 2 hace una llamada recursiva al algoritmo con R = {2}, P = {1,3,5} y X = Ø. Dentro de esta llamada recursiva, se elegirá una de 1 o 5 como pivote, y habrá dos llamadas recursivas de segundo nivel, una para el vértice 3 y la otra para el vértice que no se eligió como pivote. Estas dos llamadas eventualmente informarán las dos camarillas {1,2,5} y {2,3}. Después de volver de estas llamadas recursivas, vértice 2 se añade a X y se retira de P .
La iteración del bucle interno del algoritmo para v = 4 hace una llamada recursiva al algoritmo con R = {4}, P = {3,5,6} y X = Ø (aunque el vértice 2 pertenece al conjunto X en la llamada externa al algoritmo, no es un vecino de v y está excluido del subconjunto de X pasado a la llamada recursiva). Esta llamada recursiva terminará haciendo tres llamadas recursivas de segundo nivel al algoritmo que informa las tres camarillas {3,4}, {4,5} y {4,6}. Entonces, el vértice 4 se añade a X y se retira de P .
En la tercera y última iteración del bucle interno del algoritmo, para v = 6, hay una llamada recursiva al algoritmo con R = {6}, P = Ø y X = {4}. Debido a que esta llamada recursiva tiene P vacía y X no vacía, inmediatamente retrocede sin informar más camarillas, ya que no puede haber una camarilla máxima que incluya el vértice 6 y excluya el vértice 4.
El árbol de llamadas para el algoritmo, por lo tanto, se ve así:
BronKerbosch2 (Ø, {1,2,3,4,5,6}, Ø)
BronKerbosch2 ({2}, {1,3,5}, Ø)
BronKerbosch2 ({2,3}, Ø, Ø): salida {2, 3}
BronKerbosch2 ({2,5}, {1}, Ø)
BronKerbosch2 ({1,2,5}, Ø, Ø): salida {1,2,5}
BronKerbosch2 ({4}, {3,5,6}, Ø)
BronKerbosch2 ({3,4}, Ø, Ø): salida {3,4}
BronKerbosch2 ({4,5}, Ø, Ø): salida {4,5}
BronKerbosch2 ({4,6}, Ø, Ø): salida {4,6}
BronKerbosch2 ({6}, Ø, {4}): sin salida
El gráfico en el ejemplo tiene degeneración dos; un posible pedido de degeneración es 6,4,3,1,2,5. Si la versión de ordenamiento de vértices del algoritmo Bron-Kerbosch se aplica a los vértices, en este orden, el árbol de llamadas se ve como
BronKerbosch3 (G)
BronKerbosch2 ({6}, {4}, Ø)
BronKerbosch2 ({6,4}, Ø, Ø): salida {6,4}
BronKerbosch2 ({4}, {3,5}, {6})
BronKerbosch2 ({4,3}, Ø, Ø): salida {4,3}
BronKerbosch2 ({4,5}, Ø, Ø): salida {4,5}
BronKerbosch2 ({3}, {2}, {4})
BronKerbosch2 ({3,2}, Ø, Ø): salida {3,2}
BronKerbosch2 ({1}, {2,5}, Ø)
BronKerbosch2 ({1,2}, {5}, Ø)
BronKerbosch2 ({1,2,5}, Ø, Ø): salida {1,2,5}
BronKerbosch2 ({2}, {5}, {1,3}): sin salida
BronKerbosch2 ({5}, Ø, {1,2,4}): sin salida
Análisis del peor caso [ editar ]
El algoritmo Bron-Kerbosch no es un algoritmo sensible a la salida : a diferencia de otros algoritmos para el problema de la camarilla, no se ejecuta en tiempo polinómico por cada camarilla máxima generada. Sin embargo, es eficiente en el peor de los casos: como resultado de Moon & Moser (1965) , cualquier gráfico n- vértice tiene como máximo 3 n / 3 camarillas máximas y el peor tiempo de ejecución del Bron-Kerbosch El algoritmo (con una estrategia de pivote que minimiza el número de llamadas recursivas realizadas en cada paso) es O (3 n / 3 ), que coincide con este límite. [8]
Para gráficos dispersos , son posibles límites más estrechos. En particular, la versión de ordenamiento de vértices del algoritmo Bron-Kerbosch puede ejecutarse en el tiempo O ( dn 3 d / 3 ) , donde d es la degeneración del gráfico, una medida de su escasez. Existen gráficos degenerados d para los cuales el número total de camarillas máximas es ( n - d ) 3 d / 3 , por lo que este límite es cercano a apretado.
No hay comentarios:
Publicar un comentario