Dieser Artikel wurde maschinell übersetzt.

Testlauf

Tabu-Algorithmen und Maximum Clique

James McCaffrey

Im Artikel dieses Monats werde ich eine fortschrittliche Lösung für das Diagramm maximale Clique Problem vorlegen.Die Lösung verwendet was einen Tabu-Algorithmus genannt hat, und werde ich erläutern, wie zu entwerfen und testen diese Algorithmen.Die Idee des maximalen Clique Problems ist, finden die größte Gruppe von Knoten in einem Diagramm, die alle miteinander verbunden sind.Werfen Sie einen Blick auf die einfache Grafik in Abbildung 1.Das Diagramm verfügt über neun Knoten und 13 Kanten.Die Grafik ist nicht beruecksichtigt (es gibt keine Prioritäten zugeordnet die Kanten) und ungerichteten (alle Kanten sind bidirektional).Knoten 2, 4 und 5 bilden eine Clique von Größe drei.Die maximale Clique ist der Knoten 0, 1, 3 und 4, bildet eine Clique von Größe 4.

 

 

Abbildung 1: Grafik für ein Tabu Maximum Clique-Algorithmus

Das maximale Clique Problem ist aus mehreren Gründen interessant.Obwohl es nicht offensichtlich aus dem einfachen Diagramm in Abbildung 1, das maximale Clique Problem ist eine der größten Herausforderungen in der Informatik.Er entspringt in viele wichtige praktische Probleme, wie z. B. soziale Kommunikation Netzwerkanalyse, wo Knoten darstellen Menschen und Kanten Nachrichten oder Beziehungen darstellen.Und das Problem verwendet Techniken wie greedy-Algorithmen und Tabu Algorithmen, die wichtig sind fortgeschrittene Programmiertechniken.Eine Lösung für die maximale Clique Problem in Ihrer persönlichen Bibliothek kann sein ein nützliches praktische Werkzeug, und Verständnis des verwendete Algorithmus kann neue Techniken Ihre Fertigkeitssatz hinzufügen.

Dies ist die dritte Spalte in einer Reihe, dass verwendet das maximale Clique Problem darstellen, erweiterte codieren und testen Techniken, aber diese Spalte ohne direkten Bezug zu den beiden vorangegangenen gelesen werden kann.In meinem Artikel vom Oktober "Graph Strukturen und maximale Clique" (msdn.microsoft.com/magazine/hh456397), ich beschrieben, wie eine effiziente Datenstruktur für eine Graph Datenstruktur im Arbeitsspeicher code.In meinem Artikel vom November "Greedy-Algorithmen und maximale Clique" (msdn.microsoft.com/magazine/hh547104), ich beschrieben, wie ein relativ einfacher Algorithmus verwendet werden kann, um eine Lösung des Problems schwierig maximale Clique zu finden.

In informellen Begriffe ist ein gieriger Algorithmus einen Algorithmus, der beginnt mit einer einfachen, unvollständige Lösung eines schwierigen Problems und dann der beste Weg zur Verbesserung der Lösung iterativ sucht.Der Vorgang wird wiederholt, bis eine Bedingung beenden erreicht ist.Wie­, greedy-Algorithmen in der Regel schon eine Schwäche: sie werden wiederholt erzeugen die gleiche Lösung über und über.Tabu Algorithmen sollen mit dieser Schwäche befassen.Das Wort Tabu, buchstabiert manchmal Tabu, Mittel verboten.In einfachen Worten verwalten Tabu Algorithmen eine Liste der verbotenen Daten.Der Verarbeitung Teil des Algorithmus ist nicht zulässig, Tabu zu verwenden, die Daten bis einige Zeit verbieten verstrichen ist.Einfache Formen der Tabu Algorithmen verwenden eine feste verbieten Zeit.Erweiterte Tabu Algorithmen passen die verbieten Zeit dynamisch während der Algorithmus ausgeführt wird.

Abbildung 2 zeigt die wichtigen Ideen eines Tabu-Algorithmus auf die maximale Clique Problem angewendet und zeigt Ihnen, wohin ich bin in dieser Spalte.

