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

Ejecución de pruebas

Algoritmos codiciosos y el clique máximo

James McCaffrey

Descargar el ejemplo de código

En la columna de este mes, presentaré una solución al problema gráfico clique máxima. La solución utiliza lo que denomina un algoritmo voraz, y se explica 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 están conectados entre sí. Eche un vistazo el gráfico simple en figura 1. El gráfico tiene nueve nodos y 13 bordes. El gráfico es ponderado (no hay ningún prioridades asociadas con los bordes) y grafo (todos los bordes son bidireccionales). Los nodos 2, 4 y 5 forman a un grupo de tres de tamaño. La clique máxima es que 0, 1, 3 y 4, que forman a un grupo de cuatro de tamaño de conjunto de nodos.

 

Figura 1 gráfico para un algoritmo voraz Clique máximo

El problema de la clique máxima es interesante por varias razones. Aunque no es evidente en el gráfico simple en figura 1, el problema de la clique máxima es uno de los más intrincados en informática. Éste se produce en muchas aplicaciones importantes, como el análisis de comunicación de red social, donde los nodos representan personas y aristas de un mensaje o una relación. Y el máximo clique problema presta bien a la solución por un algoritmo voraz, que es una técnica fundamental en informática.

En términos informales, un algoritmo voraz es un algoritmo que se inicia con una solución simple y incompleta a un problema difícil y, a continuación, busca iterativamente la mejor manera de mejorar la solución. El proceso se repite hasta que se alcance una condición de detención. Figura 2 ilustra las ideas importantes del problema clique máxima y se muestra mi objetivo en este artículo.

Figura 2 ejecución avaricioso máximo Clique Demo

Tengo una aplicación de consola, que comienza por la carga en la memoria en el gráfico que corresponde a la que se muestra en figura 1. Diseñar y codificar una estructura de datos de gráfico eficaz son un problema importante en sí mismo. El código de estructura de datos de gráfico le expliqué en mi última columna (msdn.microsoft.com/magazine/hh456397). El algoritmo primero selecciona un solo nodo al azar, en este nodo case 2 e inicializa a un grupo con ese nodo. A continuación, el algoritmo busca el mejor nodo agregar a la camarilla. Si hace referencia a figura 1, verá que hay sólo dos nodos, 4 y 5, que forman un grupo más grande. Explicaré lo que significa el mejor nodo en breve.

El algoritmo selecciona y se agrega el nodo 4 para el grupo por lo que el grupo es ahora {2, 4}. En este momento, es sólo un nodo en el gráfico, 5, que aumentará el tamaño de la camarilla, por lo que el algoritmo selecciona nodo 5 y lo agrega a la camarilla. Ahora no hay disponible ningún nodo que aumentará el tamaño de la camarilla. El algoritmo cae el mejor nodo desde el grupo con la esperanza de que se puede agregar un nuevo nodo diferente que le permitirán el progreso. Una vez más, se explica lo que significa "mejor" en breve. El algoritmo quita nodo 4 de la camarilla. Como puede ver observando el gráfico, no hay ninguna manera de avanzar. Esta situación es común con algoritmos voraces, por lo que debe haber una forma de obtener provecho de las soluciones callejón sin salida.

El algoritmo realiza un seguimiento de cuánto tiempo transcurrido desde que se ha progresado — es decir, se ha encontrado un grupo con un tamaño mayor. Después de un cierto tiempo con ningún progreso, reinicia el algoritmo propio. El grupo está desactivada. Esta vez el algoritmo elige aleatoriamente el nodo 3 como el nodo inicial. Mediante el mismo proceso iterativo para encontrar el mejor nodo para agregar o quitar, el algoritmo eventualmente descubre a la camarilla máxima de {0, 1, 3, 4}. En la mayoría de los problemas que se utilizan algoritmos voraces, la solución óptima es desconocida, por lo que el algoritmo continúa hasta que se cumple alguna condición de detención. En este caso, el algoritmo está configurado para que se detenga después de 20 iteraciones. En este momento, se muestra el mejor grupo encontrado.

En las secciones siguientes, examinaré el código que genera la captura de pantalla de figura 2. El código fuente completo está disponible en code.msdn.microsoft.com/mag201110TestRun (esta columna usa el mismo código desde el mes pasado). En este artículo se supone que tiene conocimientos de programación de nivel intermedio con un idioma de la serie c o VB.NET compatible. Utilizar C#, pero he escrito el código para que puedan refactorizar para otro idioma sin demasiada dificultad si lo desea.

