Il presente articolo è stato tradotto automaticamente.

Esecuzione di test

Algoritmi misteriosi e clique massima

James McCaffrey

Scaricare il codice di esempio

Nell'articolo di questo mese, ti presento una soluzione avanzata per il problema di massima cricca del grafico.La soluzione utilizza ciò che è chiamato un algoritmo di tabù, e verrà illustrato come progettare e testare questi algoritmi.L'idea del problema cricca massima è di trovare il più grande gruppo di nodi in un grafo che sono tutti collegati l'uno a altro.Date un'occhiata al grafo semplice nella figura 1.Il grafico è nove nodi e 13 bordi.Il grafico è acustica (non ci sono alcuna priorità associate con i bordi) e grafo (tutti i bordi sono bidirezionale).Nodi 2, 4 e 5 formano una cricca di tre dimensioni.La cricca di massima è che il nodo impostato 0, 1, 3 e 4, che forma una cricca di taglia quattro.

 

 

Nella figura 1 grafico per un algoritmo Tabu massimo cricca

Il problema di massima cricca è interessante per diverse ragioni.Anche se non è evidente dal grafico semplice in Figura 1, il problema della cricca massimo è uno dei più impegnativi in informatica.Origina in molti importanti problemi pratici, quali l'analisi delle reti sociali comunicazione, dove i nodi rappresentano persone e bordi rappresentano i messaggi o le relazioni.E il problema utilizza tecniche come algoritmi avidi e algoritmi di tabù, che sono importanti avanzate tecniche di programmazione.Avere una soluzione al problema massimo cricca nella vostra biblioteca personale può essere uno strumento utile e pratico, e comprendere l'algoritmo utilizzato può aggiungere nuove tecniche per insieme di abilità.

Questa è la terza colonna in una serie che usi il problema di massima cricca per illustrare la codifica avanzata e prove tecniche, ma questa colonna può essere letta senza riferimento diretto ai due precedenti.Nel mio articolo di ottobre, "Grafico strutture e massimo cricca" (msdn.microsoft.com/magazine/hh456397), ho descritto come codificare una struttura di dati efficiente per contenere una struttura di dati del grafico in memoria.Nel mio articolo di novembre, "Avidi algoritmi e massimo cricca" (msdn.microsoft.com/magazine/hh547104), ho descritto come un algoritmo relativamente semplice può essere utilizzato per trovare una soluzione al problema difficile cricca di massima.

In termini informali, un algoritmo greedy è un algoritmo che inizia con una soluzione semplice, incompleta per un problema difficile e iterativamente cerca quindi il modo migliore per migliorare la soluzione.Questo processo viene ripetuto fino a raggiunta una condizione di arresto.Come­mai, avidi algoritmi in genere hanno un punto debole: Che verrà ripetutamente generano la stessa soluzione più e più volte.Tabu algoritmi sono progettati per affrontare questa debolezza.Il tabù della parola, a volte scritto tabù, mezzi proibiti.In termini semplici, tabu algoritmi gestire un elenco di dati proibiti.La parte di elaborazione dell'algoritmo non è consentita utilizzare tabu dati fino a quando alcuni vietare il tempo sono passato.Semplici forme di utilizzo di algoritmi di tabu un fisso vietano il tempo.Tabu avanzati algoritmi adattano dinamicamente il tempo Impedisci mentre esegue l'algoritmo.

Figura 2 illustra le idee importanti di un algoritmo di tabu applicata al problema massimo cricca e vi mostra dove sto si diresse in questa colonna.

Figura 2 massimo Tabu cricca Demo Run

Ho un'applicazione console che comincia caricando in memoria il grafico corrispondente a quella indicata Figura 1.Il file utilizza un formato di file grafico standard chiamato DIMACS.Progettazione e una struttura di dati del grafico efficiente di codifica è un problema significativo in sé.Ho spiegato il codice di struttura di dati grafico nel mio articolo di ottobre.