Abbildung 2 Tabu Maximum Clique Demo ausführen

Ich habe eine Konsolenanwendung, die beginnt mit dem Laden in den Arbeitsspeicher der Grafik, die die einer angezeigt, Abbildung 1.Die Datei verwendet eine standard Grafik-Dateiformat namens California.Entwerfen und programmieren eine effiziente Graphstruktur-Datenstruktur ist ein bedeutendes Problem in selbst.Ich habe den Graph Datenzugriffscode in meinem Artikel vom Oktober erklärt.

Der Algorithmus beginnt, indem Sie einen einzelnen Knoten nach dem Zufallsprinzip und Initialisieren einer Clique mit diesem Knoten.Der Algorithmus versucht dann iterativ zu finden und fügen Sie den besten Knoten, der die Größe der Clique zunehmen wird.Ich werde erklären, was beste Knoten später bedeutet.Wenn der Algorithmus einen Knoten hinzufügen finden kann, wird versucht, den besten Knoten löschen aus der Clique zu finden.Hinter den Kulissen erinnert der Algorithmus das letzte Mal Knoten in der aktuellen Lösung Clique verschoben oder aus der Clique ausgezogen war.Der Algorithmus verwendet diese Informationen zum Hinzufügen von verbieten oder löschen vor kurzem Knoten für eine gewisse Zeit verwendet.Dies ist der Tabu Teil des-Algorithmus.

Der Algorithmus wird selbst jeder so oft, wenn keine Fortschritte bei der Suche nach eine bessere (größere) Clique.Der Algorithmus speichert automatisch die Lösungen (Cliquen) es zuvor gesehen hat.Der Algorithmus nutzt diese Lösung Geschichte, die verbieten Zeit dynamisch anzupassen.Wenn der Algorithmus hält die gleichen Lösungen, erhöht es die Zeit verbieten zu entmutigen zuletzt verwendete Knoten verwendet werden.Wenn der Algorithmus nicht dieselben Lösungen sehen, verringert es die Zeit verbieten, so gibt es ein größerer Pool von Knoten zur Auswahl.Dies ist die adaptive Teil des Algorithmus Tabu.

In den meisten Situationen, in denen ein gieriger Algorithmus verwendet wird, ist die optimale Lösung nicht bekannt, so dass eine oder mehrere stoppen Bedingungen angegeben werden müssen.Wenn der Algorithmus eine beenden-Bedingung trifft, ist die beste Lösung gefunden angezeigt.

In den folgenden Abschnitten, ich werde durchlaufen Sie den Code, der den Screenshot in erzeugt Abbildung 2.Der vollständige Quellcode ist verfügbar unter code.msdn.microsoft.com/mag201112TestRun.Diese Spalte wird vorausgesetzt, dass Sie haben mittelaktive Programmierkenntnisse mit einer C-Familie Sprache oder die Visual Basic.NET-Sprache.C# verwenden, aber ich habe den Code geschrieben, so dass Sie können auf Umgestalten in eine andere Sprache wie z. B. f# oder Python ohne allzu große Schwierigkeiten Wenn Sie möchten.

Allgemeine Programmstruktur

Die allgemeine Struktur des Programms angezeigt, Abbildung 2 präsentiert sich in Abbildung 3.Habe ich beschlossen, platzieren Sie Code in einer einzelnen Konsolenanwendung mit statische Methoden für Einfachheit, aber Sie können Teile des Codes in Klassenbibliotheken modularisieren und Verwenden eines Objekt-orientierten Ansatzes.Das Programm ist weniger kompliziert als Sie vermuten könnte, bei der Suche nach Abbildung 3 da die meisten Methoden kurze Hilfsmethoden sind.

Abbildung 3 Allgemeine Programmstruktur

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