Estructura general del programa

La estructura general del programa se muestra en la figura 2 se presenta en figura 3. El programa tiene dependencias en los espacios de nombres del sistema, System.Collections.Generic (un grupo se representa como tipo de lista ), System.IO (para cargar el gráfico de origen desde un archivo de texto) y System.Collections (la clase de MyGraph definido por el programa utiliza la clase BitArray). Cambiar el nombre de la clase principal desde el programa de la plantilla genera Visual Studio a GreedyMaxCliqueProgram para mayor claridad. Utilizar un objeto Random de ámbito de clase denominado "aleatorio" para inicializar y restablecer a un grupo en un nodo aleatorio y romper los vínculos cuando hay más de un nodo mejor para agregar o quitar.

Estructura de programa general de la figura 3

using System;
using System.Collections.Generic;
using System.IO;
using System.Collections;
 
namespace GreedyMaxClique
{
  class GreedyMaxCliqueProgram
  {
    static Random random = null;
 
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin greedy maximum clique demo\n");
 
        string graphFile = "..
\\..
\\DimacsGraph.clq";
        Console.WriteLine("Loading graph into memory");
        Console.WriteLine("Graph loaded and validated\n");
        MyGraph graph = new MyGraph(graphFile, "DIMACS");
 
        int maxTime = 20;
        int targetCliqueSize = graph.NumberNodes;
 
        List<int> maxClique = FindMaxClique(graph, maxTime,
          targetCliqueSize);
        Console.WriteLine("\nMaximum time reached");
        Console.WriteLine("\nSize of best clique found = " +
          maxClique.Count);
 
        Console.WriteLine("\nBest clique found:");
        Console.WriteLine(ListAsString(maxClique));
 
        Console.WriteLine("\nEnd greedy maximum clique demo\n");
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal: " + ex.Message);
      }
    } // Main
 
    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> possibleAdd)
    {
      // ...
}
 
    static int GetNodeToDrop(MyGraph graph, List<int> clique,
      List<int> oneMissing)
    {
      // ...
}
 
    static List<int> MakeOneMissing(MyGraph graph, List<int> clique)
    {
      // ...
}
 
    static string ListAsString(List<int> list)
    {
      // ...
}
  } // class Program
 
  public class MyGraph
  {
    // ...
}
} // ns

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 un formato de archivo estándar denominado DIMACS. El método clave de MyGraph es AreAdjacent, que devuelve true si dos nodos están conectados. Establezco maxTime en 20 para establecer una condición de detención absoluta para el algoritmo voraz. Establecer targetCliqueSize para establecer una segunda condición de detención; Si se encuentra un grupo que tiene el mismo número de nodos, ya que hay en el gráfico, la camarilla máxima debe han encontrado.

El método FindMaxClique

Todo el trabajo se realiza por el método FindMaxClique, que utiliza un algoritmo voraz para buscar el grupo más grande posible. FindMaxClique llama a varios métodos auxiliares, lo cual describiré en detalle. Se deben estructurar el programa utilizando los métodos estáticos, pero desea refactorizar el código que presento aquí a un enfoque totalmente orientado a objetos. El método FindMaxClique se repite hasta que una de las condiciones de dos detención se cumple y, a continuación, devuelve al mejor grupo encontrado. La definición del programa incluye una clase de MyGraph incrustada, que haya sido objeto de artículo del mes pasado.

En el pseudocódigo de alto nivel, el algoritmo de FindMaxClique es:

initialize clique with a single node
get list of candidate nodes to add
loop until stop condition met
  if there are nodes that can be added
    find best node to add and add to clique
  else
    find best node to drop and drop from clique
 
  if lack of progress
    restart algorithm
 
  update list of candidate nodes
end loop
return largest clique found

Comienza la definición del método FindMaxClique:

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 grupo local es el grupo actual. He creado una instancia el objeto Random mediante un valor de inicialización arbitraria de 1. La variable de tiempo es una variable de contador de bucle; Puesto que es independiente, un buen nombre alternativo sería "graduación". Realizar un seguimiento de la hora cuando se ha encontrado el grupo mejor actual y la hora del último reinicio para controlar cuando se reinicia sucederá. Asigno valores no válidos de -1 a las variables para el nodo de agregar y colocar:

int randomNode = random.Next(0, graph.NumberNodes);
Console.WriteLine("Adding node " + randomNode);
clique.Add(randomNode);
...

El método Random.Next(x,y) devuelve un valor mayor o igual a x y estrictamente menor que y. Por valor de x = 0 e y = NumberNodes, obtener un nodo aleatorio de 0 a 8 inclusive para el gráfico de ejemplo:

List<int> bestClique = new List<int>();
bestClique.AddRange(clique);
int bestSize = bestClique.Count;
timeBestClique = time;
...

La lista de bestClique se utiliza para realizar un seguimiento de una copia de la camarilla más grande encontrada durante búsqueda del algoritmo. Utilizo el método AddRange útil para copiar los elementos en el grupo actual en bestClique. La variable bestSize se utiliza para mayor comodidad. El timeBestClique se utiliza para determinar si se producirá un reinicio del algoritmo:

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

El método auxiliar MakePossibleAdd examina al grupo actual y crea una lista de todos los nodos que se pueden agregar a la camarilla para aumentar el tamaño del grupo por uno. Esta lista es el origen de los candidatos para el mejor nodo para agregar a la camarilla. El método auxiliar de MakeOneMissing es un poco complicado. El método construye una lista de todos los nodos que están conectados al nodo todos menos uno en el grupo actual. Como verá, esta lista de oneMissing se utiliza para determinar el mejor nodo para eliminar de un grupo. Ahora comenzar el bucle de procesamiento principal:

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

Como ya he explicado anteriormente, algoritmos voraces normalmente necesitan una o varias condiciones de detención. Aquí el bucle termina si se supera el número máximo de iteraciones o el tamaño de la camarilla actual cumple con un tamaño de destino. La variable cliqueChanged se utiliza para controlar la lógica de bifurcación entre la adición de nodos y colocar los nodos. Podría ha omitido esta variable y utilizar un Si..Else estructura en lugar de separadas de control Si..a continuación, las instrucciones, pero en este caso, el uso de una variable de control de bifurcación conduce al código que es más fácil de leer y modificar, en mi opinión:

if (possibleAdd.Count > 0) {
  nodeToAdd = GetNodeToAdd(graph, possibleAdd);
  Console.WriteLine("Adding node " + nodeToAdd);
  clique.Add(nodeToAdd);
  clique.Sort();
  cliqueChanged = true;
  if (clique.Count > bestSize) {
    bestSize = clique.Count;
    bestClique.Clear();
    bestClique.AddRange(clique);
  }
} // add
...

Comprobar para asegurarme de que hay al menos un nodo que se puede agregar a la camarilla y, a continuación, llame al método auxiliar GetNodeToAdd. Este método analiza la lista de nodos en la lista de possibleAdd y devuelve el mejor nodo para agregar (la explicación oft prometido de "mejores" presentada cuando describa GetNodeToAdd). Este nodo se agrega a la camarilla actual. En este momento ordeno a la camarilla, porque más adelante en el algoritmo necesita buscar al grupo y, si el grupo está ordenada, puedo usar una búsqueda rápida en binaria en lugar de una búsqueda lineal. El nuevo grupo se comprueba para ver si es mejor (mayor) que el grupo mejor actual.

A continuación se incluye:

if (cliqueChanged == false) {
  if (clique.Count > 0) {
    nodeToDrop = GetNodeToDrop(graph, clique, oneMissing);
    Console.WriteLine("Dropping node " + nodeToDrop);
    clique.Remove(nodeToDrop);
    clique.Sort();
    cliqueChanged = true;
  }
} // drop
...

Si no se puede aumentar el tamaño de la camarilla actual, el algoritmo intenta colocar un nodo de la camarilla. El método auxiliar GetNodeToDrop selecciona el nodo mejor para colocar desde el grupo:

int restart = 2 * bestSize;
if (time - timeBestCliqueFound > restart &&
  time - timeLastRestart > restart) {
   Console.WriteLine("\nRestarting\n");
   timeLastRestart = time;
   int seedNode = random.Next(0, graph.NumberNodes);
   clique.Clear();
   Console.WriteLine("Adding node " + seedNode);
   clique.Add(seedNode);
} // restart
...

