Clique problème de la conception d'un algorithme

L'un des affectations dans mon algorithmes de la classe est de concevoir un algorithme de recherche exhaustive pour résoudre le problème de la clique. Qui est, étant donné un graphe de taille n, l'algorithme est censé déterminer si il ya un sous-graphe de taille k. Je pense que j'ai obtenu la réponse, mais je ne peux pas aider mais pense qu'il pourrait être amélioré. Voici ce que j'ai:

Version 1

entrée: Un graphe représenté par un tableau A[0,...n-1], la taille k de la sous-graphe à trouver.

sortie: True si un sous-graphe existe, False sinon

Algorithme (en python-comme le 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

entrée: Une matrice de contiguïté de taille n par n, et k la taille de la sous-graphe de trouver

sortie: Tous les sousgraphes dans Une de taille k.

Algorithme (cette fois fonctionnelle/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

N'quelqu'un a des pensées, des commentaires ou des suggestions? Cela inclut les bugs que j'ai peut-être manqué ainsi que les moyens de le rendre plus lisible (je ne suis pas habituée à l'aide de beaucoup de pseudo).

Version 3

Heureusement, j'ai parlé à mon professeur avant de soumettre la cession. Quand je lui ai montré le pseudo-code que j'avais écrit, il a souri et m'a dit que je n'ai façon trop de travail. D'une part, je n'ai pas à le soumettre pseudo-code, j'ai juste eu à démontrer que j'ai compris le problème. Et de deux, il était vouloir la force brute de la solution. Donc, ce que je me suis tourné dans ressemblaient à ceci:

entrée: Un graphe G = (V,E), la taille de la clique de trouver k

sortie: True si une clique existe, false sinon

Algorithme:

  1. Trouver le Produit Cartésien Vk.
  2. Pour chaque tuple dans la suite, le test si chaque sommet est relié à tous les autres. Si tous sont reliés, de retour de la vraie et de sortie.
  3. Return false et de sortie.

Mise à JOUR: Ajout d'une deuxième version. Je pense que c'est de mieux en mieux même si je n'ai pas ajouté de fantaisie de la programmation dynamique (que je connais).

Mise à JOUR 2: Ajout d'un peu plus de commentaire et de la documentation pour la version 2 plus lisible. Ce sera probablement la version je me tourne aujourd'hui. Merci pour l'aide de tous! Je souhaite que je pourrais accepter plus d'une réponse, mais j'ai accepté la réponse de la personne qui m'a aidé le plus. Je vous laisse les gars, vous savez ce que mon professeur pense.

Vous signifie sous-graphe de taille k droite? Aussi, je pense que k n'est pas utilisée dans votre pseudo.
Ouais, vous avez raison sur les deux points. 🙂
Il y a n sommets droit, c'est à dire Un[1,...,n]?
Arghhh... je l'ai eu mal dans le ci-dessus. Je voulais dire Un[0,...,n-1] mais je suppose que A[1,...,n] marcherait aussi bien.
Suggestion: Pourriez-vous documenter ce que les deux fonctions sont supposé faire?

OriginalL'auteur |