L'algoritmo inizia selezionando un singolo nodo a caso e l'inizializzazione di una cricca con tale nodo.L'algoritmo poi iterativamente cerca di trovare e aggiungere il nodo migliore che aumenterà la dimensione della cricca di.Mi spiego cosa migliore nodo significa più tardi.Se l'algoritmo non riesce a trovare un nodo da aggiungere, tenta di individuare il nodo migliore per eliminare dalla cricca.Dietro le quinte, l'algoritmo ricorda l'ultima volta che ogni nodo è stato spostato nella cricca di soluzione corrente o spostato dalla cricca.L'algoritmo utilizza queste informazioni per vietare l'aggiunta o cadere recentemente utilizzato i nodi per un certo periodo di tempo.Questa è la parte di tabù dell'algoritmo.

L'algoritmo si riavvia ogni tanto quando nessun progressi compiuti nella ricerca di una migliore cricca (più grande).L'algoritmo archivia in silenzio le soluzioni (cricche) ha visto in precedenza.L'algoritmo utilizza tali informazioni di storia di soluzione di adattarsi dinamicamente il tempo Impedisci.Se l'algoritmo mantiene le stesse soluzioni, aumenta il tempo di Impedisci di scoraggiare utilizzati di recente i nodi possano essere utilizzati.Se l'algoritmo non vede le stesse soluzioni, diminuisce il tempo di Impedisci quindi non c'è una piscina più grande dei nodi da cui scegliere.Questa è la parte adattiva dell'algoritmo tabu.

Nella maggior parte delle situazioni in cui viene utilizzato un algoritmo greedy, la soluzione ottimale non è nota, così una o più condizioni di arresto devono essere specificate.Quando l'algoritmo colpisce una condizione di arresto, viene visualizzata la migliore soluzione trovata.

Nelle sezioni che seguono, I'll walk attraverso il codice che ha prodotto lo screenshot in Figura 2.Il codice sorgente completo è disponibile presso code.msdn.microsoft.com/mag201112TestRun.Questa colonna si presuppone la abilità di programmazione di livello intermedio con una lingua della famiglia c o Visual Basic.Linguaggio di NET.Io uso c#, ma che ho scritto il codice in modo che sarete in grado di refactoring in un'altra lingua come F # o Python senza troppe difficoltà se si desidera.

Struttura complessiva del programma

La struttura complessiva del programma mostrato in Figura 2 è presentato in Figura 3.Ho deciso di inserire tutto il codice in un'applicazione unica console utilizzando metodi statici per la semplicità, ma si potrebbe desiderare di modulare le parti del codice in librerie di classi e di utilizzare un approccio orientato agli oggetti.Il programma è meno complicato di quanto potrebbe sospettare guardando a Figura 3 perché la maggior parte dei metodi sono metodi di supporto breve.

Struttura del programma complessivo 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

Il programma ha due classi di alto livello, e ciascuno di tali classi ha una sottoclasse di supporto. Classe TabuMaxCliqueProgram contiene il metodo Main e ogni logica di algoritmo, insieme con la sottoclasse CliqueInfo, che viene utilizzato per mantenere una storia di soluzioni precedentemente visto cricca. MyGraph classe incapsula una rappresentazione grafico efficiente e contiene la sottoclasse BitMatrix, che viene utilizzato per memorizzare le informazioni di adiacenza nodo in forma condensata. Un oggetto Random di ambito classe denominato casuale viene utilizzato per inizializzare la cricca a un nodo casuale e per rompere i legami quando ci sono più nodi migliori di aggiungere o eliminare.

Con alcune dichiarazioni WriteLine e try-catch codice rimosso, il metodo principale è:

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

Il grafico viene rappresentato come un oggetto MyGraph definito dal programma. Il grafico viene caricato da un file di testo esterni che utilizza il formato di file DIMACS. Il metodo principale di MyGraph è AreAdjacent, che restituisce true se due nodi sono collegati. Ho impostato maxTime a 50 iterazioni per stabilire una condizione di assoluta di arresto per l'algoritmo greedy. Questo è un piccolo artificialmente. In un problema reale massima cricca, il tempo massimo è tipicamente nella gamma da 1.000 a 100.000. Ho impostato la dimensione targetClique per stabilire una seconda condizione di arresto; Se non viene trovata una cricca che ha lo stesso numero di nodi, come ci sono nel grafico, la cricca di massima deve sono stata trovata. La maggior parte del lavoro avviene mediante il metodo FindMaxClique, che utilizza un algoritmo di tabu avidi, adattivo per cercare la cricca del più grande possibile. Il metodo di supporto ListAsString crea semplicemente una rappresentazione di stringa di un elenco di <int> oggetto.