En este momento, el algoritmo comprueba si se ha producido una falta de progreso. La variable de reinicio determina cuánto tiempo debe esperar antes de reiniciar. Aquí uso un valor de dos veces el tamaño de la actual camarilla mejor. En la investigación sobre el valor máximo del grupo, el valor óptimo para el reinicio sigue siendo una cuestión pendiente. El valor que utiliza aquí se basa en experimentos que he realizado con varios problemas de gráfico de referencia. Si ha habido falta de progreso en la búsqueda de una nueva solución mejor, o si han transcurrido desde el último reinicio de un tiempo relativamente largo, se produce un reinicio. Si se realiza un reinicio, el algoritmo vacía al grupo actual y, a continuación, selecciona un nodo aleatorio de todos los nodos en el gráfico. Observe que este es un enfoque crudo; Si hacen referencia a la demostración que se ejecute figura 2, verá que el último reinicio selecciona un nodo inicial que ya había sido utilizado como el primer nodo de semillas:

...
possibleAdd = MakePossibleAdd(graph, clique);
    oneMissing = MakeOneMissing(graph, clique);
  } // loop
  return bestClique;
}

El método FindMaxClique calcula desde el principio las listas de possibleAdd y oneMissing basadas en el nuevo grupo. Cuando termina el bucle de procesamiento principal, el método devuelve al mejor grupo encontrado.

Agregar el nodo mejor

Hay dos pasos para determinar el mejor nodo para agregar a la camarilla actual. En primer lugar, se necesita una lista de todos los nodos que aumentará el tamaño de la camarilla actual. En segundo lugar, se necesita alguna manera de determinar cuál de estos nodos es el mejor nodo:

static List<int> MakePossibleAdd(MyGraph graph, List<int> clique)
{
  List<int> result = new List<int>();
  for (int i = 0; i < graph.NumberNodes; ++i) {
    if (FormsALargerClique(graph, clique, i) == true)
      result.Add(i);
  }
  return result;
}

El método MakePossibleAdd recorre cada nodo en el gráfico. Si está examinando el nodo está conectado a todos los nodos en el grupo actual según lo determinado por la aplicación auxiliar FormsALargerClique, a continuación, el nodo que se está examinando es un posible nodo de "Agregar" y se une a la lista de resultados. Observe el resultado podría ser una lista vacía, pero nunca será null:

static bool FormsALargerClique(MyGraph graph, List<int> clique, int node)
{
  for (int i = 0; i < clique.Count; ++i) {
    if (graph.AreAdjacent(clique[i], node) == false)
      return false;
  }
  return true;
}

El método FormsALargerClique compara un nodo contra todos los nodos en el grupo actual. Si el nodo candidato no es adyacente a incluso uno de los nodos en el grupo, no se puede agregar el nodo candidato para el grupo actual. Tenga en cuenta que debido a que AreAdjacent devuelve false cuando un nodo se compara con la suya propia, no se agregará los nodos en el grupo actual a la lista de nodos de possibleAdd.

Es la idea principal detrás de determinar el mejor nodo para agregar seleccionar el nodo de la lista de nodos de possibleAdd que es la más conectado a todos los nodos en el conjunto de possibleAdd. Un nodo que está conectado altamente ofrece la más grande posible nueva lista de nodos que se agregan en la siguiente iteración del algoritmo de.

A continuación se incluye:

static int GetNodeToAdd(MyGraph graph, List<int> possibleAdd)
{
  if (possibleAdd.Count == 1)
    return possibleAdd[0];
...

El método GetNodeToAdd se supone que la lista de possibleAdd tiene al menos un nodo. Si hay exactamente un nodo, que debe ser el mejor nodo:

int maxDegree = 0;
for (int i = 0; i < possibleAdd.Count; ++i) {
  int currNode = possibleAdd[i];
  int degreeOfCurrentNode = 0;
  for (int j = 0; j < possibleAdd.Count; ++j) {
    int otherNode = possibleAdd[j];
    if (graph.AreAdjacent(currNode, otherNode) == true)
      ++degreeOfCurrentNode;
  }
  if (degreeOfCurrentNode > maxDegree)
    maxDegree = degreeOfCurrentNode;
}
...

Podría haber varios nodos en la lista de possibleAdd que están vinculados con otras personas como más conectado a otros nodos en la lista. Por ejemplo, supongamos que el gráfico en el análisis es el gráfico se muestra en la figura 1 y el grupo actual tiene nodos sólo 0. Los nodos de possibleAdd son {1, 3, 4}. El nodo 1 está conectado a dos de los nodos de possibleAdd — y, de hecho, por lo que son nodos 3 y 4. Por lo que se realiza un análisis preliminar para determinar el número máximo de conexiones disponibles:

List<int> candidates = new List<int>();
for (int i = 0; i < possibleAdd.Count; ++i) {
  int currNode = possibleAdd[i];
  int degreeOfCurrentNode = 0;
  for (int j = 0; j < possibleAdd.Count; ++j) {
    int otherNode = possibleAdd[j];
    if (graph.AreAdjacent(currNode, otherNode) == true)
      ++degreeOfCurrentNode;
    }
    if (degreeOfCurrentNode == maxDegree)
      candidates.Add(currNode);
}
...

Una vez que se conoce el número máximo de conexiones, el algoritmo examina la lista de possibleAdd y agrega cada uno de los nodos de possibleAdd que tiene el número máximo de conexiones a una lista de nodos candidatos. Tenga en cuenta que el análisis de la doble podían eliminarse mediante el uso de almacenes de datos auxiliares para mantener el seguimiento del número de conexiones de cada nodo de possibleAdd:

...
return candidates[random.Next(0, candidates.Count)];
}

