Dieser Artikel wurde maschinell übersetzt.

Testlauf

Greedy-Algorithmus und Maximum Clique

James McCaffrey

Im Artikel dieses Monats werde ich eine Lösung des Problems der Graph maximale Clique vorstellen.Die Lösung verwendet, was einen greedy-Algorithmus aufgerufen hat, und ich werde erläutern, wie das 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.Schauen Sie sich das einfache Diagramm in der Abbildung 1.Das Diagramm verfügt über neun Knoten und 13 Kanten.Das Diagramm nicht beruecksichtigt ist (Es gibt keine Prioritäten der Kanten zugeordnet) und ohne Ausrichtung (alle Kanten sind bidirektional).Knoten 2, 4 und 5 bilden eine Clique Größe drei.Die maximale Clique ist 0, 1, 3 und 4, bilden eine Clique Größe vier Knotensatz.

 

Abbildung 1: Grafik für einen Algorithmus gierig Maximum Clique

Das maximale Clique Problem ist aus mehreren Gründen interessant.Es ist zwar nicht aus der einfachen Grafik in Abbildung 1, das maximale Clique-Problem ist eines der größten Herausforderungen in Computer Science.Es stellt sich in vielen wichtigen Anwendungen wie z. B. Kommunikation Analyse sozialer Netzwerke, in denen Knoten Personen darstellen und Kanten darstellen, eine Nachricht oder einer Beziehung.Und das Problem der maximalen Clique eignet sich gut für die Lösung durch gierige Algorithmus eine grundlegende Technik in Computer Science ist.

Informelle ausgedrückt ist ein greedy-Algorithmus einen Algorithmus, der mit einer einfachen, unvollständige Lösung um ein schwieriges Problem beginnt und dann iterativ sucht nach der beste Weg zur Verbesserung der Lösung.Der Vorgang wird wiederholt, bis eine Bedingung anhalten erreicht ist.Abbildung 2 veranschaulicht, die wichtigen Anregungen für die maximale Clique Problem und zeigt Ihnen, worauf ich hinaus will, in diesem Artikel.

Abbildung 2 gierig Maximum Clique Demo ausführen

Ich habe eine Konsolenanwendung, die beginnt, indem Sie das Diagramm, das dem in gezeigten entspricht in den Speicher geladen Abbildung 1.Entwerfen und Programmieren eine effiziente Graph-Datenstruktur ist ein schwerwiegendes Problem an sich.Ich erklärte Code-Struktur den Graph in meinem letzten Artikel (msdn.microsoft.com/magazine/hh456397).Der Algorithmus zunächst ein einzelner Knoten in diesem Fall Knoten 2, nach dem Zufallsprinzip ausgewählt und eine Clique mit diesem Knoten initialisiert.Als Nächstes durchsucht der Algorithmus für den besten Knoten die Clique hinzu.Wenn Sie beziehen sich auf Abbildung 1, wie Sie sehen, gibt es nur zwei Knoten, 4 und 5, die eine größere Clique sein werden.Ich werde erklären, was der beste Knoten kurz bedeutet.

Der Algorithmus wählt und die Clique Knoten 4 hinzugefügt, so dass die Clique jetzt {2, 4}.An diesem Punkt liegt nur ein Knoten im Diagramm 5, das die Größe der clique zunehmen wird, so dass der Algorithmus Knoten 5 wählt und die Clique hinzugefügt.Es gibt nun keine Knoten, die die Größe der clique zunehmen wird.Der Algorithmus löscht den besten Knoten aus der Clique in der Hoffnung, dass ein neuer, andere Knoten hinzugefügt werden kann, die Fortschritte ermöglichen.In diesem Fall erkläre ich was bedeutet "beste" in Kürze.Der Algorithmus löscht Knoten 4 aus der Clique.Wie Sie sehen können, indem Sie auf das Diagramm, besteht keine Möglichkeit, Fortschritte machen.Diese Situation tritt häufig bei greedy-Algorithmen, so eine Möglichkeit es muss, aus der Sackgasse Lösungen zu erhalten.

