projeto de algoritmos problema do clique

Question

Uma das atribuições da minha turma algoritmos é a concepção de um algoritmo de busca exaustiva para resolver o problema do clique. Isto é, dado um gráfico de tamanho n , o algoritmo é suposto para determinar se há um sub-grafo completo de tamanho k . Eu acho que eu comecei a resposta, mas eu não posso ajudar, mas acho que poderia ser melhorado. Aqui está o que eu tenho:

Versão 1

entrada : Um gráfico representado por uma matriz A [0, ... n -1], o tamanho k do subgráfico de encontrar.

saída : True se existe um subgrafo, False caso contrário

Algoritmo (em python-como pseudocódigo):

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

entrada : Uma matriz de adjacência de tamanho n por n, e k o tamanho do subgráfico para encontrar

saída :. Todos os subgrafos completo em um de tamanho k

Algoritmo (desta vez em funcional pseudocódigo / 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

Alguém tem quaisquer pensamentos, comentários ou sugestões? Isso inclui erros que eu poderia ter perdido, bem como maneiras de fazer isso mais legível (eu não estou acostumado a usar muito pseudocódigo).

Versão 3

Felizmente, eu falei com meu professor antes de enviar a tarefa. Quando eu mostrei a ele o pseudo-código que eu tinha escrito, ele sorriu e me disse que eu fiz maneira muito trabalho. Por um lado, eu não têm de apresentar pseudo-código; Eu só tinha que demonstrar que eu entendi o problema. E dois, ele foi querendo a solução de força bruta. Então o que eu transformou em algo parecido com isto:

entrada : Um gráfico G = (V, E), o tamanho da clique para encontrar k

saída : True se um clique existe, caso contrário false

Algoritmo :

1. Encontre o produto cartesiano V ^k .
2. Para cada tupla no resultado, testar se cada vértice está conectado a todos os outros. Se tudo está conectado, retorna true e sair.
3. Voltar falsa e sair.

Atualizar : segunda versão Adicionado. Eu acho que isso está ficando melhor, embora eu ainda não adicionou nenhum programação fantasia dinâmico (que eu saiba).

UPDATE 2 : Adicionado mais alguns comentários e documentação para fazer a versão 2 mais legível. Esta será provavelmente a versão que eu entregar hoje. Obrigado pela ajuda de todos! Eu gostaria de poder aceitar mais de uma resposta, mas eu aceito a resposta pela pessoa que me ajudou a mais. Vou deixar vocês sabem o que meu professor pensa.

Answer 1

Alguns comentários:

• Você só precisa considerar combinações de vértices k n-escolher-, nem todos os k-tuplas (n ^ k deles).
• connected(tuple) não parece certo. Não para você precisa redefinir unconnected dentro do loop?
• Como os outros têm sugerido, há melhores maneiras de brute-forcing isso. Consideremos a seguinte relação recursiva: A (k + 1) -subgraph é uma clique se os primeiros k vértices formar um bando e vértice (k + 1) é adjacente a cada uma das primeiras k vértices. Você pode aplicar este em duas direções:
  • Comece com um 1-clique e gradualmente expandir a camarilha até obter o tamanho desejado. Por exemplo, se m é o maior vértice na panelinha atual, tentar adicionar vértice {m + 1, m + 2, ..., n-1} para obter um clique que é um vértice maior. (Isto é semelhante a uma passagem de árvore em profundidade, onde os filhos de um nó de árvore são os vértices maiores do que o maior vértice na panelinha atual.)
  • Comece com um subgrafo do tamanho e verificação desejado se for um clique, usando a relação recursiva. Configurar uma tabela memoization para armazenar os resultados ao longo do caminho.
• (sugestão aplicação) Use uma matriz de adjacência (0-1) para representar arestas no gráfico.
• (poda inicial) Jogue fora todos os vértices com grau menor do que k.

Answer 2

Uma vez eu implementado um algoritmo para encontrar todos os cliques maximais em um gráfico, que é um problema semelhante ao seu. A maneira que eu fiz foi com base neste artigo: http://portal.acm.org /citation.cfm?doid=362342.362367 - é descrita uma solução retrocesso que eu achei muito útil como um guia, embora eu mudei bastante com esse papel. Você precisa de uma assinatura para chegar a isso, porém, mas presumo sua Universidade teria um disponível.

Uma coisa sobre esse papel, porém, é que eu realmente acho que eles deveriam ter chamado o "não definida" o "set já considerado" porque ele está muito confuso contrário.

Answer 3

O algoritmo "para cada k-tuple de vértices, se for um clique, em seguida, retornar true" funciona com certeza. No entanto, é a força bruta, o que provavelmente não é o que um algoritmos curso está procurando. Em vez disso, considere o seguinte:

1. Cada vértice é um 1-clique.
2. Para cada 1-clique, cada vértice que se conecta ao vértice nos contribui com 1-clique para a 2-clique.
3. Para cada 2-clique, cada vértice que se conecta a cada vértice nos contribui 2-clique para um 3-clique.
4. ...
5. Para cada (k-1) -clique, cada vértice que se conecta a cada vértice no contribui (k-1) para uma pequena associação k-clique.

Esta ideia pode levar a uma melhor abordagem.

Answer 4

Talvez tente um técnica de programação dinâmica .

Answer 5

É incrível o que digitando as coisas como uma questão irá mostrar-lhe sobre o que você acabou de escrever. Esta linha:

P = A x A x A  //Cartesian product

deve ser esta:

P = A ^k // produto cartesiano

O que você quer dizer com A ^ k? Você está tomando um produto matriz? Se assim for, é uma matriz de adjacência (você disse que era um conjunto de n + 1 elementos)?

Na notação setbuilder, seria algo parecido com isto:

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

É basicamente apenas um produto cartesiano de k vezes Um tomadas. No papel, eu escrevi para baixo como k sendo um sobrescrito de A (eu só agora descobriu como fazer isso usando remarcação).

Além disso, A é apenas uma matriz de cada vértice indivíduo sem levar em conta adjacência.