Este artículo proviene de un motor de traducción automática.

Ejecución de prueba

Algoritmos tabú y el clique máximo

James McCaffrey

Descargar el ejemplo de código

En la columna de este mes, te presento una solución avanzada para el problema de la clique máxima de gráfico. La solución utiliza lo que ha llamado un algoritmo de tabú, y analizaré cómo diseñar y probar estos algoritmos. La idea de que el problema de la clique máxima es encontrar el mayor grupo de nodos en un gráfico que todos están conectados entre sí. Mire el gráfico simple en la figura 1. El gráfico tiene nueve nodos y 13 aristas. El gráfico es no ponderado (no hay ningún prioridades asociadas con los bordes) y grafo (todas las aristas son bidireccionales). Nodos de 2, 4 y 5 forman a una clique de tamaño tres. La camarilla máxima es que el conjunto de nodos 0, 1, 3 y 4, que forma a una camarilla de tamaño cuatro.

 

 

Figura 1 gráfico para un algoritmo de tabú máximo Clique

El problema de la clique máxima es interesante por varias razones. Aunque no es evidente desde el gráfico simple en figura 1, el problema de la clique máxima es uno de los más desafiantes en Ciencias de la computación. Surge en muchos importantes problemas prácticos, tales como análisis de comunicación de red social, donde los nodos representan personas y bordes mensajes o relaciones. Y el problema utiliza técnicas como algoritmos codiciosos y algoritmos de tabú, que son importantes avanzadas técnicas de programación. Tener una solución para el problema de la clique máxima en su biblioteca personal puede ser una herramienta práctica, y entender el algoritmo utilizado puede añadir nuevas técnicas a su conjunto de habilidades.

Se trata de la tercera columna en una serie que utiliza el problema de la clique máxima para ilustrar la codificación avanzada y las pruebas técnicas, pero esta columna puede leerse sin referencia directa a los dos anteriores. En mi columna de octubre, "Gráfico de estructuras y máximo Clique" (msdn.microsoft.com/magazine/hh456397), describía cómo codificar una estructura de datos eficiente para mantener una estructura de datos del gráfico en su memoria. En mi columna de noviembre, "Algoritmos codiciosos y Clique máxima" (msdn.microsoft.com/magazine/hh547104), se describe cómo puede utilizarse un algoritmo relativamente simple para encontrar una solución para el problema de la clique máxima difícil.

En términos informales, un algoritmo voraz es un algoritmo que comienza con una solución simple, incompleta a un problema difícil y luego iterativamente busca la mejor manera de mejorar la solución. El proceso se repite hasta que se llegue a alguna condición de parada. ¿Cómo­nunca, algoritmos codiciosos suelen tengan una debilidad: repetidamente a generar la misma solución una y otra vez. Tabú algoritmos están diseñados para hacer frente a esta debilidad. El tabú de la palabra, a veces escrito tabú, medios prohibidos. En términos simples, algoritmos de tabú mantienen una lista de datos incorrectos. La parte de procesamiento del algoritmo no está permitida utilizar tabú datos hasta algunos prohibición el tiempo transcurrido. Formas simples de uso de algoritmos de tabú un fijo prohibición a tiempo. Algoritmos avanzados tabú adaptan el tiempo de prohibir dinámicamente mientras se ejecuta el algoritmo.

Figura 2 ilustra las ideas importantes de un algoritmo de tabú que aplica para el problema de la clique máxima y muestra hacia dónde yo estoy en esta columna.

Figura 2 máximo tabú Clique Demo Run

Tengo una aplicación de consola que comienza por cargar en memoria el gráfico correspondiente a la que se muestra en figura 1. El archivo utiliza un formato de archivo gráfico estándar llamado DIMACS. Diseño y una estructura de datos del gráfico eficiente de codificación son un problema significativo en sí mismo. El código de estructura de datos de gráfico he explicado en mi columna de octubre.

