Problema Clique progettazione di algoritmi

Question

Uno dei compiti nella mia algoritmi di classe è quello di progettare una ricerca esaustiva algoritmo per risolvere il problema clique.Che è, dato riportato un grafico della dimensione n, l'algoritmo dovrebbe determinare se c'è una completa sub-grafico di dimensione k.Penso di aver ottenuto la risposta, ma non posso fare a meno di pensare che possa essere migliorato.Ecco quello che ho:

Versione 1

ingresso:Un grafico è rappresentata da un array A[0,...n-1], la dimensione k dei sottografi a trovare.

uscita:True se un sottografi esiste, False altrimenti

Algoritmo (in python-come pseudocodice):

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

Versione 2

ingresso:Un'adiacenza matrice di dimensione n con n e k la dimensione dei sottografi trovare

uscita:Tutte sentiment in Una di dimensione k.

Algoritmo (questo tempo funzionale/Python pseudocodice):

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

Qualcuno ha pensieri, commenti o suggerimenti?Questo include bug potrei aver perso così come modi per rendere più leggibile (non sono abituata a utilizzare molto di pseudocodice).

Versione 3

Fortunatamente, ho parlato con il mio professore, prima di presentare l'assegnazione.Quando gli ho mostrato il pseudo-codice che avevo scritto, lui ha sorriso e mi ha detto che ho fatto modo troppo lavoro.Per uno, non ho dovuto presentare pseudo-codice;Ho avuto solo per dimostrare che ho capito il problema.E due, lui era volendo la soluzione di forza bruta.Così che cosa ho girato sembrava qualcosa di simile a questo:

ingresso:Un grafo G = (V,E), la dimensione della cricca di trovare k

uscita:True se una cricca esiste, false altrimenti

Algoritmo:

1. Trovare il Prodotto Cartesiano V^k.
2. Per ogni tupla il risultato, verificare se ogni vertice è collegata a tutte le altre.Se sono tutti collegati, il ritorno vero e uscita.
3. Return false e di uscita.

AGGIORNAMENTO:Aggiunta la seconda versione.Penso che questo è sempre meglio anche se non ho aggiunto alcun fantasia di programmazione dinamica (che io sappia).

AGGIORNA 2:Aggiunto altri commenti e documentazione per fare la versione 2 più leggibile.Questa sarà probabilmente la versione attiva oggi.Grazie per l'aiuto di tutti!Vorrei poter accettare più di una risposta, ma ho accettato la risposta dalla persona che mi ha aiutato di più.Lascio a voi ragazzi sanno quello che il mio professore pensa.

Answer 1

Alcuni commenti:

• Hai solo bisogno di prendere in considerazione n-scegliere-k combinazioni di vertici, non tutti i k-tuple (n^k di loro).
• connected(tuple) non guardare a destra.Non è necessario reimpostare unconnected all'interno del ciclo?
• Come altri hanno suggerito, ci sono modi migliori di brute-forzatura di questo.Si consideri la seguente relazione ricorsiva:Un (k+1)-sottografi è una cricca se il primo k vertici forma una cricca di vertice e (k+1) è adiacente a ciascuno dei primi k vertici.È possibile applicare questo in due direzioni:
  • Inizia con 1 cricca e gradualmente espandere la cricca fino ad ottenere la dimensione desiderata.Per esempio, se m è il più grande vertice nell'attuale cricca, provare ad aggiungere un vertice {m+1, m+2, ..., n-1} per ottenere una cricca che è uno dei vertici più grandi.(Questo è simile a una profondità di-prima visita di alberi, dove i figli di un nodo dell'albero sono i vertici più grande il più grande vertice nell'attuale cricca.)
  • Iniziare con un sottografi della dimensione desiderata e controllare se è una cricca, utilizzando la relazione ricorsiva.Impostare un memoization tabella per memorizzare i risultati lungo la strada.
• (attuazione suggerimento) Utilizzare una matrice di adiacenza (0-1) per rappresentare i bordi del grafico.
• iniziale (potatura) Buttare via tutti i vertici di grado minore di k.

Answer 2

Una volta ho implementato un algoritmo per trovare tutti massimo di cricche in un grafico, che è un problema simile al tuo.Il modo in cui l'ho fatto era basato su questa carta: http://portal.acm.org/citation.cfm?doid=362342.362367 - ha descritto un backtracking soluzione che ho trovato molto utile come guida, anche se ho cambiato un bel po ' di carta.Hai bisogno di un abbonamento per ottenere che, però, ma presumo che la vostra Università dovrebbe avere a disposizione uno.

Una cosa su carta, però penso davvero che dovrebbe avere chiamato il "non" il "già considerati insieme" perché è solo troppo confusa altrimenti.

Answer 3

L'algoritmo "per ogni k-upla di vertici, se è una cricca, per poi tornare a vere e proprie" opere di sicuro.Tuttavia, è la forza bruta, che probabilmente non è ciò che un corso di algoritmi sta cercando.Invece, considerare quanto segue:

1. Ogni vertice è un 1-clique.
2. Per ogni 1-clique, ogni vertice che si collega al vertice del 1-clique contribuisce a 2 cricca.
3. Per ogni 2-clique, ogni vertice che si connette a ogni vertice del 2-clique contribuisce a 3 cricca.
4. ...
5. Per ogni (k-1)-clique, ogni vertice che si connette a ogni vertice in (k-1) clique contribuisce a una k-clique.

Questa idea potrebbe portare a un approccio migliore.

Answer 4

Forse provare un tecnica di programmazione dinamica.

Answer 5

È incredibile quello che digitando le cose come una questione mostra su ciò che hai appena scritto.Questa riga:

P = A x A x A  //Cartesian product

dovrebbe essere questo:

P = A ^k //Prodotto cartesiano

Che cosa si intende per A^k?Stai prendendo un prodotto matrice?Se è così, è la matrice di adiacenza (hai detto che era un vettore di n+1 elementi)?

In setbuilder notazione, sarebbe qualcosa di simile a questo:

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

È fondamentalmente solo un prodotto Cartesiano di A k volte.Sulla carta, l'ho scritto giù come k un apice di Una (ho appena capito come fare che l'utilizzo di markdown).

Plus, è solo una matrice di ogni singolo vertice, senza riguardo per il adiacenza.