Das Programm hat zwei allgemeine Klassen, und jede dieser Klassen hat eine Unterklasse Helfer. Klasse TabuMaxCliqueProgram enthält die Main-Methode und alle Algorithmus Logik, zusammen mit Unterklasse CliqueInfo, die zur Verwaltung eines Verlaufs der zuvor gesehen Clique Lösungen verwendet wird. Klasse MyGraph kapselt eine effiziente Graphstruktur-Darstellung und enthält Unterklasse BitMatrix, die verwendet wird, um Adjacency Knoteninformationen in kondensierter Form zu speichern. Ein Klasse Gültigkeitsbereich Random-Objekt mit dem Namen zufällige wird verwendet, um die Clique zu einem zufälligen Knoten zu initialisieren und Bindungen zu brechen, wenn es gibt mehrere beste Knoten zum Hinzufügen oder löschen.

Mit einigen WriteLine Anweisungen und Try-Catch-Code entfernt ist die Main-Methode:

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

Das Diagramm wird als ein Programm definierten MyGraph-Objekt dargestellt. Das Diagramm wird aus einer externen Textdatei geladen, das das California-Dateiformat verwendet. Die wichtigste Methode der MyGraph ist AreAdjacent, die true zurückgegeben, wenn zwei Knoten verbunden sind. 50 Iterationen herstellen eine absolute beenden Bedingung für den gierigen Algorithmus sollen MaxTime. Dies ist künstlich kleine. In ein richtiger maximale Clique Problem ist die maximale Zeit in der Regel im Bereich von 1.000 bis 100.000. Eingestellte TargetClique Größe, eine zweite beenden Bedingung einzurichten; wird eine Clique hat, die die gleiche Anzahl von Knoten gefunden, wie in dem Diagramm vorhanden sind, muss die maximale Clique gefunden wurden. Die meiste Arbeit erfolgt durch die FindMaxClique Methode, die einen gierig, adaptive Tabu-Algorithmus verwendet, um für die größten möglichen Clique suchen. Die Hilfsmethode ListAsString erstellt einfach eine String-Darstellung einer Liste <int> -Objekt.

Die FindMaxClique-Methode

Die FindMaxClique-Methode ruft mehrere Hilfsmethoden, die ich kurz beschreiben werde. In High-Level Pseudocode, findet sich der FindMaxClique-Algorithmus in Abbildung 4. Der Pseudocode lässt mehrere wichtige Details zur Verdeutlichung aber präsentiert die wichtigsten Punkte des-Algorithmus.

Abbildung 4 Anpassungsalgorithmus Tabu Maximum Clique

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

Das lokale Clique-Objekt ist die aktuelle Lösung Clique. Das random-Objekt instanziiert wird mit einem beliebigen Startwert von 1. Die Variable Zeit wird der Zähler für den Algorithmus wichtigsten Verarbeitungsschleife. Die Variablen TimeBestClique und TimeRestart werden verwendet, um festzustellen, ob es wurde ein Mangel an Fortschritten, so dass der Algorithmus selbst neu starten kann. Weiter:

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

Der Zeitraum verbieten wird mit 1 initialisiert. Dies bedeutet, dass — zunächst mindestens — nachdem ein Knoten vom Algorithmus verwendet wurde, kann es für eine Zeit Iteration verwendet werden. Wenn ich einen Wert von 0 verwendet hatte, wäre die Wirkung gewesen, keine Zeit überhaupt verbieten. Die meisten Tabu Algorithmen verwenden einen festen Wert für die Zeit verbieten, aber das Problem bei diesem Ansatz ist, dass Forschung, dass der beste Wert für eine feste verbieten Zeit variiert gezeigt hat von Problem zum Problem. Der adaptive Ansatz präsentiere ich Aktualisierungen verbieten Zeit während der Algorithmus ausgeführt wird, basierend auf der Geschichte der bisherigen Lösungen. Ich nenne diese Technik adaptive Tabu, aber einige Forschungsarbeiten rufen die Technik reaktive oder dynamische.