Der Algorithmus verfolgt, wie lange es seit Fortschritte – d. h. eine Clique mit einer größeren gefunden wurde.Nach einer gewissen Zeit ohne Fortschritte startet der Algorithmus selbst neu.Die Clique deaktiviert ist.Dieses Mal wählt der Algorithmus nach dem Zufallsprinzip Knoten 3 als den ersten Knoten aus.Mit den gleichen iterativen Prozess suchen Sie den besten Knoten zum Hinzufügen oder löschen, ermittelt der Algorithmus schließlich die maximale Clique von {0, 1, 3, 4}.In den meisten Problemen, wo greedy-Algorithmen verwendet werden, ist nicht die optimale Lösung bekannt, so dass der Algorithmus wird fortgesetzt, bis einige stoppen Bedingung erfüllt ist.In diesem Fall wird der Algorithmus zum nach 20 Iterationen beenden konfiguriert.Zu diesem Zeitpunkt ist die beste Clique 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/mag201110TestRun (in dieser Spalte verwendet den gleichen Code vom letzten Monat).Dieser Artikel setzt voraus, haben Sie fortgeschrittene Programmierkenntnisse mit einer Sprache C-Familie oder der ASP.NET-Sprache.Ich C#, aber ich habe den Code geschrieben, so dass Sie sich zu einer anderen Sprache ohne allzu große Schwierigkeiten umgestaltet werden, wenn Sie wünschen können.

Allgemeine Programmstruktur

Die allgemeine Struktur des Programms angezeigt, Abbildung 2 dargestellt wird, in Abbildung 3.Das Programm hat Abhängigkeiten von Namespaces System, System.Collections.Generic (eine Clique wird als Typ List <int> dargestellt), System.IO (für das Laden des Quell-Diagramms aus einer Textdatei) und System.Collections (Klasse MyGraph Programm definierten verwendet BitArray-Klasse).Ich umbenennen die Hauptklasse aus dem Visual Studio-Vorlage generiert Programm zum GreedyMaxCliqueProgram aus Gründen der Übersichtlichkeit.Ich verwende ein Gültigkeitsbereich der Klasse Random-Objekt mit dem Namen "random", eine Clique auf einen zufällig ausgewählten Knoten zurücksetzen zu initialisieren und um Gleichwertigkeiten aufzulösen, wenn sich mehrere beste Knoten zum Hinzufügen oder löschen.

Abbildung 3 insgesamt Programmstruktur

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

Das Diagramm wird als ein Programm definierten MyGraph-Objekt dargestellt. Das Diagramm wird aus einer externen Textdatei geladen ein Standarddateiformat, das mit dem Namen California verwendet. Die wichtigste Methode der MyGraph ist AreAdjacent, die true zurückgegeben, wenn zwei Knoten verbunden sind. Ich legen Sie MaxTime auf 20 eine absolute anhalten-Bedingung für den greedy-Algorithmus festlegen. Eingestellte TargetCliqueSize eine zweite anhalten-Bedingung herstellen; Wenn eine Clique gefunden wird, dass die gleiche Anzahl von Knoten hat, wie im Diagramm vorhanden sind, ist die maximale Clique muss gefunden.

Die FindMaxClique-Methode

Der gesamte Vorgang erfolgt durch die Methode FindMaxClique, die einen greedy-Algorithmus verwendet, um nach der größten Clique möglich suchen. FindMaxClique ruft mehrere Hilfsmethoden bereit, die im Detail beschreiben. Ich das Programm mithilfe der statische Methoden Struktur, aber Sie können den Code umzugestalten, die, den ich hier eine vollständig objektorientierten Ansatz vorlegen. Die FindMaxClique-Methode durchläuft, bis eine der beiden stoppen Bedingungen erfüllt ist, und dann die besten Clique gefunden gibt. Die Programmdefinition enthält eine eingebettete MyGraph-Klasse, die Artikel des letzten Monats wurde.

