Este artigo foi traduzido por máquina.

Execução de teste

Os algoritmos greedy e o número máximo de grupos

James McCaffrey

Baixar o código de exemplo

Na coluna deste mês, apresentarei uma solução para o problema de clique máximo do gráfico.A solução usa o que chamamos de um algoritmo greedy e falarei sobre como projetar e testar esses algoritmos.A idéia do problema clique máximo é encontrar o maior grupo de nós em um gráfico que são conectados uns aos outros.Dê uma olhada no gráfico simple da a Figura 1.O gráfico tem nove nós e bordas de 13.O gráfico é a média não ponderado (não há nenhum prioridades associadas com as bordas) e não dirigido (todas as bordas são bidirecional).Nós de 2, 4 e 5 formam um clique do tamanho de três.O clique em máximo é que o conjunto de nós 0, 1, 3 e 4, que formam um clique do tamanho de quatro.

 

Figura 1 gráfico para um algoritmo Greedy Clique do máximo

O problema de clique máximo é interessante por vários motivos.Embora não seja aparente no gráfico simple em a Figura 1, o problema de clique máximo é um dos mais desafiadores em ciências da computação.Ele surge em muitos aplicativos importantes como, por exemplo, análise de comunicação de rede social, onde nós representam as pessoas e bordas representam uma mensagem ou relacionamento.E o problema de clique máximo se presta bem a solução por um algoritmo greedy, que é uma técnica fundamental em ciências da computação.

Em termos informais, um algoritmo greedy é um algoritmo que começa com uma solução simple, incompleta para um problema difícil e, em seguida, iterativamente procura a melhor maneira de melhorar a solução.O processo é repetido até que alguma condição de parada seja atingida.Figura 2 ilustra as idéias importantes do problema clique máximo e mostra aonde quero chegar neste artigo.

Figura 2 máximo Greedy demonstração de clique em Run

Eu tenho um aplicativo de console, que começa a carregar na memória o gráfico que corresponde à mostrada na a Figura 1.Criar e codificar uma estrutura de dados do gráfico eficiente são um problema significativo por si só.Expliquei o código de estrutura de dados do gráfico em minha última coluna (msdn.microsoft.com/magazine/hh456397).O algoritmo primeiro seleciona um único nó aleatoriamente, esse nó de cenário 2 e inicializa um clique com o nó.Em seguida, o algoritmo de procura o melhor nó para o clique em Adicionar.Se você fizer referência a a Figura 1, você verá que há apenas dois nós, 4 e 5, que formarão um clique maior.Explicarei o que o nó melhor significa em breve.

O algoritmo seleciona e adiciona o nó 4 para o clique, portanto, o clique é agora {2, 4}.Neste ponto, há apenas um nó no gráfico, 5, que aumentará o tamanho do clique, para que o algoritmo seleciona o nó 5 e o adiciona o clique.Agora, não há nenhum nó disponível aumentará o tamanho do clique.Os descartes algoritmo o nó melhor do que o clique na esperança de que um nó de novo, diferente pode ser adicionado que permitirão o progresso.Novamente, posso explicar o que significa "melhor" em breve.O algoritmo cai 4 do nó do clique.Como você pode ver, observando o gráfico, não há nenhuma maneira de tornar o progresso.Essa situação é comum com algoritmos greedy, portanto, deve haver uma maneira de aproveitar soluções beco sem saída.

O algoritmo está controlando quanto tempo desde o progresso feito — ou seja, um clique, com um tamanho maior foi encontrado.Após um certo período de tempo com nenhum progresso, o algoritmo reinicia a mesmo.O clique está desmarcada.Desta vez o algoritmo aleatoriamente escolhe o nó 3 como o nó inicial.Usando o mesmo processo iterativo para localizar o melhor nó para adicionar ou Cancelar, o algoritmo eventualmente descobre o máximo clique {0, 1, 3, 4}.Na maioria dos problemas que sejam utilizados algoritmos greedy, a solução ideal não é conhecida, para que o algoritmo continua até que alguma condição de parada seja atendida.Nesse caso, o algoritmo está configurado para parar após 20 iterações.Neste ponto, o clique melhor encontrado é exibida.

Nas seções a seguir, vou lhe apresentar através do código que produziu a captura de tela na a Figura 2.O código-fonte completo está disponível em code.msdn.microsoft.com/mag201110TestRun (esta coluna usa o mesmo código desde o último mês).Este artigo pressupõe que você tem a habilidade de programação de nível intermediário com uma linguagem C-família ou o VB.NET compatível.Posso usar C#, mas escrevi o código para que você conseguirá refatorá-lo para outro idioma sem muita dificuldade, se desejar.

Estrutura geral do programa

