Il presente articolo è stato tradotto automaticamente.

Esecuzione di test

Algoritmi greedy e clique massima

James McCaffrey

Scaricare il codice di esempio

Nella colonna di questo mese presenterò una soluzione al problema di massima clique del grafico.La soluzione utilizza quello che ha definito un algoritmo generico e viene spiegato come progettare e testare questi algoritmi.L'idea del problema clique massima è di trovare il gruppo più grande di nodi in un grafico che si è connessi a un altro.Esaminiamo il grafico semplice in nella figura 1.Il grafico dispone di nove nodi e 13 spigoli.Il grafico è non pesato (non esistono alcuna priorità associate con i bordi) e undirected (tutti gli spigoli sono bidirezionali).I nodi 2, 4 e 5 formano un clique di dimensioni 3.La massima clique è che 0, 1, 3 e 4, che formano un clique di dimensioni quattro set di nodi.

 

Figura 1 grafico per un algoritmo generico massimo Clique

Il problema clique massima è interessante per diverse ragioni.Sebbene non sia evidente che il grafico semplice in nella figura 1, il problema clique massima è uno dei più complessi in informatica.Questo si verifica in molte applicazioni importanti quali l'analisi di comunicazione di rete sociale, in cui i nodi rappresentano persone e gli spigoli un messaggio o una relazione.E il problema clique massima presta per soluzione da un algoritmo generico, che è una tecnica fondamentale in informatica.

In termini di informale, un algoritmo generico è un algoritmo che inizia con una soluzione semplice, incompleta per un problema difficile e iterativo cerca quindi il modo migliore per migliorare la soluzione.Il processo viene ripetuto fino a quando non viene raggiunta una condizione di interruzione.Figura 2 illustra i concetti importanti del problema massimo clique, nonché si in cui potrò in questo articolo.

Figura 2 esecuzione massimo generici Clique Demo

Dispone di un'applicazione console, che inizia con il caricamento in memoria, il grafico che corrisponde a quella mostrata nella nella figura 1.Progettazione e la codifica di una struttura di dati del grafico efficiente è un problema significativo di per sé.Il codice di struttura dati grafico è stato spiegato nel mio ultimo articolo (msdn.microsoft.com/magazine/hh456397).Innanzitutto, l'algoritmo seleziona un singolo nodo in modo casuale, in questo nodo case 2 e consente di inizializzare una clique con tale nodo.Successivamente, l'algoritmo di ricerca per il nodo migliore aggiungere la clique.Se si fa riferimento a nella figura 1, si vedrà che esistono solo due nodi, 4 e 5, che costituiscono un clique di dimensioni maggiori.Spiegherò il nodo migliore significato al più presto.

L'algoritmo seleziona e aggiunge il nodo 4 per il clique in modo che il clique è ora {2, 4}.A questo punto, è presente un solo nodo nel grafico, 5, che consentirà di aumentare le dimensioni del clique, in modo che l'algoritmo Seleziona nodo 5 e lo aggiunge al clique.Esistono nodi disponibili che aumenteranno la dimensione del clique.L'algoritmo Elimina il nodo migliore da clique nella speranza che è possibile aggiungere un nuovo nodo diverso grado di abilitare lo stato di avanzamento.Anche in questo caso spiegare quale mezzo di "migliore" al più presto.L'algoritmo scende nodo 4 dal clique.Come si può vedere dal grafico, non vi è alcun modo per progredire.Questa situazione è comune con gli algoritmi generici, in modo che deve esistere un modo per sfruttare al meglio soluzioni ciechi.

È l'algoritmo di verifica come tempo trascorso dal momento che sono stati realizzati progressi, vale a dire che è stato trovato un clique con una dimensione maggiore.Dopo un determinato periodo di tempo con avanzamento non si riavvia l'algoritmo stesso.Il clique è deselezionata.Questa volta l'algoritmo sceglie in modo casuale il nodo 3 come nodo iniziale.Utilizzando lo stesso processo iterativo per trovare il nodo migliore per aggiungere o eliminare, infine l'algoritmo rileva che la massima clique di {0, 1, 3, 4}.Nella maggior parte dei problemi in cui vengono utilizzati algoritmi generici, non è nota la soluzione ottimale, in modo che l'algoritmo continua fino a quando non vengono soddisfatte alcune condizioni di arresto.In questo caso, l'algoritmo è configurato per arrestare dopo 20 iterazioni.A questo punto, viene visualizzata la migliore clique trovato.

Nelle sezioni che seguono, si prenderanno in considerazione è tramite il codice che ha prodotto la schermata in nella figura 2.Il codice sorgente completo è disponibile all'indirizzo code.msdn.microsoft.com/mag201110TestRun (in questa colonna viene utilizzato lo stesso codice rispetto al mese).In questo articolo si presuppone esperienza di programmazione di livello intermedio con una lingua della famiglia c o di Visual Basic.NET language.Utilizzare C#, ma ho scritto il codice in modo che si sarà in grado di refactor per un'altra lingua senza eccessiva difficoltà se lo si desidera.

Struttura generale del programma

La struttura complessiva del programma indicato nella nella figura 2 presentate in nella figura 3.Il programma dispone di dipendenze sugli spazi dei nomi System, System.Collections.Generic (un clique viene rappresentato come tipo di elenco <int>), System. IO (per il caricamento del grafico di origine da un file di testo) e System. Collections (la classe di MyGraph definito dal programma utilizza la classe BitArray).Rinominare la classe principale dal programma di Visual Studio generati dal modello di GreedyMaxCliqueProgram per motivi di chiarezza.Utilizzare un oggetto di ambito della classe Random denominato "casuali" per inizializzare e reimpostare un clique a un nodo casuale e interruzione ties quando è presente più di un nodo migliore per aggiungere o eliminare.

Figura 3 struttura del programma generale

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

Il grafico è rappresentato come un oggetto di MyGraph definito dal programma. Il grafico viene caricato da un file di testo esterno, viene utilizzato un formato di file standard denominato DIMACS. Il metodo chiave MyGraph è AreAdjacent, che restituisce true se due nodi sono collegati. Ho impostato maxTime su 20 per impostare una condizione di interruzione assoluto per l'algoritmo generico. È possibile impostare targetCliqueSize per stabilire una seconda condizione di interruzione; Se un clique viene rilevato lo stesso numero di nodi sono presenti nel grafico, è necessario il massimo clique sono stati trovati.

Il metodo FindMaxClique

Tutto il lavoro viene eseguita tramite il metodo FindMaxClique, che utilizza un algoritmo generico per cercare la clique più grande possibile. FindMaxClique chiama diversi metodi di supporto, descriverò in dettaglio. Struttura di programma utilizzando i metodi statici, ma è possibile che si desideri il refactoring del codice che qui riportate per un approccio completamente orientate agli oggetti. Il metodo FindMaxClique scorre fino a quando una delle condizioni di due arresto viene soddisfatta e quindi restituisce il migliore clique trovato. La definizione del programma include una classe di MyGraph incorporata, è stato oggetto di un articolo del mese scorso.

In pseudocodice di alto livello, l'algoritmo di 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

Inizia la definizione di metodo di 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;
...

L'oggetto clique locale è il clique corrente. Viene creata l'istanza dell'oggetto Random utilizzando un valore di inizializzazione arbitrario di 1. La variabile di tempo è una variabile contatore di ciclo; Poiché è discreto, un buon nome alternativo sarebbe "tick". Tenere traccia l'ora quando è stato trovato il clique migliore corrente e l'ora dell'ultimo riavvio per il controllo quando si verifica il riavvio. Assegnare valori fittizi-1 per le variabili per il nodo componente e il nodo di discesa:

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

Il metodo Random.Next(x,y) restituisce un valore maggiore o uguale a x e minore di y. Impostazione x = 0 e y = NumberNodes, viene visualizzato un nodo casuale da 0 a 8 per il grafico di esempio:

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

L'elenco di bestClique viene utilizzato per tenere traccia di una copia del più grande clique rilevati durante la ricerca dell'algoritmo. Utilizzare il metodo AddRange utile copiare gli elementi della corrente clique in bestClique. La variabile bestSize viene utilizzata per motivi di praticità. Il timeBestClique viene utilizzata per determinare se si verifica un riavvio dell'algoritmo:

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

Il metodo di supporto MakePossibleAdd esamina la clique corrente e crea un elenco di tutti i nodi che possono essere aggiunti a clique per aumentare la dimensione del clique da uno. Questo elenco è l'origine dei candidati per il nodo migliore per aggiungere la clique. Il metodo di supporto MakeOneMissing è piuttosto difficile. Il metodo crea un elenco di tutti i nodi sono collegati a tutti tranne uno nodo il clique corrente. Come si vedrà, questo elenco di oneMissing viene utilizzato per determinare il nodo migliore per eliminare da un clique. Ora di inizio del ciclo di elaborazione principale:

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

Come spiegato in precedenza, gli algoritmi generici in genere è necessario uno o più condizioni di arresto. Qui il ciclo termina se viene superato il numero massimo di iterazioni o le dimensioni del clique corrente soddisfano una dimensione di destinazione. La variabile cliqueChanged viene utilizzata per controllare la logica di diramazione tra l'aggiunta di nodi e l'eliminazione di nodi. Potrei aver omesso di questa variabile e utilizzato un se..Else struttura anziché distinte di controllo se..quindi istruzioni, ma in questo caso, l'utilizzo di una variabile di controllo diramazione conduce al codice è più facile da leggere e modificare, a mio parere:

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

È necessario controllare per verificare che sia presente almeno un nodo che può essere aggiunti per la clique e quindi chiamarla il metodo di supporto GetNodeToAdd. Questo metodo analizza l'elenco dei nodi presenti nell'elenco di possibleAdd e restituisce il nodo migliore per aggiungere (spiegazione controlli promessa di "migliore" verrà visualizzata quando descriverò GetNodeToAdd). Questo nodo viene aggiunto il clique corrente. A questo punto ordinare clique, poiché più avanti nell'algoritmo è necessario eseguire la ricerca di clique e se il clique è ordinato, è possibile utilizzare una rapida ricerca binaria invece di una ricerca lineare. Il nuovo clique viene controllato per verificare se è preferibile a quello della corrente clique migliore.

Quindi viene:

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 non può aumentare la dimensione della corrente clique, l'algoritmo tenta di rilasciare un nodo da al clique. Il metodo di supporto GetNodeToDrop seleziona il nodo migliore per eliminare dal 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
...

A questo punto, l'algoritmo di verifica se è stata una mancanza di avanzamento. La variabile di riavvio determina il tempo di attesa prima del riavvio. Qui è possibile utilizzare un valore pari a due volte la dimensione della corrente clique migliore. Ricerche sul valore massimo clique, il valore ottimale per il riavvio è ancora una domanda a risposta libera. Il valore di che utilizzare in questo caso si basa su esperimenti che ho ho eseguito con numerosi problemi di grafico di benchmark. Riavviare il computer si verifica se è stata la mancanza dei progressi realizzati nella ricerca di una nuova soluzione migliore o se è stato relativamente molto tempo dall'ultimo riavvio. Se viene effettuato un riavvio, l'algoritmo Svuota il clique corrente e quindi si seleziona un nodo casuale da tutti i nodi nel grafico. Si noti che questo è un approccio greggio; Se si fa riferimento nuovamente la demo di eseguire in nella figura 2, si noterà che l'ultimo riavvio prelevato un nodo iniziale che era già stato utilizzato come primo nodo di sementi:

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

Il metodo FindMaxClique calcola partendo da zero, gli elenchi di possibleAdd e oneMissing in base al nuovo clique. Quando termina il ciclo di elaborazione principale, il metodo restituisce la migliore clique trovato.

Aggiungere il nodo migliore

Esistono due passaggi per determinare il nodo migliore per aggiungere la clique corrente. In primo luogo, è necessario un elenco di tutti i nodi che aumenteranno la dimensione del clique corrente. In secondo luogo, è necessario un modo per determinare quale di questi nodi è il nodo migliore:

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

Il metodo MakePossibleAdd di scansioni eseguite tramite ogni nodo nel grafico. Se si è esaminato il nodo è connesso a tutti i nodi del clique corrente determinata dal supporto FormsALargerClique, quindi il nodo in corso l'analisi è un nodo "add" possibili e viene aggiunto l'elenco dei risultati. Si noti il risultato potrebbe essere un elenco vuoto, ma non sarà mai 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;
}

Il metodo FormsALargerClique consente di confrontare un nodo contro tutti i nodi del clique corrente. Se il nodo candidato non è adiacente a anche uno dei nodi del clique, la corrente clique Impossibile aggiungere il nodo candidato. Si noti quanto AreAdjacent restituisce false quando un nodo viene confrontato con se stesso, nodi di clique corrente non verranno aggiunti all'elenco dei nodi di possibleAdd.

L'idea principale determina il nodo migliore per aggiungere consiste nel selezionare un nodo dall'elenco di nodi possibleAdd che è la maggior parte dei connesso a tutti gli altri nodi nel set di possibleAdd. Un nodo che è connesso ad elevata consente di ottenere il più grande possibile nuovo elenco di nodi da aggiungere per l'iterazione successiva dell'algoritmo.

Quindi viene:

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

Il metodo GetNodeToAdd si presuppone che l'elenco di possibleAdd ha almeno un nodo. Se è presente esattamente un nodo, che deve essere il nodo migliore:

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

È possibile che diversi nodi nell'elenco possibleAdd legati con altri utenti come più connesso agli altri nodi nell'elenco. Ad esempio, si supponga che il grafico di analisi è il grafico riportato nella nella figura 1 e il clique corrente ha solo nodo 0. I nodi di possibleAdd sono {1, 3, 4}. Nodo 1 è connesso a due nodi in possibleAdd, e, in realtà, sono così nodi 3 e 4. Pertanto, un'analisi preliminare viene effettuata per determinare il numero massimo di connessioni disponibili:

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 volta che è noto il numero massimo di connessioni, l'algoritmo riesegue la scansione dell'elenco di possibleAdd e aggiunge ognuno dei nodi in possibleAdd con il numero massimo di connessioni per un elenco dei nodi candidati. Si noti che la scansione di doppia poteva essere eliminata utilizzando i dati ausiliari archivi per tenere traccia del numero di connessioni a ciascun nodo possibleAdd è:

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

A questo punto, l'elenco di candidati ha uno o più nodi migliori per aggiungere la clique. Si noti che candidati devono avere un conteggio di almeno uno perché si presuppone che l'elenco possibleAdd per avere un conteggio di almeno uno. L'algoritmo in modo casuale consente di selezionare uno dei nodi candidati e lo restituisce. Potrei avere inserire in un controllo per verificare se la dimensione dell'elenco candidati è esattamente uno e in tal caso, restituire il singolo nodo di candidati.

Eliminazione del nodo migliore

Per determinare il nodo migliore per eliminare dal clique corrente è un po' meno evidenti. L'idea è di rilasciare un nodo nel clique corrente comporterà l'aumento più grande nell'elenco dei nodi di possibleAdd.

Un modo per effettuare questa operazione consiste nella verifica di ogni nodo nel clique corrente venga effettivamente rimosso dal clique corrente e successivamente calcolando le dimensioni dell'elenco risultante di possibleAdd. Ma c'è un approccio molto più efficiente che utilizza un elenco di nodi che sono connessi a tutti tranne esattamente uno dei nodi di clique corrente. Se è presente un elenco di nodi oneMissing, l'elenco può essere utilizzata come segue: scorrere ciascun nodo della corrente clique e contare il numero di nodi nell'elenco oneMissing non è connessi al nodo clique. Il nodo nel clique corrente è connesso in meno per i nodi nell'elenco oneMissing sia il migliore per eliminare. Dopo l'eliminazione di questo nodo connesso al minimo, tutti i nodi presenti nell'elenco di oneMissing che non sono stati collegati al nodo ignorato verranno ora essere completamente connesso alla nodi rimanenti del clique, pertanto non sono più nuovi nodi di possibleAdd.

Viene presentato il metodo MakeOneMissing in nella figura 4. Il metodo esegue la scansione tramite ogni nodo nel grafico. L'idea è di contare il numero di nodi di clique è connessi al nodo corrente in corso l'analisi. Se il conteggio totale di nodi connessi è esattamente una minore la dimensione della corrente clique, quindi il nodo in corso l'analisi è un nodo oneMissing. Se il nodo corrente in corso l'analisi è inferiore al numero necessario di router adiacenti, il metodo provoca un corto circuito. Il metodo è necessario filtrare i nodi che sono già nel clique, dal momento in cui sono connessi al nodo tutti tranne uno nel proprio clique (vale a dire a se stessi). Poiché il clique corrente viene ordinato (dopo ogni aggiunta o il rilascio), una ricerca binaria può essere utilizzata invece di una ricerca lineare più lenta (vedere nella figura 4).