El algoritmo comienza seleccionando un nodo único al azar y al inicializar a una camarilla con ese nodo. El algoritmo de forma iterativa intenta buscar y agregar el nodo mejor que aumentará el tamaño de la camarilla. Lo explicaremos de qué nodo mejor significa más tarde. Si el algoritmo no puede encontrar un nodo para agregar, intenta encontrar el nodo mejor para eliminar de la camarilla. Detrás de las escenas, el algoritmo recuerda la última vez que cada nodo se ha movido en la actual camarilla de solución o se mudó de la camarilla. El algoritmo utiliza esta información para prohibir agregar o colocar recientemente utilizados nodos de una cierta cantidad de tiempo. Esta es la parte tabú del algoritmo.

El algoritmo propio reinicia cada cierto tiempo cuando no se avanzó en la búsqueda de una mejor camarilla (mayor). El algoritmo silenciosamente almacena las soluciones (camarillas) se ha visto anteriormente. El algoritmo utiliza esa información de historia de la solución para adaptarse dinámicamente el tiempo de prohibir. Si el algoritmo sigue encontrando las mismas soluciones, aumenta el tiempo de prohibir para desalentar nodos utilizados recientemente se utilicen. Si el algoritmo no ve las mismas soluciones, disminuye el tiempo de prohibir, por lo que hay un grupo mayor de nodos a elegir. Esta es la parte adaptativa del algoritmo tabú.

En la mayoría de las situaciones donde se usa un algoritmo voraz, la solución óptima se desconoce, por lo que deben especificar una o más condiciones de detención. Cuando el algoritmo alcanza una condición de parada, se muestra la mejor solución encontrada.

En las secciones siguientes, le guiará a través del código que se produjo la captura de pantalla en figura 2. El código fuente completo está disponible en code.msdn.microsoft.com/mag201112TestRun. Esta columna se supone que tienes habilidades de programación de nivel intermedio con un idioma de la serie c o Visual Basic.NET lenguaje. Utilizar C#, pero he escrito el código para que serás capaz de refactor a otro idioma como F # o Python sin demasiada dificultad si desea.

Estructura general del programa

La estructura general del programa se muestra en la figura 2 se presenta en figura 3. Decidí colocar todo el código en una aplicación de consola mediante métodos estáticos para mayor simplicidad, pero tal vez desee modularize partes del código en las bibliotecas de clases y utilizar un enfoque orientado a objetos. El programa es menos complicado de lo que podría sospechar en mirar figura 3 porque la mayoría de los métodos son métodos auxiliares corto.

Estructura del programa general figura 3

using System;
using System.Collections.Generic; // List<int>
using System.Text; // StringBuilder
using System.IO; // FileStream
using System.Collections; // Hashtable
namespace TabuMaxClique
{
  class TabuMaxCliqueProgram
  {
    static Random random = null;
    static void Main(string[] args) { ...
}
    static List<int> FindMaxClique(MyGraph graph, int maxTime,
      int targetCliqueSize) { ...  }
    static List<int> MakePossibleAdd(MyGraph graph,
      List<int> clique) { ...
}
    static bool FormsALargerClique(MyGraph graph,
      List<int> clique, int node) { ...
}
    static int GetNodeToAdd(MyGraph graph,
      List<int> allowedAdd, List<int> possibleAdd) { ...
}
    static int GetNodeToDrop(MyGraph graph, List<int> clique,
      List<int> oneMissing) { ...
}
    static List<int> MakeOneMissing(MyGraph graph,
      List<int> clique) { ...
}
    static List<int> SelectAllowedNodes(List<int> listOfNodes,
      int time, int prohibitPeriod, int[] lastMoved) { ...
}
    static int UpdateProhibitPeriod(MyGraph graph, List<int> clique,
      int bestSize, Hashtable history, int time, int prohibitPeriod,
      ref int timeProhibitChanged) { ...
}
    static string ListAsString(List<int> list) { ...
}
    private class CliqueInfo
    {
      // ...
}
  }
  public class MyGraph
  {
    // ...
private class BitMatrix
    {
      // ...
}
  }
} // ns