Im Allgemeinen Pseudocode ist der FindMaxClique-Algorithmus:

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

Die Definition der FindMaxClique-Methode beginnt:

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 Clique. Das Random-Objekt, das mit einer beliebigen Startwert von 1 wird instanziiert. Die Zeitvariable wird eine Zählervariable der Schleife; Da es diskret ist, wäre ein guter alternativer Name "Tick". Ich verfolgen, die Zeit, als die aktuelle beste Clique gefunden wurde, und die Zeit des letzten Neustarts zu steuern, wann Neustarts geschehen wird. Ich werden Variablen für das Hinzufügen und Drop-Knoten dummy-Werte von-1 zuweisen:

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

Die Random.Next(x,y)-Methode gibt einen Wert größer oder gleich x und kleiner als y. Mit der Einstellung X = 0 "und" y = NumberNodes, erhalte ich einen zufällig ausgewählten Knoten von 0 bis 8 für den Graphen Beispiel:

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

Die BestClique-Liste wird verwendet, um eine Kopie der größten clique, bei dem Algorithmus Suchlauf gefundenen zu verfolgen. Ich verwende handy AddRange-Methode, um die Elemente in der aktuellen in BestClique kopiert. Die BestSize-Variable wird zur Vereinfachung verwendet. Die TimeBestClique wird verwendet, um festzustellen, ob ein Neustart des Algorithmus ausgeführt wird:

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

Die MakePossibleAdd-Hilfsmethode prüft die aktuelle Clique und erstellt daraus eine Liste aller Knoten, die die Clique der Clique vergrößert um eins hinzugefügt werden können. Diese Liste ist die Quelle des Kandidaten für den besten Knoten die Clique hinzu. Die MakeOneMissing-Hilfsmethode ist ein bisschen knifflig. Die Methode erstellt eine Liste aller Knoten, die alle bis auf einen Knoten in der aktuellen verbunden sind. Wie Sie sehen werden, wird diese OneMissing-Liste verwendet, bestimmen Sie den besten Knoten aus einer Clique löschen. Jetzt beginne ich die wichtigsten Verarbeitungsschleife:

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

Ich habe bereits erwähnt, benötigen greedy-Algorithmen in der Regel eine oder mehrere Bedingungen für stoppen. Hier wird die Schleife beendet, wenn die maximale Anzahl von Iterationen überschritten wird oder wenn die Größe der aktuellen clique eine Zielgröße erfüllt. Die CliqueChanged-Variable wird verwendet, um die Verzweigungslogik zwischen Knoten hinzufügen und Löschen von Knoten zu steuern. Ich konnte diese Variable ausgelassen und verwendet ein Wenn...Else Programmverzweigung anstelle von separaten Wenn...Klicken Sie dann Anweisungen, um Code, der einfacher zu lesen und zu ändern, meiner Meinung nach ist aber in diesem Fall die Verwendung eine Verzweigung Steuerelementvariable führt:

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

Ich überprüfen, um sicherzustellen, dass mindestens ein Knoten, die die Clique hinzugefügt werden kann, und rufen Sie die Hilfsmethode GetNodeToAdd vorhanden ist. Diese Methode durchsucht die Liste der Knoten in der Liste PossibleAdd und gibt den besten Knoten hinzufügen (die oft versprochen Erklärung der "beste" wird präsentiert Beschreiben von GetNodeToAdd). Dieser Knoten wird der aktuelle Clique hinzugefügt. Zu diesem Zeitpunkt sortieren Clique, weil ich weiter unten in der Algorithmus die Clique suchen muss, und die Clique sortiert wird, kann ich eine binäre Schnellsuche statt eine lineare Suche verwenden. Die neue Clique wird überprüft, um festzustellen, ob es besser ist als der aktuelle beste Clique (größer).