Il metodo FindMaxClique

Il metodo FindMaxClique chiama diversi metodi di supporto, che descriverò poco. In pseudocodice ad alto livello, l'algoritmo di FindMaxClique è data Figura 4. Lo pseudocodice lascia fuori diversi dettagli importanti per chiarezza, ma presenta i punti principali dell'algoritmo.

Figura 4 algoritmo adattivo Tabu massimo cricca

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

L'oggetto cricca locale è la cricca di soluzione corrente. Viene creata un'istanza dell'oggetto casuale con un valore di inizializzazione arbitrario di 1. La variabile di tempo è il contatore per ciclo di elaborazione principale dell'algoritmo. Le variabili timeBestClique e timeRestart vengono utilizzate per determinare se c'è stata una mancanza di progressi così l'algoritmo può riavviare stesso. Argomento successivo:

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

Il periodo Impedisci viene inizializzato su 1. Ciò significa che, inizialmente, almeno — dopo un nodo è stato utilizzato dall'algoritmo, non può essere utilizzato per un'iterazione di tempo. Se avevo usato un valore pari a 0, l'effetto sarebbe stato a non avere vietare il tempo a tutti. La maggior parte gli algoritmi di tabu utilizzano un valore fisso per la volta Impedisci, ma il problema di questo approccio è che la ricerca ha dimostrato che il miglior valore per un periodo di tempo fisso Impedisci varia da un problema al problema. L'approccio adattivo vi presento aggiornamenti il tempo Impedisci mentre l'algoritmo viene eseguito, basato sulla storia di precedenti soluzioni. Io chiamo questo tabù adattivo di tecnica, ma alcuni documenti di ricerca chiamano la tecnica reattiva o dinamico.

La matrice di lastMoved viene utilizzata per determinare se un nodo è consentito o vietato in un dato momento. L'indice della matrice rappresenta un nodo, e il corrispondente valore di matrice è il tempo che il nodo è stato spostato ultima (aggiunto o eliminato). Utilizzando la matrice lastMoved, eliminare la necessità di creare in modo esplicito un elenco di nodi consentiti (o, equivalentemente, vietato nodi). Inizializzo tutte le cellule di lastMoved a int.MinValue così più tardi è possibile determinare se un nodo non è mai stato utilizzato.

L'oggetto Hashtable storia contiene un insieme di cricche soluzione visto in precedenza. Ogni elemento nella tabella hash è un oggetto CliqueInfo che descriverò in dettaglio più avanti. Potrei hai utilizzato un oggetto dizionario generico anziché l'oggetto Hashtable non generici. FindMaxClique continua:

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

Inizializzo la cricca di soluzione corrente a un nodo casuale dal grafico. Creare un elenco di bestClique per tenere traccia della soluzione migliore (più grande) cricca trovata dall'algoritmo. Successiva è:

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

Il metodo MakePossibleAdd crea un elenco di tutti i nodi che possono essere aggiunti per la cricca di corrente per aumentare la dimensione della cricca di 1. In altre parole, il metodo crea un elenco di nodi che non sono nella cricca, ma sono connessi a ogni nodo nella cricca. Questo elenco di possibleAdd potrebbe avere un conteggio di 0 o potrebbe contenere nodi proibiti. MakePossibleAdd chiama il metodo di supporto FormsALargerClique.

Il metodo MakeOneMissing crea un elenco di tutti i nodi che sono collegati a tutti, ma esattamente uno dei nodi nella cricca di corrente. Non è ovvio, ma si scopre che il mantenimento di tale elenco crea un modo intelligente per determinare quale nodo nella corrente cricca è il nodo migliore di cadere, come spiegherò più tardi. Inizia il ciclo di elaborazione principale:

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