A estrutura geral do programa mostrado na a Figura 2 é apresentado em a Figura 3.O programa tem dependências nos espaços para nome de sistema, System.Collections.Generic (um clique é representado como um tipo de lista de <int>), System. IO (para carregar o gráfico de origem de um arquivo de texto) e System. Collections (a classe de MyGraph definida pelo programa usa a classe BitArray).Posso renomear a classe principal do programa Visual Studio modelo gerado para GreedyMaxCliqueProgram para maior clareza.Posso usar um objeto de Random de escopo de classe chamado "aleatórios" para inicializar e redefinir um clique em um nó aleatório e quebrar ties quando há mais de um nó de melhor para adicionar ou Cancelar.

Estrutura de programa geral de 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

O gráfico é representado como um objeto de MyGraph definido pelo programa. O gráfico é carregado a partir de um arquivo de texto externo, que usa um formato de arquivo padrão chamado DIMACS. O método principal de MyGraph é AreAdjacent, que retorna true se dois nós estão conectados. Defino maxTime 20 para definir uma condição de parada absoluto para o algoritmo greedy. Conjunto de targetCliqueSize para estabelecer uma segunda condição de parada; Se um clique for encontrado, que tem o mesmo número de nós, já que há no gráfico, o clique em máximo deve ter foi encontrado.

O método FindMaxClique

Todo o trabalho é feito pelo método FindMaxClique, que usa um algoritmo greedy para procurar o clique maior possível. FindMaxClique chama vários métodos auxiliares, que descreverei em detalhes. Estrutura de programa usando os métodos estáticos, mas talvez você queira refatorar o código que apresento aqui para uma abordagem totalmente orientada a objeto. O método FindMaxClique itera até que uma das condições dois interrompendo for satisfeita e retorna o clique melhor encontrado. A definição do programa inclui uma classe de MyGraph incorporada, que era o assunto do artigo do mês passado.

No pseudocódigo de alto nível, o algoritmo de FindMaxClique é:

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

A definição do método FindMaxClique começa:

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;
...

O objeto de clique local é o atual clique. Instanciar o objeto Random usando um valor de semente arbitrário de 1. A variável de tempo é uma variável de contador de loop; como é discreta, um bom nome alternativo seria "tick". Posso controlar o tempo quando o clique melhor atual foi encontrado e a hora da última reinicialização para controlar quando reinicializações acontecerá. Atribuir valores fictícios de -1 a variáveis para o nó de soltar e adicionar nós:

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

O método Random.Next(x,y) retorna um valor maior ou igual a x e estritamente menores do que o y. Definindo x = 0 e y = NumberNodes, recebo um nó aleatório de 0 a 8, inclusive para o gráfico de exemplo:

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

A lista de bestClique é usada para controlar uma cópia do clique maior encontrado durante pesquisa do algoritmo. Uso o método AddRange úteis para copiar os itens em que a atual clique em bestClique. A variável bestSize é usada por conveniência. O timeBestClique é usado para determinar se uma reinicialização do algoritmo irá ocorrer:

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

O método auxiliar MakePossibleAdd examina a atual clique e constrói uma lista de todos os nós que podem ser adicionados por um para o clique para aumentar o tamanho do clique. Esta lista é a origem de candidatos para o nó de melhor para o clique em Adicionar. O método auxiliar MakeOneMissing é um pouco complicado. O método constrói uma lista de todos os nós conectados a apenas um nó em que o clique atual. Como você verá, esta lista de oneMissing é usada para determinar o melhor nó para soltar de um clique. Agora posso começar o loop de processamento principal:

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

Como expliquei anteriormente, algoritmos greedy normalmente precisam de uma ou mais condições de parada. Aqui o loop é encerrado se o número máximo de iterações for excedido ou o tamanho do que a atual clique atende a um tamanho de destino. A variável cliqueChanged é usada para controlar a lógica de ramificação entre a adição de nós e soltando nós. Eu poderia ter omitido essa variável e usado um se..outra controlam a estrutura em vez de separada se..em seguida, instruções, mas neste caso, o uso de uma variável de controle de ramificação leva ao código que é mais fácil de ler e modificar, na minha opinião:

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
...

Eu Verifique se há pelo menos um nó que pode ser adicionado para o clique em e em seguida, chame o método auxiliar GetNodeToAdd. Esse método verifica a lista de nós na lista possibleAdd e retorna o nó melhor para adicionar (a explicação oft prometidos da "melhor" será apresentada quando estiver descrevendo GetNodeToAdd). Este nó é adicionado para o clique atual. Nesse ponto eu classificar o clique, porque mais tarde no algoritmo preciso pesquisar o clique, e se o clique for classificado, posso usar uma pesquisa rápida de binária em vez de uma pesquisa linear. O clique de novo é verificado para ver se é melhor (maior) que o clique melhor atual.

A próxima etapa é:

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
...

