Clique Problem Algorithmus Design

Question

Eine der Aufgaben in meiner Algorithmen-Klasse ist eine erschöpfende Suche Algorithmus zu entwerfen, die Clique Problem zu lösen. Das heißt, eine grafische Darstellung der Größe gegeben n , wird der Algorithmus bestimmen soll, ob es ein vollständiger Unter Graph der Größe ist k . Ich glaube, ich habe die Antwort bekommen, aber ich kann nicht umhin zu denken, es verbessert werden könnte. Hier ist, was ich habe:

Version 1

Eingabe : Ein Graph, der mit einem Array repräsentiert A [0, ... n -1], die Größe K des Subgraphen zu finden.

Ausgang : Wahr, wenn ein Teilgraph existiert, ansonsten False

Algorithm (in Python-like Pseudo-Code):

def clique(A, k):
    P = A x A x A //Cartesian product
    for tuple in P:
        if connected(tuple):
            return true
    return false

def connected(tuple):
    unconnected = tuple
    for vertex in tuple:
        for test_vertex in unconnected:
            if vertex is linked to test_vertex:
                remove test_vertex from unconnected
    if unconnected is empty:
        return true
    else:
        return false

Version 2

Eingabe : Eine Adjazenzmatrix der Größe n mit n und k der Größe des Subgraphen zu finden

Ausgang :. Alle komplett Subgraphen in A der Größe k

Algorithm (diesmal in Funktions- / Python Pseudo-Code):

//Base case:  return all vertices in a list since each
//one is a 1-clique
def clique(A, 1):
    S = new list
    for i in range(0 to n-1):
        add i to S
    return S

//Get a tuple representing all the cliques where
//k = k - 1, then find any cliques for k
def clique(A,k):
    C = clique(A, k-1)
    S = new list
    for tuple in C:
        for i in range(0 to n-1):
            //make sure the ith vertex is linked to each
            //vertex in tuple
            for j in tuple:
                if A[i,j] != 1:
                    break
            //This means that vertex i makes a clique
            if j is the last element:
                newtuple = (i | tuple) //make a new tuple with i added
                add newtuple to S
    //Return the list of k-cliques
    return S

Hat jemand irgendwelche Gedanken, Kommentare oder Anregungen? Dazu gehören Bugs Ich habe auch Möglichkeiten verpasst könnte dies besser lesbar zu machen (ich bin zu verwenden viel Pseudo-Code nicht verwendet).

Version 3

Zum Glück, ich sprach mit meinem Professor, bevor die Zuordnung einreichen. Als ich ihm den Pseudo-Code zeigte ich geschrieben hatte, lächelte er und sagte mir, dass ich es tat Weg zu viel Arbeit. Zum einen musste ich nicht Pseudo-Code vorzulegen; Ich hatte gerade zu zeigen, dass ich das Problem verstanden. Und zwei, er war die Brute-Force-Lösung wollen. Also, was ich gedreht sah in etwa so aus:

input : Ein Graph G = (V, E), die Größe der Clique finden k

Ausgang : Wahr, wenn eine Clique nicht vorhanden ist, andernfalls false

Algorithm :

1. Finden Sie die Kartesisches Produkt V ^k .
2. Für jedes Tupel im Ergebnis, Test, ob jeder Knoten mit jedem anderen verbunden ist. Wenn alle miteinander verbunden sind, return true und beenden.
3. Zurück falsch und zu beenden.

UPDATE : Added zweite Version. Ich denke, das wird immer besser, obwohl ich keine Lust dynamische Programmierung hinzugefügt haben (die ich kenne).

UPDATE 2 : hinzugefügt einige weitere Kommentierung und Dokumentation zu Version 2 besser lesbar zu machen. Dies wird wahrscheinlich die Version, die ich heute machen. Vielen Dank für die Hilfe aller! Ich wünschte, ich könnte mehr als eine Antwort akzeptieren, aber ich akzeptierte die Antwort von der Person, die mir am meisten geholfen hat. Ich lasse euch wissen, was mein Professor denkt.

Answer 1

Einige Kommentare:

• Sie müssen nur n-wählen-k Kombinationen von Scheitelpunkten betrachten, nicht alle k-Tupel (n ^ k von ihnen).
• connected(tuple) sieht nicht richtig aus. Brauchen Sie nicht unconnected innerhalb der Schleife zurück?
• Wie die andere vorgeschlagen haben, gibt es bessere Möglichkeiten, dies zu Brute-Forcing. Betrachten Sie die folgende rekursive Beziehung: A (k + 1) -subgraph eine Clique ist, wenn die ersten k Ecken eine Clique und Eckpunkt bilden (k + 1) ist neben jedem der ersten k Ecken. Sie können dies in zwei Richtungen gelten:
  • Starten Sie mit einem 1-Clique und allmählich die Clique erweitern, bis die gewünschte Größe zu erhalten. Zum Beispiel, wenn m der größte Knoten in der aktuellen Clique ist, versucht Vertex hinzuzufügen {m + 1, m + 2, ..., n-1} eine Clique zu erhalten, die eine Ecke größer ist. (Dies ist ähnlich einen Depth-First-Baum-Traversal, wo die Kinder eines Baumknoten der Ecken größer als der größte Eckpunkt in der aktuellen Clique sind.)
  • Starten Sie mit einem Subgraphen der gewünschten Größe und überprüfen, ob es sich um eine Clique, die rekursive Relation verwendet wird. Richten Sie eine memoization Tabelle, die Ergebnisse zu speichern, auf dem Weg.
• (Umsetzung Vorschlag) Verwenden eine Adjazenzmatrix (0-1) Kanten in dem Graphen darstellen.
• (initial Beschneiden) Wegwerfen alle Ecken mit Grad weniger als k.

Answer 2

I umgesetzt einmal einen Algorithmus alle maximalen Cliquen in einem Graphen zu finden, die ein ähnliches Problem bei Ihnen ist. So wie ich es tat, war auf diesem Papier zugrunde: http://portal.acm.org /citation.cfm?doid=362342.362367 - es beschrieb eine Backtracking-Lösung, die ich sehr nützlich als Leitfaden gefunden, obwohl ich ziemlich viel von diesem Papier gewechselt. Sie würden ein Abonnement müssen an, dass, obwohl zu bekommen, aber ich nehme an Ihrer Universität würde man zur Verfügung hat.

Eine Sache, über dieses Papier ist aber, ich glaube wirklich, sollten sie die „nicht festgelegt“ genannt haben, die „bereits als Set“, weil es sonst einfach zu verwirrend ist.

Answer 3

Der Algorithmus „für jedes k-Tupel von Ecken, wenn es sich um eine Clique ist, dann return true“ funktioniert sicher. Allerdings ist es brutale Gewalt, das ist wahrscheinlich nicht das, was ein Algorithmus Kurs sucht. Stattdessen betrachten die folgenden Möglichkeiten:

1. Jeder Knoten ist eine 1-Clique.
2. Für jede 1-Clique, jede Ecke, das in der 1-Clique zum Scheitel verbindet trägt zu einer 2-Clique.
3. Für jede 2-Clique, jede Ecke, das in der 2-Clique zu jedem Eckpunkt verbindet trägt zu einer 3-Clique.
4. ...
5. Für jede (k-1) -clique, jede Ecke, das in der (k-1) Clique zu jedem Scheitelpunkt verbindet trägt zu einer k-Clique.

Diese Idee könnte zu einem besseren Ansatz führen.

Answer 4

Vielleicht versuchen ein dynamische Programmiertechnik .

Answer 5

Es ist erstaunlich, was die Eingabe Dinge nach unten als Frage zeigen, werden Sie über das, was Sie gerade geschrieben haben. Diese Zeile:

P = A x A x A  //Cartesian product

sollte dies sein:

P = A ^k // cartesianischen Produkt

  

Was meinst du mit A ^ k? Nehmen Sie eine Matrix Produkt? Wenn dies der Fall ist, A die Adjazenzmatrix (Sie sagte, dass es eine Anordnung von n + 1 Elementen)?

In setbuilder Notation, würde es in etwa so aussehen:

  

P = {(x0, x1, ... xk) | x0 ∈ A und x1 ∈ A ... und xk ∈ A}

Es ist im Grunde nur ein Kartesisches Produkt von A genommen k mal. Auf dem Papier ich es geschrieben hätte mich wie k ein Exponent von A zu sein (ich jetzt gerade herausgefunden, wie die Verwendung von Abschlag zu tun).

Plus, A ist nur ein Array jeden einzelnen Vertex ohne Rücksicht auf adjacency.