El programa tiene dos clases de alto nivel, y cada una de esas clases tiene una subclase de auxiliar. Clase TabuMaxCliqueProgram contiene el método Main y toda la lógica de algoritmo, junto con la subclase CliqueInfo, que se utiliza para mantener un historial de soluciones previamente camarilla. MyGraph clase encapsula una representación gráfica eficiente y contiene la subclase BitMatrix, que se utiliza para almacenar información de adyacencia de nodo en forma condensada. Un objeto de aleatoria de ámbito de clase denominado aleatorio se utiliza para inicializar la camarilla a un nodo aleatorio y romper lazos cuando hay varios nodos mejores para agregar o quitar.

Con algunas declaraciones de WriteLine y try-catch código eliminado, el método Main es:

Console.WriteLine("\nBegin tabu algorithm maximum clique demo\n");
string graphFile = "..
\\..
\\DimacsGraph.clq";
MyGraph graph = new MyGraph(graphFile, "DIMACS");
int maxTime = 50;
int targetCliqueSize = graph.NumberNodes;
List<int> maxClique = FindMaxClique(graph, maxTime, targetCliqueSize);
Console.WriteLine("\nSize of best clique found = " + maxClique.Count);
Console.WriteLine(ListAsString(maxClique));

El gráfico se representa como un objeto definido por el programa de MyGraph. El gráfico se carga desde un archivo de texto externo que utiliza el formato de archivo DIMACS. El método clave de MyGraph es AreAdjacent, que devuelve true si dos nodos están conectados. Configurar maxTime para 50 repeticiones para establecer una condición de parada absoluta para el algoritmo voraz. Se trata de una pequeña artificialmente. En un problema de la clique real máximo, el tiempo máximo es típicamente en el rango de 1.000 a 100.000. Configurar tamaño de targetClique para establecer una segunda condición parada; Si no encuentra una camarilla que tiene el mismo número de nodos que hay en el gráfico, la camarilla máxima debe han sido encontrada. La mayoría del trabajo se realiza mediante el método FindMaxClique, que utiliza un algoritmo de tabú codiciosos, adaptable para buscar la camarilla más grande posible. El método auxiliar ListAsString simplemente crea una representación de cadena de una lista de <int> objeto.

El método FindMaxClique

El método FindMaxClique llama varios métodos auxiliares, que describiré en breve. En pseudocódigo de alto nivel, se da el algoritmo de FindMaxClique en figura 4. El pseudocódigo deja fuera varios detalles importantes para mayor claridad, pero presenta los puntos principales del algoritmo.

Figura 4 algoritmo adaptativo de tabú máximo Clique

initialize clique with a single node
get list of candidate nodes to add
loop until stop condition met
  if there are nodes which can be added
    get list of allowed nodes
    if there are allowed nodes to add
      find best node to add and add to clique
      mark added node as recently used
      record current clique
 else
   get list of allowed nodes to drop
   if there are allowed nodes which can be dropped
     find best node to drop and drop from clique
     mark dropped node as recently used
     record current clique
 else
   select a random node to drop and drop from clique
   mark dropped node as recently used
   record current clique
 if lack of progress
   restart algorithm
  update list of candidate nodes
  update prohibit time