Il ciclo di elaborazione principale terminerà quando viene raggiunto il numero massimo di iterazioni o se viene trovata una soluzione migliore con la dimensione di cricca di destinazione. Utilizzare la variabile cliqueChanged per controllare la ramificazione logica tra l'aggiunta e l'eliminazione di nodi, come si vedrà. La logica per aggiungere un nodo consentito è mostrata in Figura 5.

Figura 5 la logica per aggiungere un nodo consentito

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

L'algoritmo di verifica per vedere se ci sono eventuali nodi che aumenteranno la dimensione della cricca del corrente. Se così, il metodo SelectAllowedNodes crea un elenco di nodi che sono ammessi — che è, non tabu — dall'elenco dei nodi che possono essere aggiunti.

La linea di chiave in SelectAllowedNodes è:

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

Il currNode è uno dei nodi nell'elenco possibleAdd. La logica controlla se abbastanza tempo è trascorso dal momento che il nodo ultima è stato utilizzato in modo che il nodo è passato il periodo Impedisci. Se è così, il nodo viene aggiunto all'elenco dei nodi allowedAdd.

Ora, se ci sono eventuali nodi che sono ammessi e aumenteranno la dimensione della cricca di, metodo GetNodeToAdd determina il nodo migliore per aggiungere la cricca. Il nodo migliore è il nodo dall'elenco allowedAdd che è più collegato ai nodi nell'elenco possibleAdd. L'idea è che si desidera aggiungere un nodo che vi darà il più probabilità di trovare un nodo da aggiungere nella prossima iterazione dell'algoritmo. Ci potrebbe essere più nodi nell'elenco allowedAdd che sono legati come più connesso ai nodi in possibleAdd. Se è così, uno dei nodi legati viene selezionato a caso. Dopo aver aggiunto il nodo migliore, la soluzione attuale cricca viene ordinata per motivi che spiegherò più tardi. Il codice di cadere un nodo è:

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

Se l'algoritmo non è possibile aggiungere un nodo, tenta di eliminare un nodo consentito nella speranza che aspettarne produrrà una soluzione che consentirà un nuovo nodo da aggiungere nella prossima iterazione. Elenco dei nodi nella cricca di corrente viene filtrata dal metodo SelectAllowedNodes per ottenere i nodi che non sono tabù. il GetNodeToDrop prende il meglio di questi nodi a goccia utilizzando l'elenco di nodi di oneMissing.

L'idea è di cadere il nodo consentito nella cricca di corrente, che si tradurrà nel più grande aumento nell'elenco dei nodi possibleAdd. Un modo per farlo è di testare ogni nodo nell'elenco consentito in realtà rimuovendolo la cricca di corrente e quindi calcolando le dimensioni dell'elenco risultante possibleAdd. Ma c'è un approccio molto più efficiente che utilizza un elenco di nodi che sono collegati a tutti, ma esattamente uno dei nodi nella cricca di corrente. Utilizzando l'elenco di oneMissing di nodi, l'elenco può essere utilizzato come segue. Scansione attraverso ogni nodo nei nodi cricca consentiti e contare quanti nodi nell'elenco oneMissing sono notconnected al nodo cricca. Il nodo dell'elenco consentiti cricca che è almeno collegato ai nodi nella oneMissing elenco è il nodo migliore a goccia. Dopo aver abbandonato questo nodo collegato a meno, tutti i nodi nella lista oneMissing che non erano collegati al nodo caduto ora saranno completamente collegati ai nodi rimanenti nella cricca e quindi diventano nuovi nodi possibleAdd.

A questo punto nella logica, non potrebbe essere possibile aggiungere un nodo consentito o cadere un nodo consentito. Per scollare stessa, l'algoritmo scende un nodo casuale dalla cricca di corrente:

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

Successivamente, i controlli di algoritmo per vedere se c'è stata una mancanza di progressi e, in caso affermativo, viene riavviato se stessa:

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