Als Nächstes kommt:

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

Wenn die Größe der aktuellen clique kann nicht erhöht werden, versucht der Algorithmus so löschen Sie einen Knoten aus der Clique. Die Hilfsmethode GetNodeToDrop wählt den besten Knoten aus der Clique löschen:

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

Zu diesem Zeitpunkt überprüft der Algorithmus um festzustellen, ob ein Mangel an Fortschritt stattgefunden hat. Der Neustart-Variablen bestimmt, wie lange warten, bevor Sie neu starten. Hier verwenden Sie den Wert der aktuellen besten clique doppelt so groß. In der Forschung auf dem Wert maximale Clique ist der optimale Wert für den Neustart noch offen. Der hier verwendete Wert basiert auf Versuche, die ich mit mehreren Benchmark-Graph Problemen durchgeführt haben. Ein Neustart tritt auf, wenn keine Fortschritte bei der Suche nach eine neue beste Lösung wurde oder er relativ viel Zeit seit dem letzten Neustart wurde. Wenn ein Neustart erfolgt, wird der Algorithmus leert die aktuelle Clique und wählt dann alle Knoten im Diagramm einen zufällig ausgewählten Knoten. Beachten Sie, dass es sich um ein simples Verfahren handelt. Wenn Sie wieder auf die Demo führen Sie im verweisen Abbildung 2, wie Sie sehen, der letzte Neustart einen anfänglichen Knoten ausgewählt, die bereits als erster Knoten Saatgut verwendet wurden, hatten:

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

Die FindMaxClique-Methode berechnet basierten auf der neuen Clique PossibleAdd und OneMissing-Listen, von Grund auf neu. Wenn die wichtigsten Verarbeitungsschleife beendet wird, gibt die Methode die beste Clique gefunden.

Den besten Knoten hinzufügen

Es gibt zwei Schritte zum Ermitteln des besten Knotens der aktuellen Clique hinzu. Zunächst wird eine Liste aller Knoten, die die Größe der aktuellen clique zunehmen wird benötigt. Zweitens ist zu bestimmen, welche dieser Knoten den besten Knoten erforderlich:

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

Die MakePossibleAdd-Methode scannt jeden Knoten im Diagramm. Wenn der Knoten geprüft ist an alle Knoten in der aktuellen gemäß Helper FormsALargerClique, verbunden, und klicken Sie dann den Knoten, die geprüft ein möglicher "hinzufügen"-Knoten ist und die Result-Liste verknüpft. Beachten Sie, könnte das Ergebnis eine leere Liste aber niemals null sein:

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

Die FormsALargerClique-Methode vergleicht ein Knoten, die für alle Knoten in der aktuellen. Wenn der andere Anwärterknoten neben sogar auf einem der Knoten in der nicht ist, kann nicht der andere Anwärterknoten der aktuellen Clique hinzugefügt werden. Beachten Sie, dass da AreAdjacent false zurückgibt, wenn ein Knoten mit sich selbst verglichen wird, wird nicht die Knoten in der aktuellen zur Liste der PossibleAdd-Knoten hinzugefügt werden.

Die Grundidee hinter Ermitteln des besten Knotens hinzufügen ist ein Knoten aus der Liste der PossibleAdd-Knoten auswählen, die meisten kann, mit allen anderen Knoten in der PossibleAdd verbunden. Ein Knoten, der hoch verbunden ist liefert die größte neue Liste der Knoten, auf die nächste Iteration des Algorithmus hinzuzufügen.

Als Nächstes kommt:

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

Die GetNodeToAdd-Methode wird davon ausgegangen, dass die PossibleAdd-Liste mindestens ein Knoten hat. Wenn genau ein Knoten vorhanden ist, muss, die den besten Knoten sein:

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

Es kann mehrere Knoten in der Liste der PossibleAdd, die mit anderen als den verbundenen zu den anderen Knoten in der Liste gebunden sind. Nehmen wir beispielsweise an, das Diagramm in der Analyse wird das Diagramm dargestellt, die Abbildung 1 und die aktuelle Clique hat nur Knoten 0. Die PossibleAdd-Knoten sind {1, 3, 4}. Knoten 1 mit zwei Knoten im PossibleAdd verbunden ist – und in der Tat, so sind die Knoten 3 und 4. Eine vorläufige Überprüfung erfolgt so bestimmen die maximale Anzahl von Verbindungen zur Verfügung:

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

Sobald die maximale Anzahl von Verbindungen bekannt ist, wird der Algorithmus erneut von die PossibleAdd-Liste und fügt alle Knoten im PossibleAdd, die die maximale Anzahl von Verbindungen zu einer Liste von Kandidaten Knoten verfügen. Beachten Sie, dass der Double-Scan beseitigt werden konnte, mithilfe von auxiliary-Datenspeichern, die Anzahl der Verbindungen an, die jeder PossibleAdd-Knoten verfügt über:

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

An diesem Punkt hat die Kandidatenliste ein oder mehrere beste Knoten die Clique hinzu. Beachten Sie, dass Kandidaten eine Anzahl von mindestens haben müssen, da angenommen wird, haben eine Anzahl von mindestens einem die PossibleAdd-Liste. Der Algorithmus wählt einen der Knoten Kandidat nach dem Zufallsprinzip und gibt es zurück. Ich konnte gesucht wird, um festzustellen, ob die Größe der Liste der Kandidaten eine ist, und wenn dies der Fall ist, den einzelnen Knoten in Kandidaten zurückzugeben habe.

Den besten Knoten löschen

Ermitteln des besten Knotens löschen aus der aktuellen Clique ist ein wenig subtil. Die Idee ist, einen Knoten in der aktuellen zu löschen, die die größte Zunahme der Liste der PossibleAdd-Knoten führt.

Eine Möglichkeit, dies zu tun ist auf jedem Knoten in der aktuellen zu testen, indem Sie tatsächlich aus der aktuellen Clique zu entfernen und anschließend die Größe der resultierenden Liste PossibleAdd. Aber es gibt ein viel effizienter Ansatz, der eine Liste von Knoten verwendet, die mit genau einer der Knoten in der aktuellen verbunden sind. Es ist so eine OneMissing Liste der Knoten, kann die Liste wie folgt verwendet werden: Scannen Sie jeden Knoten in der aktuellen und zählen, wie viele Knoten in der Liste der OneMissing nicht mit dem Clique Knoten verbunden sind. Der Knoten in der aktuellen, die mit den Knoten in der Liste der OneMissing am wenigsten verbunden ist ist die beste Knoten löschen. Nach dem Ablegen dieser Knoten am wenigsten verbunden, werden alle Knoten in der OneMissing-Liste, die mit dem gelöschten Knoten verbunden waren nicht jetzt vollständig mit den verbleibenden Knoten in der Clique, neue PossibleAdd-Knoten und sind somit verbunden sein.

Die MakeOneMissing-Methode dargestellt, in Abbildung 4. Die Methode überprüft jeden Knoten im Diagramm. Die Idee ist, zählen, wie viele Knoten in der mit dem aktuellen Knoten geprüft verbunden sind. Wenn die Summe der verbundenen Knoten zählen ist genau eins kleiner sein als die Größe der aktuellen clique, und klicken Sie dann der Knoten, die geprüft ist ein OneMissing-Knoten. Die Methode Kurzschlüsse, wenn der aktuelle Knoten, die geprüft wird, die weniger als die notwendige Anzahl von Nachbarn verfügt. Die Methode muss Knoten herauszufiltern, die bereits in der sind, da sie alle bis auf einen Knoten in ihrer eigenen Clique (d. h. sich) verbunden sind. Da die aktuelle Clique (nach jedem Hinzufügen oder die Drop) sortiert ist, kann eine binäre Suche verwendet werden, anstatt eine langsamere lineare Suche (finden Sie unter Abbildung 4).

