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:
- Trouver le Produit Cartésien Vk.
- 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.
- 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.
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 |
Vous devez vous connecter pour publier un commentaire.
Quelques commentaires:
connected(tuple)
ne pas regarder à droite. N'avez-vous pas besoin de réinitialiserunconnected
l'intérieur de la boucle?OriginalL'auteur Zach Scrivena
Une fois, j'ai mis en place un algorithme pour trouver toutes les cliques maximales d'un graphe, qui est un problème similaire à la vôtre. Je l'ai fait il a été basée sur ce document: http://portal.acm.org/citation.cfm?doid=362342.362367 - il décrit une mandature solution que j'ai trouvé très utile comme un guide, mais j'ai changé beaucoup de ce document. Vous aurez besoin d'un abonnement pour obtenir à ce bien, mais je présume que votre Université aurait un disponible.
Une chose à propos de ce papier est bien vraiment, je pense qu'ils devraient avoir nommé le "non défini" les "déjà ensemble considéré" parce que c'est juste trop compliqué sinon.
OriginalL'auteur Ray Hidayat
L'algorithme "pour chaque k-tuple de sommets, si c'est une clique, alors retourner vrai" fonctionne pour vous. Cependant, il est la force brutale, qui n'est probablement pas ce que l'un des algorithmes de parcours de recherche. Au lieu de cela, envisager les mesures suivantes:
Cette idée pourrait conduire à une meilleure approche.
OriginalL'auteur Rudd Zwolinski
Peut-être essayer un technique de programmation dynamique.
OriginalL'auteur Nixuz
C'est incroyable ce que le typage des choses vers le bas comme une question de vous montrer sur ce que tu viens d'écrire. Cette ligne:
devrait être ceci:
P = A k //produit Cartésien
Dans setbuilder notation, il ressemblerait à quelque chose comme ceci:
Il est fondamentalement juste un produit Cartésien d'Une prise k fois. Sur le papier, je l'ai écrit vers le bas comme k étant un exposant de (je viens de trouvé comment le faire en utilisant markdown).
Plus, est juste un tableau de chaque sommet, sans égard pour la contiguïté.
Je crois que a est Une liste non-ordonnée de nœuds, c'est à dire 1, 2, 3, ... ,n. A^k donne tous les possibles de la longueur k de la combinaison d'entre eux. Puis il vérifie si une combinaison est connecté, c'est à dire, une clique.
A^k est simplement le produit Cartésien A×A×...Un (k fois), le commentaire et la réponse dit. [Il se compose de k-tuples (u,v,w,...) où chacun des éléments est dans A.]
Merci à vous, Paul. Vous l'avez dit mieux que je le pouvais. 🙂 Je vais prendre cela comme une invite qui je pourrais avoir besoin de reconsidérer une plus lisible moyen de le faire.
Ah, je vois. Donc les arêtes dans le graphe n'est pas explicite dans votre code de droit?
OriginalL'auteur Jason Baker