Figura 4 rendere l'elenco di nodi di 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;
}

Inizia il metodo GetNodeToDrop:

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

Il metodo presuppone che il clique corrente disponga di almeno un nodo. Se il clique corrente esiste un solo nodo, è l'unico nodo che può essere eliminato. Il metodo determina il numero massimo di nodi nell'elenco oneMissing che non sono connessi a qualsiasi nodo della clique corrente perché potrebbe essere più di un nodo nel clique conservabilità viene disconnesso all'elenco di 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 volta che è noto il numero massimo di disconnessioni, il metodo riesegue la scansione clique per trovare i nodi che non sono più disconnessi e verranno aggiunte ciascuna a un elenco di candidati. Come con il metodo di GetNodeToAdd GetNodeToDrop Impossibile evitare una nuova analisi mantenendo gli archivi dei dati supplementare:

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

Metodo GetNodeToDrop si conclude con la restituzione di un nodo selezionato casualmente dall'elenco dei nodi migliori per eliminare:

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

Considerazioni finali

Quanto efficaci sono algoritmi generici? Nonostante la presenza di loro relativa semplicità algoritmi generici hanno dimostrati molto efficace in molti scenari di problema. Tuttavia, l'efficacia può essere definito utilizzando diversi criteri, tra cui la velocità e la qualità della soluzione. È stato eseguito questo algoritmo contro diversi problemi di graph benchmark estremamente difficile gestiti dall'organizzazione di ricerche DIMACS e l'algoritmo è stato molto efficacia, in esecuzione in modo rapido e producendo cliques massima che erano in genere all'interno del 5% delle soluzioni più note.

Test generici algoritmi può risultare difficile. Oltre a tutte le normali tecniche, ad esempio unit test, test e così via condizione di contorno di test, e poiché gli algoritmi generici dispongono di soluzioni in grado di crescono nel tempo, un'efficacia strategia di test consiste nella scrittura di metodi di supporto iterativo verificare lo stato delle strutture di dati utilizzato dall'algoritmo. Ad esempio, durante il test dell'algoritmo clique massima presentato in questo articolo, ho scritto i metodi che consentono di verificare che la clique di corrente non durante alcun nodo duplicato, verificare alcun nodo nel clique corrente non è il corrente possibleAdd o oneMissing corrente sono elencati e così via.

L'algoritmo generico clique massima presentate in questo articolo può essere modificato per ottenere risultati migliori in diversi modi. Una tecnica comune per gli algoritmi più generici, consiste nell'aggiungere una feature di cosiddetti tabu. Gli algoritmi di tabu gestiscono un elenco di dati utilizzati di recente ed eventualmente un elenco di soluzioni visto di recente. I dati dell'elenco di tabu non viene utilizzati per la costruzione di nuove soluzioni. Inoltre, gli algoritmi generici possono spesso utilizzano una strategia di ricerca raggiunge una piattaforma. Quando un algoritmo generico non è in grado di migliorare la soluzione corrente, una ricerca di tale produce una nuova soluzione senza tornare alla precedente, ad esempio l'eliminazione di un nodo nel problema clique massima. In un prossimo articolo saranno descritti questi tabu utile e interessante e tecniche raggiunge una piattaforma.

Dr. James McCaffrey lavora per Volt Information Sciences Inc., dove gestisce la formazione tecnica degli ingegneri software Microsoft a Redmond, WA, campus. Si è occupato di diversi prodotti Microsoft, inclusi Internet Explorer e MSN Search. Dr. McCaffrey è l'autore di ".NET Test Automation Recipes"(Apress, 2006) e può essere contattato al jammc@microsoft.com.

Grazie per i seguenti esperti tecnici per la revisione di questo articolo: Paul Koch, Dan Liebling, Ann Loomis Thompson e Shane Williams