Das LastMoved-Array wird verwendet, um festzustellen, ob ein Knoten erlaubt oder zu einem bestimmten Zeitpunkt verboten. Der Index des Arrays stellt einen Knoten dar, und der entsprechenden Array-Wert ist die Zeit, die der Knoten zuletzt verschoben wurde (hinzugefügt oder gelöscht). Mithilfe des LastMoved-Arrays, wodurch ich müssen explizit erstellen, eine Liste der zulässigen Knoten (oder äquivalent, verboten Knoten). Ich Initialisieren aller Zellen in LastMoved in int.MinValue, so dass ich später feststellen können, ob ein Knoten nie verwendet wurde.

Das Geschichte Hashtable-Objekt enthält eine Auflistung von zuvor gesehen Lösung Cliquen. Jedes Element in der Hashtabelle ist ein CliqueInfo-Objekt, das ich später im Detail beschreiben werde. Ich konnte ein generisches Dictionary-Objekt anstelle von der nicht generischen Hashtable-Objekt verwendet haben. FindMaxClique fährt fort:

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

Ich initialisieren die aktuelle Lösung Clique zu einem zufälligen Knoten aus dem Diagramm. Eine BestClique-Liste zu verfolgen die besten (größte) Clique gefundene Lösung vom Algorithmus wird instanziiert. Als nächstes kommt:

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

Die MakePossibleAdd-Methode erstellt eine Liste aller Knoten, die die aktuellen Clique um die Größe der Clique erhöhen von 1 hinzugefügt werden können. Mit anderen Worten, erstellt die Methode eine Liste von Knoten, die nicht in der für jeden Knoten in der Clique verbunden sind. Dieser PossibleAdd Liste hätte die Anzahl 0 oder verbotene Knoten enthalten kann. MakePossibleAdd Ruft Hilfsmethode FormsALargerClique.

Die MakeOneMissing-Methode erstellt eine Liste aller Knoten, die für alle aber genau einer der Knoten in der aktuellen verbunden sind. Es ist nicht offensichtlich, aber es stellt sich heraus, dass solch eine Liste erstellt einen cleveren Weg, um zu bestimmen, welcher Knoten in der aktuellen Clique der besten Knoten zu löschen, ist wie ich später eingehen werde. Die wichtigsten Verarbeitungsschleife beginnt:

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

Die wichtigsten Verarbeitungsschleife wird beendet, wenn die maximale Anzahl von Iterationen erreicht wird oder wenn eine beste Lösung mit der Zielgröße Clique gefunden wird. Ich verwende die CliqueChanged-Variable steuern die Verzweigungslogik zwischen hinzufügen und Löschen von Knoten, wie Sie sehen werden. Die Logik für einen zulässigen Knoten hinzufügen wird angezeigt, Abbildung 5.

Abbildung 5 die Logik einen zulässigen Knoten hinzufügen

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

Der Algorithmus prüft, ob es gibt keine Knoten, die die Größe der aktuellen Clique zunehmen wird. Wenn also, Methode SelectAllowedNodes erstellt eine Liste der Knoten, die zulässig sind – d. h. nicht tabu — aus der Liste der Knoten, die hinzugefügt werden können.

Die wichtigste Zeile in SelectAllowedNodes lautet:

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

Die CurrNode ist einer der Knoten in der Liste PossibleAdd. Die Logik überprüft, um festzustellen, ob genügend Zeit Statuszählern der Knoten zuletzt verwendet wurde seit, so dass der Knoten hinter den Zeitraum verbieten ist. Wenn ja, wird der Knoten in die Liste der AllowedAdd-Knoten hinzugefügt.

Jetzt, wenn gibt es keine Knoten, die sind zulässig und erhöht die Größe der Clique, bestimmt Methode GetNodeToAdd den besten Knoten die Clique hinzu. Der besten Knoten ist der Knoten aus der AllowedAdd-Liste, die am meisten mit Knoten in der Liste PossibleAdd verbunden. Die Idee ist, dass Sie einen Knoten hinzuzufügen, der Sie die meisten Chancen geben auf einen Knoten in der nächsten Iteration des Algorithmus hinzufügen möchten. Es kann mehrere Knoten in der AllowedAdd-Liste, die gebunden sind, als die meisten zu den Knoten im PossibleAdd verbunden. Wenn ja, ist einer der gebundenen Knoten nach dem Zufallsprinzip ausgewählt. Nach den besten Knoten hinzufügen, wird die aktuellen Projektmappe Clique Gründen sortiert, die ich später eingehen werde. Der Code zum Löschen eines Knotens ist:

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