end loop
return largest clique found
The FindMaxClique method definition begins:
static List<int> FindMaxClique(MyGraph graph, int maxTime,
  int targetCliqueSize)
{
  List<int> clique = new List<int>();
  random = new Random(1);
  int time = 0;
  int timeBestClique = 0;
  int timeRestart = 0;
  int nodeToAdd = -1;
  int nodeToDrop = -1;
...

El objeto de la camarilla local es la actual camarilla de solución. Se crea una instancia del objeto aleatorio con un valor arbitrario de semilla de 1. La variable de tiempo es el contador de bucle de procesamiento principal del algoritmo. Las variables timeBestClique y timeRestart se utilizan para determinar si ha habido una falta de progreso por lo que el algoritmo puede reiniciar a sí mismo. Siguiente:

int prohibitPeriod = 1;
int timeProhibitChanged = 0;
int[] lastMoved = new int[graph.NumberNodes];
for (int i = 0; i < lastMoved.Length; ++i) {
  lastMoved[i] = int.MinValue;
}
Hashtable history = new Hashtable();
...

El período de prohibir se inicializa en 1. Esto significa que, inicialmente, al menos — después de que un nodo ha sido utilizado por el algoritmo, no se puede utilizar para una iteración de tiempo. Si hubiera utilizado un valor de 0, el efecto hubiera sido que no prohibir en todo momento. La mayoría de los algoritmos tabú utilizan un valor fijo para el tiempo de prohibir, pero el problema con este enfoque es que la investigación ha demostrado que el mejor valor para un tiempo fijo de prohibir varía de un problema a problema. El enfoque adaptativo presento el tiempo de prohibir las actualizaciones mientras se ejecuta el algoritmo, basado en la historia de las soluciones anteriores. Pido este tabú adaptación técnica, pero algunos trabajos de investigación llaman la técnica reactiva o dinámico.

La matriz de lastMoved se utiliza para determinar si un nodo está permitido o prohibido en cualquier momento dado. El índice de la matriz representa un nodo, y el valor correspondiente de la matriz es la vez que última fue trasladado el nodo (agregado o caído). Utilizando la matriz de lastMoved, elimina la necesidad de crear explícitamente una lista de nodos permitidos (o, equivalente, prohibido nodos). Inicializar el todas las celdas de lastMoved a int.MinValue para posteriormente puedo determinar si un nodo nunca ha sido usada.

El objeto Hashtable historia posee una colección de camarillas solución previamente. Cada elemento de la tabla hash es un objeto CliqueInfo, que te describen en detalle más adelante. Pude ha utilizado un objeto genérico de diccionario en lugar del objeto Hashtable no genéricas. FindMaxClique continúa:

int randomNode = random.Next(0, graph.NumberNodes);
clique.Add(randomNode);
List<int> bestClique = new List<int>();
bestClique.AddRange(clique);
int bestSize = bestClique.Count;
timeBestClique = time;
...

Inicializar a la actual camarilla de solución un nodo aleatorio desde el gráfico. Cree una instancia de una lista de bestClique para realizar un seguimiento de la mejor solución de camarilla (mayor) encontrada por el algoritmo. Viene a continuación:

List<int> possibleAdd = MakePossibleAdd(graph, clique);
List<int> oneMissing = MakeOneMissing(graph, clique);
...

El método MakePossibleAdd crea una lista de todos los nodos que pueden agregarse a la camarilla actual para aumentar el tamaño de la camarilla por 1. En otras palabras, el método crea una lista de nodos que no están en la camarilla pero están conectadas a cada nodo de la camarilla. Esta lista de possibleAdd podría tener un conteo de 0 o podría contener nodos prohibidos. Método auxiliar MakePossibleAdd llamadas FormsALargerClique.

El método MakeOneMissing crea una lista de todos los nodos que están conectados a todos pero exactamente uno de los nodos en la camarilla actual. No es obvio, pero resulta que mantener esa lista crea una forma inteligente para determinar qué nodo en la actual camarilla será el mejor a soltar, como explicaré más tarde. Comienza el bucle principal de procesamiento:

while (time < maxTime && bestSize < targetCliqueSize)
{
  ++time;
  bool cliqueChanged = false;
...

El bucle principal proceso terminará cuando se alcanza el número máximo de iteraciones o si se encuentra una solución mejor con el tamaño de la camarilla de destino. Utilizar la variable cliqueChanged para controlar la lógica de ramificaciones entre agregar y quitar nodos, como lo verá. La lógica para agregar un nodo permitido se muestra en la figura 5.

Figura 5 la lógica para agregar un nodo permitido

if (possibleAdd.Count > 0) {
  List<int> allowedAdd = SelectAllowedNodes(possibleAdd, time,
    prohibitPeriod, lastMoved);
  if (allowedAdd.Count > 0) {
    nodeToAdd = GetNodeToAdd(graph, allowedAdd, possibleAdd);
    clique.Add(nodeToAdd);
    lastMoved[nodeToAdd] = time;
    clique.Sort();  cliqueChanged = true;
    if (clique.Count > bestSize) {
      bestSize = clique.Count;
      bestClique.Clear();
      bestClique.AddRange(clique);
      timeBestClique = time;
    }
  }
}

El algoritmo comprueba si hay nodos que aumentarán el tamaño de la camarilla actual. Si así, método SelectAllowedNodes crea una lista de nodos que están permitidos, es decir, no tabú — de la lista de nodos que se pueden agregar.

La línea clave SelectAllowedNodes es:

if (time > lastMoved[currNode] + prohibitPeriod)
  result.Add(currNode); // Allowed

El currNode es uno de los nodos en la lista de possibleAdd. La lógica se comprueba para ver si suficiente tiempo transcurrido desde el nodo último fue utilizado para que el nodo es pasado el período de prohibir. Si es así, el nodo se agrega a la lista de nodos de allowedAdd.

Ahora, si hay cualquiera de los nodos que está permitida y aumentará el tamaño de la camarilla, método GetNodeToAdd determina el mejor nodo para agregar a la camarilla. El mejor nodo es el nodo de la lista de allowedAdd que es la mayoría conectados al nodo de la lista de possibleAdd. La idea es que desea agregar un nodo que le dará las mayoría posibilidades de encontrar un nodo para agregar en la siguiente iteración del algoritmo. Podría haber varios nodos en la lista de allowedAdd que están vinculados como más conectados a los nodos de possibleAdd. Si es así, uno de los nodos vinculados seleccionado al azar. Después de agregar el nodo mejor, la solución de camarilla actual está ordenada por razones que explicaré más adelante. El código para colocar un nodo es:

if (cliqueChanged == false) {
  if (clique.Count > 0) {
    List<int> allowedInClique = SelectAllowedNodes(clique, time,
      prohibitPeriod, lastMoved);
    if (allowedInClique.Count > 0) {
      nodeToDrop = GetNodeToDrop(graph, clique, oneMissing);
      clique.Remove(nodeToDrop);
      lastMoved[nodeToDrop] = time;
      clique.Sort();  cliqueChanged = true;
    }
  }
}
...

Si el algoritmo no puede agregar un nodo, intenta colocar un nodo permitido en la esperanza de que retroceso dará una solución que permitirá un nuevo nodo que se añadan en la siguiente iteración. La lista de nodos en la camarilla actual es filtrada por el método SelectAllowedNodes para obtener los nodos que no son tabú. El GetNodeToDrop recoge lo mejor de estos nodos para colocar en la lista de nodos de oneMissing.

La idea es colocar el nodo permitido en la camarilla actual, lo que redundará en el aumento más grande en la lista de nodos de possibleAdd. Una manera de hacer esto es probar cada nodo en la lista permitida por quitarlo realmente la camarilla actual y luego calcular el tamaño de la lista resultante de la possibleAdd. Pero hay un enfoque mucho más eficiente que utiliza una lista de nodos que están conectados a todos pero exactamente uno de los nodos en la camarilla actual. Mediante la lista de oneMissing de nodos, la lista puede utilizarse como sigue. Escanear a través de cada nodo en los nodos de la camarilla permitidos y contar cuántos nodos en la lista de oneMissing es notconnected para el nodo de camarilla. El nodo de la lista de permitidos de camarilla que es menos conectados a los nodos en el oneMissing la lista es el nodo mejor a soltar. Después de perder este nodo conectado por lo menos, todos los nodos en la lista de oneMissing que no estaba conectado al nodo perdido estarán ahora completamente conectados a los nodos restantes de la camarilla y por lo tanto se convierten en nuevos nodos de possibleAdd.

En este momento en la lógica, podría no han sido posible agregar un nodo permitido o colocar un nodo permitido. Para despegar a sí mismo, el algoritmo cae un nodo aleatorio de la camarilla actual:

if (cliqueChanged == false) {
  if (clique.Count > 0) {
    nodeToDrop = clique[random.Next(0, clique.Count)];
    clique.Remove(nodeToDrop);
    lastMoved[nodeToDrop] = time;
    clique.Sort();
    cliqueChanged = true;
  }
}
...

A continuación, el algoritmo comprueba si ha habido una falta de progreso y, en caso afirmativo, se reinicia propia:

int restart = 100 * bestSize;
if (time - timeBestClique > restart && time - timeRestart > restart) {
  timeRestart = time;
  prohibitPeriod = 1;
  timeProhibitChanged = time;
  history.Clear();
...

La variable de reinicio es el número de iteraciones para permitir que exista ninguna mejora o desde el último reinicio. Aquí utilizo un valor de 100 veces el tamaño de la mejor solución actual. El valor que se utilizará para el intervalo de reinicio no es bien entendido y puede que desee probar alternativas. (Usé un valor ficticio de 2 para producir más reinicios para la captura de pantalla en figura 2). El valor de que uso ha trabajado bien para mí en la práctica, sin embargo. Si hay un reinicio, el algoritmo restablece el tiempo de prohibir y borra la tabla de hash de historia sosteniendo a camarillas de solución que se han visto. Tenga en cuenta que el algoritmo aún no ha actualizado la tabla de hash de la historia. El código de reinicio no, sin embargo, restablece la matriz lastVisited, que almacena información acerca de cuando nodos fueron última agregados o quitados de la camarilla de solución. Viene a continuación:

int seedNode = -1;
List<int> temp = new List<int>();
for (int i = 0; i < lastMoved.Length; ++i) {
  if (lastMoved[i] == int.MinValue) temp.Add(i);
}
if (temp.Count > 0)
  seedNode = temp[random.Next(0, temp.Count)];
else
  seedNode = random.Next(0, graph.NumberNodes);
...

El algoritmo intenta repropagar a la camarilla de solución con un nodo que no se ha utilizado nunca antes. Si hay varios nodos no utilizados, se selecciona al azar. Si no hay ningún nodo no utilizado, se selecciona un nodo al azar. En lugar de utilizar un nodo aleatorio, una alternativa inexplorada es seleccionar el nodo que pasó menos recientemente. El código de reinicio termina con lo siguiente:

...
clique.Clear();
  clique.Add(seedNode);
}

El bucle de procesamiento principal y FindMaxClique ceñido hasta así:

...
possibleAdd = MakePossibleAdd(graph, clique);
    oneMissing = MakeOneMissing(graph, clique);
    prohibitPeriod = UpdateProhibitPeriod(graph, clique, bestSize,
      history, time, prohibitPeriod, ref timeProhibitChanged);
  } // Main processing loop
  return bestClique;
}

