7

Estou realizando a implementação do algoritmo de Christofides e de entrada recebo os dados da TSPLIB. o Algoritmo de Christofides tem os seguintes passos:

  1. Achar a árvore geradora mínima
  2. Achar todos os vértices impares (um número par de vértices)
  3. Achar o casamento mínimo perfeito dos vértices de grau impar
  4. Adicionar as arestas do casamento perfeito na AGM
  5. Encontrar um caminho euleriano dentro desse grafo

Eu fui fazendo o algoritmo e cheguei até o passo 5, porém, só ai percebi que o casamento dos vértices que eu estava encontrando não era o perfeito, que é feito nesse código a seguir:

int** adicionar_CM_na_AGM(int **m, int **agm, int qVgi, int *vGi,int n){
int menor =99999,v1=0,v2=0,verticeMenor;
int *aux = (int *) calloc(qVgi, sizeof(int));
for(int i=0; i<qVgi; i++)
{
    for(int j=0; j<qVgi; j++)
    {
        if(vGi[i] != vGi[j] && menor > m[vGi[i]][vGi[j]] && aux[vGi[i]] != 1 && aux[vGi[j]] != 1)
        {
            printf("%d O %d\n", i, m[vGi[i]][vGi[j]]);
            v1 = vGi[i];
            v2 = vGi[j];
            menor = m[vGi[i]][vGi[j]];
        }
    }
    aux[v1]= 1;//cria a situação de já visitados
    aux[v2]= 1;
    agm[v1][v2] = m[v1][v2];//adiciona na AGM as arestas dos vGi
    agm[v2][v1] = m[v2][v1];
    menor =9999;
}
return agm;

sendo : m: matriz de adjacência com as distâncias dos vértices

agm: matriz de adjacência da AGM de m

qVgi: inteiro que representa a quantidade de vértices de grau impar

vGi: vetor que contém os números dos vértices que tem grau impar

n: inteiro que representa o número de vértices total da matriz m

Gostaria de saber se alguém teria ideias para que eu consiga achar o casamento mínimo perfeito dos vértices de grau impar do meu grafo.

4
  • Uma árvore não tem, por definição, vértices de grau ímpar obrigatoriamente? As folhas dela? Commented 7/06/2018 às 15:30
  • A árvore só precisa ser acíclica e conexa, não? Commented 7/06/2018 às 15:39
  • Excetuando a raiz, o grau de todo vértice é 1 + número de filhos. Como folhas não tem filhos, seu grau é 1, portanto ímpar. Eu não conheço o algoritmo de Christofides, mas é que achei estranho essa seleção de vértices de grau par. Commented 7/06/2018 às 16:24
  • porém, podem existir graus dentro da árvore que também sejam impares, por exemplo um grau ligado a um numero par de folhas, porém o meu problema é na verdade uma forma de casar perfeitamente os vértices impares e adicionar arestas entre eles, para assim eu ter um grafo com um circuito euleriano. Commented 7/06/2018 às 21:54

1 Resposta 1

-2

Encontrar o casamento perfeito não é uma tarefa fácil, mas há várias maneiras de fazê-lo. Você pode tentar usar o algoritmo de Edmonds para casamentos perfeitos, que é muito eficiente e pode ser implementado em tempo polinomial. Outra opção é usar o algoritmo húngaro, que é um pouco mais complexo, mas também é eficiente.

Além disso, você pode tentar usar uma biblioteca de grafos já existente, como a Boost Graph Library, que tem algoritmos implementados para encontrar casamentos perfeitos em grafos. Espero que isso ajude!

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .