Ir ao conteúdo
  • Cadastre-se
avl

Ajuda com algoritmo vizinho mais proximo

Recommended Posts

E ai pessoal beleza?

O problema é o seguinte. Tenho uma matriz N x N (N é o numero de cidades) em que cada entrada é a distancia entre os pares de cidades. Só como exemplo, vamos supor que eu tenho a seguinte matriz:

999999 331 450

162 999999 970

856 424 999999

Na primeira linha, a distancia entre a cidade de índice 0 até 0 é 999999(padrão), a distancia entre a cidade de índice 0 ate 1 é 331, a distancia entra a cidade de índice 0 ate 2 é 450, e assim por diante. Tenho de encontrar um caminho satisfatório(menor distancia), passando por cada cidade exatamente uma vez e voltando para a cidade inicial do percurso(começa-se sempre pela cidade de índice 0). A saida do programa, para o exemplo acima seria:

0

1

2

0 (essa seria a volta para a cidade inicial, mas pode-se omitir essa parte)

Do jeito que eu fiz, a saída para o exemplo acima ta dando:

0

1

1

Pensei em fazer desse jeito, mas ta dando errado. Será que alguem poderia me dar uma ajuda? Se nao entenderem alguma parte, me fale.

Agradeço quem ajudar!


#include <stdio.h>
#include <stdlib.h>


int colunas (int a,int b,int *c){ //função para verificar se um elemento pertence a um vetor (será que ta certo?)


int i;

for (i=0;i<b;i++){
if (c[i]==a){
return 1;
}else{
return 0;
}
}
}


int main(int argc, char **argv){
int n = atoi(argv[1]); // esse é o numero de cidades
int i,j;

// alocando e inicializando a matriz com as distancias:
int **M = (int **)malloc(n*sizeof(int *));
for (i=0; i<n; i++){
M[i] = (int *)malloc(n*sizeof(int));
for (j=0; j<n; j++){
scanf("%d", &M[i][j]);
}
}



int *vetor2 = (int *)malloc(n*sizeof(int));
int menor,k,l;

menor=999999;
k=0;
l=0;
vetor2[0]=0;

for (i=k;i<n;i++){
for (j=0;j<n;j++){
if (M[i][j] < menor && colunas(k,n,vetor2)){ //preciso chamar essa função, pois se um elemento 'menor' estiver na mesma coluna do que um encontrado anteriormente, nao e valido

menor= M[i][j];
l=i;
k=j;

}

}

printf("%d\n",l);


}
}




Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×