Se regeneran las listas possibleAdd y oneMissing. Es una alternativa mantener estructuras de datos auxiliares y actualizar estas dos listas en lugar de les recreación desde cero. El método UpdateProhibitPeriod es el componente clave de la parte adaptativa del algoritmo tabú y describiré próximamente.

Recordando las soluciones anteriores

Método UpdateProhibitPeriod utiliza una tabla de hash de soluciones previamente para aumentar o disminuir el tiempo de prohibir dinámicamente. Recordemos que una solución es una camarilla que es una lista de <int> de los nodos que están conectados entre sí. Pero también deba almacenar el tiempo cuando fue visto por última vez una solución. Por lo tanto, encapsulan una solución de camarilla y la última vez fue visto en una clase de CliqueInfo como se muestra en figura 6.

Figura 6 la clase CliqueInfo

private class CliqueInfo
{
  private List<int> clique;
  private int lastSeen;
  public CliqueInfo(List<int> clique, int lastSeen)
  {
    this.clique = new List<int>();
    this.clique.AddRange(clique);
    this.lastSeen = lastSeen;
  }
  public int LastSeen
  {
    get { return this.lastSeen; }
    set { this.lastSeen = value; }
  }
  public override int GetHashCode()
  {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < clique.Count; ++i) {
      sb.Append(clique[i]);
      sb.Append(" ");
    }
    string s = sb.ToString();
    return s.GetHashCode();
  }
  public override string ToString()
  {
    string s = "";
    for (int i = 0; i < clique.Count; ++i)
      s += clique[i] + " ";
      return s;
  }
}