La variabile di riavvio è il numero di iterazioni per consentire dove non esiste alcun miglioramento o dall'ultimo riavvio. Qui io uso un valore pari a 100 volte la dimensione della migliore soluzione corrente. Il valore da utilizzare per l'intervallo di riavvio non è ben conosciuto e si potrebbe voler cercare alternative. (Ho usato il valore fittizio 2 per produrre ulteriori riavvii per lo screenshot in Figura 2). Il valore che io uso ha funzionato bene per me, in pratica, tuttavia. Se c'è un riavvio, l'algoritmo reimposta il tempo Impedisci e cancella la tabella di hash storia holding cricche di soluzione che sono stati visti. Si noti che l'algoritmo non è ancora aggiornato la tabella hash di storia. Il codice di riavvio non, tuttavia, reimposta la matrice di lastVisited, che memorizza informazioni su quando i nodi ultima sono stati aggiunti o è sceso dalla cricca di soluzione. Successiva è:

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

L'algoritmo tenta di inizializzare nuovamente la cricca di soluzione con un nodo che non è mai stato utilizzato prima. Se ci sono molti nodi inutilizzati, uno viene selezionato a caso. Se non ci sono nessun nodo inutilizzato, viene selezionato un nodo casuale. Invece di utilizzare un nodo casuale, inesplorata alternativa, è possibile selezionare il nodo che meno recentemente è stato spostato. Il codice di riavvio termina con il seguente:

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

Il ciclo di elaborazione principale e FindMaxClique wrap up come segue:

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

Le liste di possibleAdd e oneMissing vengono rigenerate. Un'alternativa è di mantenere strutture dati ausiliari e aggiornare questi due elenchi invece di loro ricreare da zero. Il metodo UpdateProhibitPeriod è il componente chiave della parte adattiva dell'algoritmo tabu e descriverò poco.

Ricordando precedenti soluzioni

UpdateProhibitPeriod metodo utilizza una tabella hash di soluzioni precedentemente visti per dinamicamente aumentare o diminuire il tempo di Impedisci. Ricordiamo che una soluzione è una cricca che è un elenco di <int> di nodi che sono tutti collegati l'uno a altro. Ma ho anche bisogno di memorizzare il tempo quando una soluzione è stata l'ultima volta. Pertanto, incapsulare una soluzione cricca e l'ultima volta è stato visto in una classe di CliqueInfo come elencato in Figura 6.

Figura 6 la classe di 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;
  }
}

Perché un elemento CliqueInfo verrà aggiunto all'oggetto Hashtable storia soluzione, ho bisogno di una funzione di hash di GetHashCode personalizzata. Scrivere funzioni hash personalizzato è sorprendentemente difficile, e una discussione approfondita di tutte le questioni richiederebbe un'intera colonna. In questa situazione, io uso il più semplice — ma non il più efficiente — approccio. Creo una rappresentazione di stringa dei nodi nel campo cricca, separato da spazi e quindi utilizzare il String.GetHashCode incorporato. Ad esempio, se una cricca contenute nodi {3 5 8}, generare "3 5 8" (con uno spazio finale) e quindi generare un codice hash da quella stringa. Ricordiamo che cricche sono sempre mantenuti ordinati, quindi non sarebbe possibile avere una cricca {3 5 8} e un'altra cricca {8 3 5}. Inserire spazi tra i nodi in modo che della cricca {3 5 8} si distingue da cricca {3 58}.

L'aggiornamento il periodo di vietare

Metodo UpdateProhibitPeriod adattivo aumenta o diminuisce il tempo di Impedisci basato su soluzioni precedentemente visto cricca. Il metodo inizia:

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

Il metodo restituirà un tempo Impedisci che potrebbe essere lo stesso tempo Impedisci corrente. Un oggetto CliqueInfo tenendo la cricca corrente e l'ora corrente viene creata un'istanza, come illustrato di seguito:

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