Se o tamanho do clique atual não pode ser aumentado, o algoritmo tenta cancelar um nó do clique. O método auxiliar GetNodeToDrop seleciona o nó melhor para soltar a partir do clique:

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
...

Neste ponto, o algoritmo verifica se houve uma falta de progresso. A variável de reinicialização determina quanto tempo esperar antes de reiniciar. Aqui, eu uso um valor do dobro do tamanho do clique melhor atual. Na pesquisa sobre o valor máximo de clique, o valor ideal para a reinicialização ainda é uma questão em aberto. O valor que eu use aqui se baseia em experimentos que executou com vários problemas de gráfico padrão de referência. Uma reinicialização ocorrerá se tiver havido falta de progresso na localização de uma nova solução melhor ou se ele tiver sido um tempo relativamente longo desde a última reinicialização. Se uma reinicialização for feita, o algoritmo esvazia o clique atual e, em seguida, seleciona um nó aleatório de todos os nós no gráfico. Observe que se trata de uma abordagem crua; Se você consultar novamente a demonstração executado em a Figura 2, você verá que a última reinicialização escolheu um nó inicial que já tenha sido usado como o primeiro nó de propagação:

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

O método de FindMaxClique calcula desde o início, as listas de possibleAdd e oneMissing com base em que o clique de novo. Quando o loop de processamento principal é encerrado, o método retorna o clique melhor encontrado.

Adicionar o nó melhor

Há duas etapas para determinar o melhor nó para adicionar o clique atual. Primeiro, uma lista de todos os nós que aumentará o tamanho do clique atual é necessária. Em segundo lugar, alguma forma para determinar qual de nós é o nó melhor é necessária:

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;
}

O método MakePossibleAdd examina cada nó no gráfico. Se o nó que está sendo examinada está conectada a todos os nós do clique atual, conforme determinado pelo auxiliar FormsALargerClique, em seguida, o nó que está sendo examinado é um nó de "Adicionar" possíveis e ingressa na lista de resultados. Observe o resultado poderia ser uma lista vazia, mas nunca será nulo:

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;
}

O método FormsALargerClique compara um nó em relação a todos os nós do clique atual. Se o nó candidato não estiver adjacente ao mesmo um de nós no clique, o nó candidato não pode ser adicionado para o clique atual. Observe que, como AreAdjacent retorna Falso quando um nó é comparado com o próprio, nós o clique atual não serão adicionados à lista de nós de possibleAdd.

A idéia principal por trás de determinar o melhor nó para adicionar é selecionar o nó da lista de nós possibleAdd mais conectado a todos os outros nós no conjunto de possibleAdd. Um nó que está conectado altamente produz a nova lista de nós para adicionar a próxima iteração do algoritmo de possível maior.

A próxima etapa é:

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

O método GetNodeToAdd supõe que a lista de possibleAdd tem pelo menos um nó. Se houver exatamente um nó, que deve ser o melhor nó:

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;
}
...

Pode haver vários nós na lista possibleAdd que são associados com outras pessoas como sendo mais conectado aos outros nós na lista. Por exemplo, suponha que o gráfico de análise é mostrado no gráfico a Figura 1 e o clique atual tem apenas nó 0. Os nós de possibleAdd são {1, 3 e 4}. O nó 1 está conectado a dois nós de possibleAdd — e, na verdade, então, são nós 3 e 4. Portanto, é feita uma verificação preliminar para determinar o número máximo de conexões disponíveis:

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);
}
...

Depois que o número máximo de conexões é conhecido, o algoritmo examina a lista de possibleAdd e adiciona cada um de nós no possibleAdd que tem o número máximo de conexões a uma lista de nós de candidato. Observe que a verificação de duplo pode ser eliminada usando os armazenamentos de dados auxiliares para controlar o número de conexões em que cada nó de possibleAdd tem:

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

Neste ponto, a lista de candidatos possui um ou mais nós de melhores para o clique em Adicionar. Observe que os candidatos devem ter uma contagem de pelo menos um porque a lista de possibleAdd será considerada para ter uma contagem de pelo menos um. O algoritmo aleatoriamente seleciona um de nós candidatos e o retorna. Poderia tiver colocado em uma verificação para ver se o tamanho da lista de candidatos é exatamente um e em caso afirmativo, retornar o nó único de candidatos.

Descartando o melhor nó

Determinar o melhor nó para soltar do clique atual é um pouco sutil. A idéia é descartar um nó no clique atual que resultarão no maior aumento na lista de nós de possibleAdd.

Uma maneira de fazer isso é testar cada nó em que o clique atual, na verdade, removendo-o de que o clique atual e, em seguida, o tamanho da lista possibleAdd resultante de computação. Mas há uma abordagem muito mais eficiente que usa uma lista de nós que estão conectados a todos, exceto exatamente um de nós no clique atual. Se não houver tal lista oneMissing de nós, a lista pode ser usada da seguinte maneira: varredura através de cada nó em que o clique atual e contar quantos nós na lista oneMissing não são conectados ao nó clique. O nó em que o clique atual que esteja conectada de menos para os nós na lista oneMissing é o nó melhor para soltar. Depois de soltar este nó conectado a menos, todos os nós na lista oneMissing que não estavam conectados ao nó eliminado serão agora totalmente conectados para os nós restantes no clique, portanto, tornando-se novos nós de possibleAdd.

O método MakeOneMissing é apresentado em a Figura 4. O método examina cada nó no gráfico. A idéia é contar quantos nós o clique estão conectados ao nó atual sendo examinado. Se o total de contagem de nós conectados é exatamente uma menor que o tamanho do clique atual, o nó que está sendo examinado é um nó de oneMissing. O método short-circuits se o nó atual sendo examinado tiver menos que o número necessário de vizinhos. O método deve filtrar os nós que já estão sendo o clique porque estão conectados para apenas um nó em seu próprios clique (ou seja, si). Porque o clique atual for classificado (após cada add ou drop), uma pesquisa binária pode ser usada em vez de uma pesquisa mais lenta linear (consulte a Figura 4).

Figura 4 fazer lista de nós 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;
}

O método GetNodeToDrop começa:

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

O método pressupõe que o clique atual tem pelo menos um nó. Se houver apenas um nó em que o clique atual, ele é o único nó que pode ser descartado. O método determina o maior número de nós na lista oneMissing que não estão conectados a qualquer nó do clique atual porque pode haver mais de um nó a clique desconectado maximally à 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;
}
...

Depois que o número máximo de desconexões for conhecido, o método examina o clique para localizar os nós que mais são desconectados e adiciona cada um para uma lista de candidatos. Assim como acontece com o método GetNodeToAdd, GetNodeToDrop poderia evitar um reexame, mantendo os armazenamentos de dados 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 termina retornando um nó selecionado aleatoriamente da lista de nós melhores para soltar:

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

Considerações finais

Qual serão a eficácia algoritmos greedy? Apesar de sua relativa simplicidade, algoritmos greedy demonstraram que seja bastante eficaz em muitos cenários de problema. No entanto, a eficácia pode ser definida usando diversos critérios, incluindo a velocidade e a qualidade da solução. Executei esse algoritmo contra vários problemas de gráfico de benchmark extremamente difícil mantidos pela organização de pesquisa de DIMACS e o algoritmo foi bastante eficaz, funcionando com rapidez e produzindo máximo cliques que eram geralmente dentro de 5 por cento das soluções mais conhecidas.

Testes de algoritmos greedy podem ser complicado. Com todos os controles usuais técnicas, como testes de unidade, testes e assim por diante de condição de limite de teste — e porque os algoritmos greedy possuem soluções que crescem ao longo do tempo — uma estratégia eficaz de teste é escrever métodos auxiliares que iterativamente verificar o estado das estruturas de dados usada pelo algoritmo. Por exemplo, ao testar o algoritmo de clique máximo apresentado aqui, eu escrevi métodos que verifique se que não havia nenhum nó duplicados no clique atual, verifique se nenhum nó em que o clique atual está na possibleAdd atual ou listas de oneMissing atual e assim por diante.

O algoritmo greedy clique máximo que apresentei aqui pode ser modificado para produzir melhores resultados de várias maneiras. Uma técnica comum para os algoritmos mais greedy, é adicionar um recurso chamado tabu. Algoritmos de tabu mantêm uma lista de dados usados recentemente e, possivelmente, uma lista de soluções vistas recentemente. Dados da lista de tabu não são usados para construir novas soluções. Além disso, os algoritmos greedy freqüentemente podem empregar uma estratégia chamada pesquisa de estabilização. Quando um algoritmo greedy é possível melhorar a sua solução atual, uma pesquisa de estabilização produz uma nova solução sem passar para trás, como o descarte de um nó no problema clique máximo. Apresentarei esses tabu interessante e úteis e técnicas de estabilidade em uma coluna futura.

Dr. James McCaffrey trabalha para a Volt Information Sciences Inc., onde gerencia o treinamento técnico para engenheiros de software, trabalhando com a Microsoft em Redmond, Wash, campus. Ele trabalhou em vários produtos da Microsoft, como Internet Explorer e MSN Search. Dr. McCaffrey é autor de ".NET Test Automation Recipes"(Apress, 2006) e pode ser contatado pelo jammc@microsoft.com.

Graças aos seguintes especialistas técnicos para revisão deste artigo: Paul Koch, Dan Liebling, Thompson Loomis de Ana Maria e Shane Williams