Porque un elemento CliqueInfo se agregará al objeto Hashtable solution historia, necesito una función de hash GetHashCode personalizada. Escribir funciones hash personalizado es sorprendentemente complicado, y una discusión detallada de todas las cuestiones involucradas requeriría una columna completa. En esta situación, utilizar la más simple, pero no la más eficiente — enfoque. Crear una representación de cadena de los nodos en el campo de la camarilla, separado por espacios y, a continuación, utilizar el String.GetHashCode incorporado. Por ejemplo, si una camarilla contiene nodos {3 5 8}, generar "3 5 8" (con un espacio final) y, a continuación, generar un código hash de esa cadena. Recordar que camarillas se mantienen siempre en un orden, por lo que no sería posible tener una camarilla {3 5 8} y otra camarilla {8 3 5}. Colocar espacios entre los nodos de manera que clique {3 5 8} se distingue de la camarilla {3 58}.

Actualizando el prohibir el período

Método UpdateProhibitPeriod adaptativa aumenta o disminuye el tiempo de prohibir basado en soluciones de camarilla previamente. El método comienza:

static int UpdateProhibitPeriod(MyGraph graph, List<int> clique,
  int bestSize, Hashtable history, int time, int prohibitPeriod,
  ref int timeProhibitChanged)
{
  int result = prohibitPeriod;
  CliqueInfo cliqueInfo = new CliqueInfo(clique, time);
.
.
.

El método devolverá una vez prohibir que posiblemente podría ser el mismo que el actual momento de prohibir. Se crean instancias de un objeto CliqueInfo sosteniendo la camarilla actual y la hora actual, como se muestra aquí:

if (history.Contains(cliqueInfo.GetHashCode())) {
  CliqueInfo ci = (CliqueInfo)history[cliqueInfo.GetHashCode
  int intervalSinceLastVisit = time - ci.LastSeen;
  ci.LastSeen = time;
  if (intervalSinceLastVisit < 2 * graph.NumberNodes - 1) {
    timeProhibitChanged = time;
    if (prohibitPeriod + 1 < 2 * bestSize) return prohibitPeriod + 1;
    else return 2 * bestSize;
  }
}
else history.Add(cliqueInfo.GetHashCode(), cliqueInfo);
...

¿El código comprueba si la solución actual de camarilla, en forma de un objeto CliqueInfo, se ha visto antes, es decir, la camarilla de la tabla de hash de la historia? Si la camarilla actual se ha visto antes, el algoritmo calcula cuánto tiempo ha pasado desde la camarilla fue vista. Si este intervalo es suficientemente corto, se incrementa el tiempo de prohibir (sujeto a un límite superior). La idea es que porque no ha sido muy largo ya que la camarilla actual fue vista, el algoritmo es generar soluciones duplicadas. Si se aumenta el tiempo de prohibir, habrá más nodos de tabú y por lo tanto menos permitieron nodos, reduciendo las posibilidades de generar soluciones de camarilla duplicados. Si la actual solución camarilla no ha visto antes, se añade a la tabla de hash de la historia.

El intervalo "corta suficiente" es dos veces el número de nodos en el gráfico, menos uno. Esto se utiliza para determinar cuándo se debe incrementar el tiempo de prohibir. El mejor valor a utilizar aquí es otra pregunta abierta en la investigación de la camarilla máximo. El "límite superior" a la hora de prohibir es dos veces el tamaño de la solución actual más conocido. El mejor valor límite superior es, como se puede adivinar probablemente por ahora, otra pregunta de investigación abierta.

En este punto, ya sea la camarilla actual no ha sido vista antes, o la camarilla se ha visto antes pero el intervalo necesario para incrementar el tiempo de prohibir no era lo suficientemente pequeño. Por lo tanto el algoritmo ahora comprueba si se puede disminuye, el período de prohibir que se reduzca el número de nodos de tabú y aumentar el número de nodos permitidos, que a su vez da el algoritmo más nodos para añadir o quitar:

...
if (time - timeProhibitChanged > 10 * bestSize) {
    timeProhibitChanged = time;
    if (prohibitPeriod - 1 > 1)
      return prohibitPeriod - 1;
    else
      return 1;
  }
  else {
    return result; // no change
  }
} // UpdateProhibitTime

En lugar de comprobar explícitamente para ver si ha sido "relativamente" tiempo ya se veía la camarilla actual, el algoritmo indirectamente comprueba cuánto tiempo ha pasado desde la camarilla actual fue vista examinando el tiempo cuando el período de prohibir se cambió por última vez. Una vez más, no está claro el mejor valor para "relativamente largo". Utilizo un valor 10 veces el tamaño de la mejor solución actual. Observe que el tiempo de prohibir no puede caer por debajo de 1.

Más investigación

Resultados de la investigación sobre el problema de la clique máxima sugieren que un enfoque codicioso con una función adaptativa tabú da los mejores resultados globales al rendimiento y calidad de la solución se toman en cuenta. DIMACS es una organización de investigación que creó un conjunto de problemas de referencia gráfica difícil camarilla. Corrí el código presentado aquí contra un problema particularmente difícil de DIMACS (C2000.9) y el código rápidamente (en menos de dos segundos) encontraron una camarilla con tamaño 76 que es en 1.5 por ciento del tamaño de la solución más conocido de los 77.

En varios puntos en esta columna, he mencionado resultados de la investigación sobre el problema de la clique máxima. Si estás interesado en esta investigación, les recomiendo que busque la Web académicos artículos escritos por el texto siguiente: r. Battiti et al., w el. Pullan et al. y k. Katayama et al. Varios artículos por estos tres autores y sus colegas fueron mis referencias principales.

Un área prometedora inexplorado para el algoritmo de camarilla máxima presentado aquí es incorporar algún tipo de lo que se denomina búsqueda de meseta. Recordemos que el algoritmo de máxima camarilla primero intenta agregar un nodo no tabú a la solución actual de camarilla. Entonces, si no es posible, el algoritmo cae un nodo de la solución actual de camarilla. La idea de búsqueda de meseta es encontrar un nodo en la solución actual de camarilla que puede intercambiarse con un nodo no en la camarilla. Aunque esto no aumenta el tamaño de la actual camarilla, no reducir el tamaño de la camarilla, tampoco.

Dr.James McCaffrey trabaja para Volt Information Sciences Inc., donde administra formación técnica para ingenieros de software trabajando en el Microsoft Redmond, Washington, campus. Trabajó en varios productos de Microsoft, Internet Explorer y MSN Search. Dr. McCaffrey es el autor de ".Recetas de automatización de prueba NET"(Apress, 2006) y puede ser contactado en jammc@microsoft.com.

Gracias a los siguientes expertos técnicos para revisar este artículo: Paul Koch, Dan Liebling, Ann Loomis Thompson y Shane Williams