la conception d'algorithmes de problème coterie

StackOverflow https://stackoverflow.com/questions/509808

Question

L'une des missions dans ma classe d'algorithmes est de concevoir un algorithme de recherche exhaustive pour résoudre le problème clique. Ainsi, compte tenu de la taille d'un graphique n , l'algorithme est censé déterminer s'il y a un sous-graphe complet de taille k . Je pense que j'ai eu la réponse, mais je ne peux pas empêcher de penser qu'il pourrait être amélioré. Voici ce que j'ai:

Version 1

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

Sortie : Vrai si existe sous-graphe, Faux sinon

Algorithme (en pseudocode en forme de python): 

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 du sous-graphe de trouver

Sortie :. Tous les sous-graphes complets en A de taille k

Algorithme (cette fois en pseudocode fonctionnelle / Python): 

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

Quelqu'un at-il des pensées, des commentaires ou des suggestions? Cela inclut des bugs que je pourrais avoir manqué ainsi que les moyens de rendre plus lisible (je ne suis pas habitué à utiliser beaucoup pseudocode).

Version 3

Heureusement, j'ai parlé à mon professeur avant de soumettre la cession. Quand je lui ai montré le pseudo-code, je l'avais écrit, il a souri et m'a dit que je l'ai fait chemin trop de travail. D'une part, je ne devais pas soumettre pseudo-code; Je devais démontrer que je compris le problème. Et deux, il était vouloir la solution de force brute. Alors, que je me suis tourné dans l'air quelque chose comme ceci:

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

Sortie : Vrai si une clique existe, sinon false

algorithme :

  1. Trouvez le produit cartésien V k .
  2. Pour chaque tuple dans le résultat, le test si chaque sommet est relié à tous les autres. Si tous sont connectés, return true et la sortie.
  3. Retour faux et sortie.

UPDATE : deuxième version ajoutée. Je pense que cela va mieux même si je ne l'ai pas ajouté de programmation dynamique de fantaisie (que je connais).

MISE À JOUR 2 : Ajout de quelques commentaires et des documents pour la version 2 plus lisible. Ce sera probablement la version que je tourne aujourd'hui. Merci pour l'aide de tout le monde! Je voudrais pouvoir accepter plus d'une réponse, mais j'ai accepté la réponse par la personne qui m'a aidé le plus. Je vais vous laisser savoir ce que mon professeur pense.

Était-ce utile?

La solution

Quelques commentaires:

  • Vous ne devez considérer n-k-choisir des combinaisons de sommets, tous les k-uplets (n ^ k d'entre eux).
  • connected(tuple) ne semble pas juste. Vous ne devez réinitialiser dans la boucle unconnected?
  • Comme les autres ont suggéré, il y a de meilleures façons de forçage brute cela. Considérons la relation récursive suivante: A (k + 1) -subgraph est une clique si les premiers k sommets forment une clique et le sommet (k + 1) est adjacente à chacun des premiers k sommets. Vous pouvez appliquer ce dans deux directions:
    • Commencez avec un 1-clique et d'étendre progressivement la clique jusqu'à ce que vous obtenez la taille désirée. Par exemple, si m est le plus grand sommet de la clique actuelle, essayez d'ajouter sommet {m + 1, m + 2, ..., n-1} pour obtenir une clique qui est un sommet plus large. (Ceci est similaire à une profondeur d'abord traversal d'arbres, où les enfants d'un nœud de l'arbre sont les sommets plus grand que le plus grand sommet de la clique actuelle.)
    • Commencez par un sous-graphe de la taille désirée et vérifier si elle est une clique, en utilisant la relation récursive. Mettre en place un pour stocker les résultats sur le chemin tableau memoization .
  • (suggestion de mise en œuvre) Utiliser une matrice d'adjacence (0-1) pour représenter des bords du graphe.
  • (la taille initiale) Jeter tous les sommets avec un degré inférieur à k.

Autres conseils

une fois mis en œuvre un algorithme pour trouver toutes les cliques maximales dans un graphique, ce qui est un problème semblable à la vôtre. La façon dont je l'ai fait était basé sur cet article: http://portal.acm.org /citation.cfm?doid=362342.362367 - il a décrit une solution de retour en arrière que j'ai trouvé très utile comme guide, bien que je l'ai changé beaucoup de ce papier. Vous auriez 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 je pense vraiment qu'ils auraient dû nommé « non défini » le « jeu déjà considéré » parce qu'il est tout simplement trop confus autrement.

L'algorithme « pour chaque k-tuple des sommets, si elle est une clique, puis return true » fonctionne bien sûr. Cependant, il est la force brute, ce qui est probablement pas ce qu'est un cours d'algorithmes est à la recherche. Au lieu de cela, considérer les points suivants:

  1. Chaque sommet est un 1-clique.
  2. Pour chaque 1-clique, chaque sommet qui se connecte au sommet dans le 1-clique contribue à une 2-clique.
  3. Pour chaque 2-clique, chaque sommet qui se connecte à chaque sommet dans le 2-clique contribue à 3-clique.
  4. ...
  5. Pour chaque (k-1) -clique, chaque sommet qui se connecte à chaque sommet de la clique (k-1) contribue à un k-clique.

Cette idée pourrait conduire à une meilleure approche.

Peut-être essayer un .

Il est étonnant que taper les choses comme une question va vous montrer ce que vous venez d'écrire. Cette ligne: 

P = A x A x A  //Cartesian product

devrait être ceci:

P = A k // produit cartésien

  

Que voulez-vous dire par A ^ k? Prenez-vous un produit de la matrice? Si oui, est une matrice de contiguïté (vous avez dit qu'il était un tableau de n + 1 éléments)?

Dans la notation de setbuilder, il ressemblerait à quelque chose comme ceci:

  

P = {(x0, x1, ... XK) | x0 ∈ A et x1 ∈ A ... et XK ∈ A}

Il est fondamentalement juste un produit cartésien A pris k fois. Sur le papier, je l'ai écrit comme k étant un indice supérieur de A (je viens compris comment le faire en utilisant démarquage).

De plus, A est juste un tableau de chaque sommet individuel sans tenir compte de contiguïté.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top