Wenn der Algorithmus einen Knoten hinzufügen kann, wird versucht, einen zulässigen Knoten in der Hoffnung zu löschen, die Rückverfolgung eine Lösung führen, mit denen einen neuen Knoten in der nächsten Iteration hinzugefügt werden. Die Liste der Knoten in der aktuellen wird von der SelectAllowedNodes-Methode zum Abrufen von Knoten, die nicht Tabu sind gefiltert. Der GetNodeToDrop wählt die besten dieser Knoten löschen Sie mithilfe der Liste der OneMissing-Knoten.

Die Idee ist, den zulässigen Knoten in der aktuellen, löschen, der der größte Anstieg in der Liste der PossibleAdd Knoten führt. Eine Möglichkeit, dies zu tun ist jeder Knoten in die Liste der zulässigen testen, indem es tatsächlich von der aktuellen Clique zu entfernen und dann die Größe der resultierenden PossibleAdd Liste computing. Aber es ist ein sehr viel effizienter Ansatz, der eine Liste von Knoten verwendet, die für alle aber genau einer der Knoten in der aktuellen verbunden sind. Mithilfe der OneMissing-Liste der Knoten, kann die Liste wie folgt verwendet werden. Scannen Sie jeden Knoten in den zulässigen Clique Knoten und zählen Sie, wie viele Knoten in der Liste OneMissing Fernsehgerät auf den Knoten Clique sind. Verbindung des Knotens in der Liste zulässiger Clique, die zumindest für die Knoten in der OneMissing Liste ist der beste Knoten zu löschen. Nach dieser am wenigsten verbundenen Knoten löschen, alle Knoten in der OneMissing-Liste, die mit dem gelöschten Knoten verbunden waren nicht werden jetzt vollständig auf den verbleibenden Knoten in der verbunden und daher werden neue PossibleAdd Knoten.

An diesem Punkt in der Logik, es möglicherweise nicht möglich gewesen, einen zulässigen Knoten hinzufügen oder Löschen eines zulässigen Knotens. Um selbst unstick, löscht der Algorithmus einen zufälligen Knoten aus der aktuellen Clique:

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

Als nächstes startet den Algorithmus überprüft, wenn eine mangelnde Fortschritte gegeben hat, und wenn ja, selbst:

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

Die Neustart-Variable ist die Anzahl der Iterationen, wo es keine Besserung oder seit dem letzten Neustart zulassen. Hier verwende ich einen Wert von 100 mal so groß wie die aktuelle beste Lösung. Der Wert für das Neustartintervall ist nicht gut verstanden und vielleicht möchten Alternativen zu versuchen. (Ich habe einen Dummywert von 2 zu mehr Neustarts für das Bildschirmfoto in Abbildung 2). Der Wert, den ich verwende hat gut für mich in der Praxis jedoch gearbeitet. Wenn es ein Neustart gibt, der Algorithmus setzt die verbieten Zeit zurück und löscht die Geschichte Hash-Tabelle mit Lösung Cliquen, die gesehen haben. Beachten Sie, dass der Algorithmus hat nicht noch Geschichte Hash-Tabelle aktualisiert. Der Neustart-Code Zurücksetzen nicht, jedoch das Array LastVisited die speichert Informationen über wenn Knoten wurden zuletzt hinzugefügt oder gelöscht von der Lösung Clique. Als nächstes kommt:

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

Der Algorithmus versucht, die Lösung Clique mit einem Knoten ein erneutes Seeding, die noch nie zuvor verwendet wurde. Wenn mehrere nicht verwendete Knoten vorhanden sind, ist eine nach dem Zufallsprinzip ausgewählt. Wenn keine nicht verwendeten Knoten vorhanden sind, wird ein zufälliger Knoten ausgewählt. Anstatt einen zufälligen Knoten zu verwenden, ist eine unerforschte Alternative um den Knoten auszuwählen, der am längsten verschoben wurde. Die Neustart-Codes abgeschlossen ist mit folgendem:

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