En este momento, la lista de candidatos tiene uno o varios nodos mejores para agregar a la camarilla. Observe que los candidatos deben tener un recuento de al menos uno porque se supone que la lista de possibleAdd tiene un recuento de al menos uno. El algoritmo aleatoriamente selecciona uno de los nodos del candidato y lo devuelve. Podía has puesto en una comprobación para ver si el tamaño de la lista de candidatos es exactamente uno y si es así, devolver el único nodo de candidatos.

Quitando el nodo mejor

Determinar el mejor nodo para colocar desde el grupo actual es un poco sutil. La idea es colocar el nodo en el grupo actual que dará como resultado el mayor aumento en la lista de nodos de possibleAdd.

Una forma de hacerlo es probar cada nodo en el grupo actual por eliminarlo realmente el grupo actual y, a continuación, calcular el tamaño de la lista de possibleAdd resultante. Pero hay un enfoque mucho más eficaz que utiliza una lista de nodos que están conectados a todos excepto exactamente uno de los nodos en el grupo actual. Si hay una lista de oneMissing de nodos, la lista puede utilizarse como sigue: escanear a través de cada nodo en el grupo actual y contar el número de nodos en la lista de oneMissing no está conectado al nodo de grupo. El nodo en el grupo actual que está conectado a la menos para los nodos de la lista de oneMissing es el mejor nodo a colocar. Después de colocar este nodo conectados por lo menos, todos los nodos de la lista de oneMissing que no estaba conectado al nodo perdido ahora totalmente conectará a los nodos restantes en el grupo, por lo tanto, convirtiéndose en nuevos nodos de possibleAdd.

El método MakeOneMissing se presenta en figura 4. El método recorre cada nodo en el gráfico. La idea es contar el número de nodos en el grupo está conectado al nodo actual que se está examinando. Si el recuento total de nodos conectados es exactamente uno menor que el tamaño de la camarilla actual y, a continuación, el nodo que se está examinando es un oneMissing. El método cortocircuitos si el nodo actual que se está examinando sea menor que el número necesario de vecinos. El método debe filtrar los nodos que ya están en el grupo porque están conectados al nodo todos menos uno en su propio grupo (es decir, ellos mismos). Debido a que se ordena el grupo actual (después de cada agregar o colocar), se puede utilizar una búsqueda binaria en lugar de una búsqueda lineal más lenta (consulte figura 4).

Figura 4 hacer lista de nodos de oneMissing

static List<int> MakeOneMissing(MyGraph graph, List<int> clique)
{
  int count;
  List<int> result = new List<int>();
  for (int i = 0; i < graph.NumberNodes; ++i) {
    count = 0;
    if (graph.NumberNeighbors(i) < clique.Count - 1) continue;
    if (clique.BinarySearch(i) >= 0) continue;
    for (int j = 0; j < clique.Count; ++j) {
      if (graph.AreAdjacent(i, clique[j]))
        ++count;
    }
    if (count == clique.Count - 1)
      result.Add(i);
  }
  return result;
}

Comienza el método GetNodeToDrop:

static int GetNodeToDrop(MyGraph graph, List<int> clique,
  List<int> oneMissing)
{
  if (clique.Count == 1)
    return clique[0];
...

El método supone que el grupo actual tiene al menos un nodo. Si hay sólo un nodo en el grupo actual, es el único nodo que se puede colocar. El método determina el número máximo de nodos de la lista de oneMissing que no está conectado a cualquier nodo en el grupo actual porque podría haber más de un nodo en el grupo que se ha desconectado al máximo a la lista de oneMissing:

int maxCount = 0;
for (int i = 0; i < clique.Count; ++i) {
  int currCliqueNode = clique[i];
  int countNotAdjacent = 0;
  for (int j = 0; j < oneMissing.Count; ++j) {
    int currOneMissingNode = oneMissing[j];
    if (graph.AreAdjacent(currCliqueNode, currOneMissingNode) == false)
      ++countNotAdjacent;
  }
  if (countNotAdjacent > maxCount)
    maxCount = countNotAdjacent;
}
...

Una vez que se conoce el número máximo de desconexiones, el método vuelve a examinar el clique para encontrar aquellos nodos que más están desconectados y se agregan a una lista de candidatos. Al igual que con el método GetNodeToAdd, GetNodeToDrop podría evitar una repetición del análisis mediante el mantenimiento de almacenes de datos auxiliares:

List<int> candidates = new List<int>();
for (int i = 0; i < clique.Count; ++i) {
  int currCliqueNode = clique[i];
  int countNotAdjacent = 0;
  for (int j = 0; j < oneMissing.Count; ++j) {
    int currOneMissingNode = oneMissing[j];
    if (graph.AreAdjacent(currCliqueNode, currOneMissingNode) == false)
      ++countNotAdjacent;
  }
  if (countNotAdjacent == maxCount)
    candidates.Add(currCliqueNode);
}
...

Método GetNodeToDrop finaliza devolviendo un nodo seleccionado aleatoriamente en la lista de nodos mejores quitar:

...
return candidates[random.Next(0, candidates.Count)];
} // GetNodeToDrop

Observaciones finales

¿La eficacia, son algoritmos voraces? A pesar de su relativa simplicidad, algoritmos voraces han demostrado ser muy eficaz en muchos escenarios de problema. Sin embargo, eficacia puede definirse mediante varios criterios, como la velocidad y calidad de la solución. Ejecuté este algoritmo contra varios problemas de gráfico de referencia extremadamente difícil mantenidas por la organización de investigación DIMACS y el algoritmo es bastante eficaz, rápidamente y producir a grupos máximas que estaban generalmente dentro de 5 por ciento de las soluciones más conocidas.

Algoritmos avariciosos de pruebas pueden ser complicada. Además de todos los controles normales pruebas técnicas tales como las pruebas, pruebas y así sucesivamente condición de límite de unidades, y porque los algoritmos avariciosos tienen soluciones que crecen con el tiempo — una estrategia eficaz de las pruebas consiste en escribir métodos auxiliares que comprobación el estado de las estructuras de datos utilizado por el algoritmo de forma iterativa. Por ejemplo, al probar el algoritmo clique máxima presentado aquí, escribí métodos que comprueban que no había ningún nodo duplicado en el grupo actual, compruebe ningún nodo en el grupo actual está en la actual possibleAdd o oneMissing actual se muestra y así sucesivamente.

El algoritmo voraz clique máxima que he presentado aquí puede modificarse para producir mejores resultados de varias maneras. Es una técnica común de algoritmos voraces más agregar una característica denominada TS. Algoritmos de TS mantienen una lista de los datos utilizados recientemente y, posiblemente, una lista de soluciones vistas recientemente. Datos de la lista de TS no se utilizan para construir nuevas soluciones. Además, algoritmos voraces con frecuencia pueden emplear una estrategia de búsqueda de la fase estacionaria. Cuando no puede mejorar su solución actual un algoritmo voraz, una búsqueda de meseta produce una nueva solución sin ir hacia atrás, como colocar un nodo en el problema de la clique máxima. Presentaré estas útiles e interesantes de TS y técnicas de meseta en una columna futura.

Dr. James McCaffrey trabaja en Volt Information Sciences Inc., donde encarga de formación técnica, los ingenieros de software en el Microsoft Redmond, Washington, campus. Ha colaborado en el desarrollo de varios productos de Microsoft como, por ejemplo, Internet Explorer y MSN Search. Dr. McCaffrey es el autor de ".NET Test Automation Recipes"(Apress, 2006) y puede ponerse en jammc@microsoft.com.

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