Il codice controlla per vedere se la soluzione attuale cricca, sotto forma di un oggetto CliqueInfo, è stato visto prima — è la cricca nella tabella hash storia? Se la cricca di corrente è stato visto prima, l'algoritmo calcola quanto tempo è stato visto era visto la cricca. Se questo intervallo è abbastanza breve, il tempo di Impedisci viene incrementato (soggetto a un limite massimo). L'idea è che, poiché non è stata molto lungo, poiché la cricca di corrente è stato visto, l'algoritmo sta generando soluzioni duplicati. Se il tempo Impedisci è aumentato, non ci sarà più nodi tabu e quindi meno permesso nodi, riducendo le possibilità di generare soluzioni cricca duplicati. Se la soluzione attuale cricca non è stato visto prima, viene aggiunto alla tabella hash storia.

L'intervallo "short abbastanza" è due volte il numero di nodi nel grafico, meno uno. Questo è usato per determinare quando incrementare il tempo Impedisci. Il miglior valore per utilizzare qui è un'altra questione aperta nella ricerca della massima cricca. Il "limite" per la volta Impedisci è due volte la dimensione della soluzione corrente meglio conosciuta. Il miglior valore limite superiore è, come si può intuire probabilmente ormai, un'altra domanda di ricerca aperto.

A questo punto, sia la cricca di corrente non è stato visto prima, o la cricca è stato visto prima ma l'intervallo per incrementare il tempo Impedisci necessaria non era abbastanza piccolo. Così l'algoritmo ora controlla per vedere se il periodo Impedisci può essere decrementato, che diminuire il numero di nodi tabu e aumentare il numero di nodi consentiti, che a sua volta dà l'algoritmo più nodi di aggiungere o eliminare:

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

Piuttosto che esplicitamente controllare per vedere se è stato un tempo "relativamente lungo" la cricca di corrente è stato visto, l'algoritmo indirettamente controlla quanto tempo è stato poiché la cricca di corrente è stato visto esaminando il tempo quando il periodo di Impedisci ultima è stato modificato. Ancora una volta, il miglior valore per "relativamente lungo" chiaramente non è compreso. Io uso un valore di 10 volte la dimensione della migliore soluzione corrente. Si noti che il tempo Impedisci non può scendere sotto 1.

Ulteriori ricerche

Risultati di ricerca sul problema massimo cricca suggeriscono che un approccio avido con una caratteristica adattiva tabu dà i migliori risultati complessivi quando sia le prestazioni e la qualità della soluzione sono presi in considerazione. DIMACS è un'organizzazione di ricerca che ha creato una serie di problemi di difficile grafico cricca di riferimento. Ho eseguito il codice presentato qui contro uno particolarmente difficile problema DIMACS (C2000.9) e il codice rapidamente (in meno di due secondi) trovato una cricca con dimensioni 76 all'interno di 1,5 per cento delle dimensioni della soluzione più conosciuta di 77.

In diversi punti in questa colonna, ho accennato risultati delle ricerche sul problema massimo cricca. Se siete interessati a questa ricerca, raccomando cercate sul Web per pubblicazioni accademiche, scritto dal seguente: R. Mezzanotte et al., w. Pullan et al. e k. Katayama et al. Documenti diversi da questi tre autori ed i loro colleghi erano miei riferimenti primari.

Una zona inesplorata promettente per l'algoritmo di massima cricca presentato qui consiste nell'incorporare qualche forma di quello che viene chiamato ricerca altopiano. Ricordiamo che l'algoritmo di massima cricca prima tenta di aggiungere un nodo non tabu alla soluzione corrente cricca. Quindi, se non è possibile, l'algoritmo elimina un nodo dalla soluzione attuale cricca. L'idea di ricerca altopiano è quello di trovare un nodo nella soluzione corrente cricca che può essere scambiata con un nodo non nella cricca. Anche se questo non aumenta le dimensioni della cricca corrente, non diminuire la dimensione della cricca, di in uno o l'altro.

Dr. James McCaffrey lavora per Volt Information Sciences Inc., dove gestisce la formazione tecnica per gli ingegneri software della Microsoft di Redmond, Washington, campus. Ha lavorato su diversi prodotti Microsoft, tra cui Internet Explorer e MSN Search. Dr. McCaffrey è l'autore di ".NET Test Automation Recipes"(Apress, 2006) e può essere raggiunto a jammc@microsoft.com.

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