Die wichtigsten Verarbeitungsschleife und FindMaxClique Wrap up, etwa so:

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

Die Listen PossibleAdd und OneMissing werden neu generiert. Eine Alternative ist Hilfsdaten Strukturen pflegen und aktualisieren diese beiden Listen statt sie von Grund auf neu zu erstellen. Die UpdateProhibitPeriod-Methode ist die Schlüsselkomponente des adaptive Teils des Algorithmus Tabu, und ich werde es kurz beschreiben.

Erinnerung an frühere Lösungen

Methode UpdateProhibitPeriod verwendet eine Hash-Tabelle der zuvor gesehen Lösungen dynamisch erhöhen oder verringern die Zeit nicht zulassen. Daran erinnern Sie, dass eine Lösung einer Clique, die eine Liste <int> der Knoten, die alle miteinander verbunden sind. Aber ich muss auch zum Speichern der Zeit, wann eine Lösung zuletzt gesehen wurde. Daher ich Kapseln eine Clique-Lösung und das letzte Mal wurde gesehen in einer CliqueInfo-Klasse in aufgeführten Abbildung 6.

Abbildung 6 die CliqueInfo-Klasse

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

Da die Lösung Geschichte Hashtable ein CliqueInfo-Element hinzugefügt wird, benötige ich eine benutzerdefinierte GetHashCode Hash-Funktion. Schreiben von benutzerdefinierten Hashfunktionen ist überraschend schwierig, und eine gründliche Diskussion aller Beteiligten Fragen müsste eine ganze Spalte. In diesem Fall, ich benutze die einfachste — aber nicht die effizienteste — Ansatz. Erstellt eine Zeichenfolgendarstellung der Knoten im Feld Clique, getrennt durch Leerzeichen, und dann mithilfe der integrierten String.GetHashCode. Zum Beispiel, wenn eine Clique Knoten enthaltenen {3 5 8}, ich generieren "3 5 8" (mit dem hinteren Leerzeichen) und anschließend einen Hashcode zu generieren aus dieser Zeichenfolge. Daran erinnern, dass Cliquen immer in einer sortierten Reihenfolge beibehalten werden, so wäre es möglich, dass eine Clique {3 5 8} und einem anderen Clique {8 3 5}. Ich statt Leerzeichen zwischen den Knoten also, die clique {3 5 8} unterscheidet sich von Clique {3 58}.

Aktualisieren der Zeitraum verbieten

Methode UpdateProhibitPeriod adaptiv erhöht oder verringert die verbieten Zeit auf der Grundlage von zuvor gesehen Clique Lösungen. Die Methode beginnt:

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

Die Methode gibt eine verbieten Zeit zurück, die vielleicht das gleiche wie die aktuelle verbieten Zeit sein könnte. Ein CliqueInfo-Objekt, das das aktuelle Clique und die aktuelle Uhrzeit instanziiert werden, wie hier gezeigt:

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

Der Code überprüft, ob die aktuelle Clique Lösung in Form eines CliqueInfo-Objekts zuvor gesehen hatte — ist die Clique in der Hashtabelle Geschichte? Wenn die aktuelle Clique zuvor gesehen hatte, berechnet der Algorithmus, wie lange es seit die Clique gesehen wurde. Wenn dieses Intervall kurz genug ist, wird die verbieten (vorbehaltlich einer Obergrenze) erhöht. Die Idee ist, da es sehr lange seit noch nicht die aktuelle Clique gesehen wurde, der Algorithmus doppelte Lösungen generiert. Wenn die verbieten Zeit erhöht wird, wird es mehr Tabu Knoten und daher zulässig weniger Knoten, wodurch die Chancen doppelte Clique Lösungen zu generieren. Wenn vor die aktuellen Projektmappe Clique gesehen wurde hat, ist es die Geschichte Hash-Tabelle hinzugefügt.