Abbildung 4 Stellen Liste der OneMissing Knoten

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

Die GetNodeToDrop-Methode beginnt:

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

Die Methode wird davon ausgegangen, dass die aktuelle Clique mindestens ein Knoten hat. Wenn in der aktuellen nur ein Knoten vorhanden ist, ist es der einzige Knoten, der gelöscht werden kann. Die Methode bestimmt die größte Anzahl von Knoten in der Liste der OneMissing, die zu einem Knoten in der aktuellen verbunden sind, da es sich möglicherweise mehr als einen Knoten in der, die maximal von der Liste OneMissing getrennt ist:

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

Sobald die maximale Anzahl der Unterbrechungen bekannt ist, erneut die Methode die Clique diesen Knoten suchen, die am häufigsten getrennt sind und jeweils eine Liste von Kandidaten hinzugefügt. Wie bei der Methode GetNodeToAdd konnte GetNodeToDrop einen erneuten Scan vermeiden, indem auxiliary Datenspeicher verwalten:

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

Methode GetNodeToDrop beendet einen zufällig ausgewählten Knoten aus der Liste der besten Knoten löschen zurückgegeben:

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

Schlussbemerkung

Sind greedy-Algorithmen effizient? Greedy-Algorithmen wurden trotz der ihrer relativen Einfachheit sehr effektiv in viele Problemszenarien werden gezeigt. Allerdings kann die Effektivität anhand verschiedener Kriterien, einschließlich der Geschwindigkeit und Qualität der Lösung definiert werden. Es diesen Algorithmus gegen mehrere extrem schwierig Benchmark-Graph Probleme, die von der California Research Organization verwaltet der Algorithmus war und sehr effektiv, maximale cliquen, die in der Regel innerhalb von 5 Prozent der bekanntesten Lösungen waren produzieren und schnell ausgeführt.

Greedy-Algorithmen testen kann schwierig sein. Testen Sie zusätzlich zu den üblichen Verfahren wie z. B. Komponententests, Randbedingung testen und so weiter – und da greedy-Algorithmen Lösungen haben, die im Laufe der Zeit zunehmen – eine wirksame Prüfstrategie Hilfsmethoden zu schreiben, die den Status der vom Algorithmus verwendeten Datenstrukturen iterativ zu überprüfen ist. Beispielsweise schrieb ich während des Testens des maximale Clique-Algorithmus, der hier vorgestellten, Methoden, mit die überprüft wird, gab es keine doppelten Knoten in der aktuellen, stellen Sie sicher, kein Knoten in der aktuellen befindet sich in der aktuellen PossibleAdd oder OneMissing aktuellen Listen und so weiter.

Die hier vorgestellten gierig maximale Clique Algorithmus kann auf verschiedene Weise eine bessere Ergebnisse geändert werden. Eine Technik, die für die meisten greedy-Algorithmen, ist es, eine so genannte Tabu-Feature hinzuzufügen. Tabu Algorithmen verwalten eine Liste der zuletzt verwendeten Daten und möglicherweise eine Liste der zuletzt gesehen Lösungen. Daten in der Liste Tabu wird nicht verwendet, um neue Lösungen zu erstellen. Darüber hinaus können greedy-Algorithmen eine Strategie namens Plateau Search häufig einsetzen. Wenn ein greedy-Algorithmus die aktuelle Projektmappe nicht verbessern kann, erzeugt eine Plateau Suche eine neue Lösung ohne rückwärts, wie z. B. das Löschen eines Knotens in das maximale Clique-Problem. Ich werde diese interessante und nützliche Tabu und Plateau-Techniken in einer zukünftigen Kolumne vorstellen.

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

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