Entrar Ainda não tem acesso?
2
respostas

Ajuda com algoritmos para encontrar maior clique e menor cobertura de cliques em grafos não-direcionados

Referente ao curso Pesquisa operacional: entendendo as bases dos métodos de otimização

por Vitor Matos Soares
| 9.1k xp | 3 posts
Técnico de Planejamento e Controle da Manutenção II

Estou trabalhando em um projeto de algoritmos para meu curso de Projeto e Análise de Algoritmos, e estou enfrentando dificuldades em resolver duas tarefas relacionadas a grafos não-direcionados. Gostaria de pedir a ajuda de vocês para entender melhor como implementar esses algoritmos.

Preciso implementar usando backtracking e branch and brounch.

Tarefa 1: Encontrar o Maior Clique A primeira tarefa é encontrar o maior clique em um grafo não-direcionado. Um clique é um subconjunto de vértices onde cada par de vértices está conectado por uma aresta. O clique máximo é o clique que não pode ser aumentado adicionando mais vértices.

entrada:

c FILE: brock200_4.b p edge 200 13089 e 3 1 e 4 3 e 5 1 ...

saída:

17 160 27 116 164 126 53 64 78 191 138 11 92 37 70 185 18 28

Tarefa 2: Minimizar o Número de Cliques para Cobrir Todos os Vértices A segunda tarefa é minimizar o número de cliques necessários para cobrir todos os vértices do grafo. Isso significa encontrar a menor cobertura de cliques possível.

entrada: c FILE: C125.9.clq p col 125 6963 e 2 1 e 3 1 e 4 1 ...

saída:

7 24 15 18 21 29 31 35 36 44 49 54 64 68 72 74 82 83 92 ... 23 1 2 10 11 27 32 46 58 60 61 73 76 78 81 85 88 94 ... ...

2 respostas
por Monalisa Meyrelle de Sousa Silva
| 2079.9k xp | 4620 posts
Alura Scuba Team Monitoria Fórum Ops

Olá Vitor, tudo bem?

Que desafio, hein! haha. Neste caso, como é um projeto, externo eu não tenho como fornecer e testar o código. Mas vou deixar as etapas para que você possa se guiar no projeto.

  • Tarefa 1: Encontrar o Maior Clique

  • Backtracking

    1. Definir uma função recursiva que tenta adicionar um vértice ao clique atual.
    2. Verificar se o clique é válido (ou seja, todos os vértices no clique estão conectados entre si).
    3. Atualizar o maior clique encontrado se o clique atual for maior.
    4. Retroceder (backtrack) removendo o último vértice adicionado e tentando o próximo.

  • Branch and Bound

    1. Ordenar os vértices por grau decrescente (ou outra heurística).
    2. Usar uma função recursiva que tenta adicionar vértices ao clique atual.
    3. Calcular um limite superior para o tamanho do clique que pode ser obtido a partir do clique atual.
    4. Podar (cortar) ramos da busca que não podem melhorar a solução atual.

  • Tarefa 2: Minimizar o Número de Cliques para Cobrir Todos os Vértices

  • Backtracking

    1. Definir uma função recursiva que tenta adicionar um clique à cobertura atual.
    2. Verificar se a cobertura é válida (ou seja, todos os vértices estão cobertos).
    3. Atualizar a menor cobertura encontrada se a cobertura atual for menor.
    4. Retroceder (backtrack) removendo o último clique adicionado e tentando o próximo.

  • Branch and Bound

    1. Usar uma função recursiva que tenta adicionar cliques à cobertura atual.
    2. Calcular um limite inferior para o número de cliques necessários para cobrir os vértices restantes.
    3. Podar ramos da busca que não podem melhorar a solução atual.

Espero ter ajudado.

Qualquer dúvida, compartilhe no fórum.

Abraços e bons estudos!

Caso este post tenha lhe ajudado, por favor, marcar como solucionado ✓. Bons Estudos!
por Vitor Matos Soares
| 9.1k xp | 3 posts
Técnico de Planejamento e Controle da Manutenção II

Obrigado pela resposta. A tarefa 01 consegui implementar o backtracking e tive um resultado aceitável! Entretanto a tarefa 02 ainda não. E agora preciso usar o branch and bound.

O objetivo é encontrar o menor número de cliques dentro de um grafo, onde todos os nós precisam estar em um ( e somente em um) clique, mesmo que seja um clique de um único nó. (Essa foi a orientação do professor, fiquei meio confuso).