Das "kurz genug" Intervall ist zweimal die Anzahl der Knoten im Diagramm, weniger ein. Dies dient zum bestimmen, wann die verbieten Zeit erhöhen. Der beste Wert, hier ist eine weitere offene Frage in der maximale Clique Forschung. Die "Obergrenze" für die Zeit nicht zulassen ist zweimal die Größe der aktuellen Projektmappe bekannt. Der beste Obergrenze Wert ist, wie Sie vielleicht, von jetzt an, eine weitere offene Fragestellung denken können.

Zu diesem Zeitpunkt entweder die aktuelle Clique noch nicht vorher, gesehen oder die Clique hat vorher gesehen aber das Intervall benötigt, um die verbieten Zeit erhöhen war nicht klein genug. Also überprüft der Algorithmus nun, ob der Zeitraum verbieten, werden kann die verringert der Anzahl der Knoten Tabu und erhöhen die Anzahl der zulässigen Knoten, die wiederum dem Algorithmus gibt weitere Knoten hinzufügen oder löschen:

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

Anstatt explizit überprüft, ob es "relativ" lange gewesen, da die aktuelle Clique gesehen wurde, überprüft der Algorithmus indirekt, wie lange es seit die aktuelle Clique gesehen wurde, anhand der Zeit, wann die verbieten Zeit zuletzt geändert wurde. Wieder einmal ist nicht der beste Wert für "relativ lange" klar. Ich benutze einen Wert 10 mal so groß wie die aktuelle beste Lösung. Beachten Sie, dass das verbieten Mal unter 1 löschen kann.

Mehr Forschung

Forschungsergebnisse auf das maximale Clique Problem schlagen vor, daß ein gieriger Ansatz mit adaptive Tabu-Funktion die besten Ergebnisse gibt, wenn Leistung und Lösungsqualität berücksichtigt werden. California ist eine Forschungseinrichtung, die eine Reihe von schwierigen Graph Clique Maßstab Probleme erstellt. Ich lief den Code gegen einen besonders schwierigen California Problem (C2000.9) und den Code schnell (in weniger als zwei Sekunden) eine Clique mit Größe 76 gefunden, die innerhalb von 1,5 Prozent der Größe der bekanntesten Lösung von 77 ist hier dargestellt.

An mehreren Punkten in dieser Spalte habe ich Forschungsergebnisse auf das maximale Clique Problem erwähnt. Wenn Sie diese Forschung interessiert sind, empfehle ich Sie Durchsuchen Sie das Web für wissenschaftliche Arbeiten durch Folgendes geschrieben: R. Battiti Et Al., W. Pullan Et Al. und k. Katayama Et Al. Mehrere Papiere von diesen drei Autoren und ihre Kollegen wurden meine Primärverweise.

Ein viel versprechende unerforschtes Gebiet für den maximalen Clique Algorithmus hier dargestellt ist, irgendeine Form des sogenannten Plateau Suche zu integrieren. Daran erinnern Sie, dass der maximale Clique Algorithmus zunächst versucht, einen nicht-Tabu Knoten der aktuellen Clique Projektmappe hinzuzufügen. Wenn das nicht möglich ist, löscht der Algorithmus dann, einen Knoten aus der aktuellen Projektmappe Clique. Die Idee der Hochebene Suche ist zu einem Knoten in der aktuellen Projektmappe Clique, die mit einem Knoten nicht in der ausgetauscht werden können. Obwohl dies nicht die Größe der aktuellen Clique erhöhen, verringern nicht die Größe der Clique, entweder.

Dr. James McCaffrey* arbeitet für Volt Information Sciences Inc., wo er technische Schulungen für Softwareentwickler bei der Microsoft in Redmond, Washington, Campus. Er ist in mehreren Microsoft-Produkten, einschließlich Internet Explorer und MSN Search gearbeitet. Dr. McCaffrey ist der Autor von ".NET Test Automation Recipes"(Apress, 2006), und kann erreicht werden unter jammc@microsoft.com*.

Dank der folgenden technischen Experten für die Überprüfung dieses Artikels: Paul Koch, Dan Liebling, Ann Loomis Thompson und Shane Williams