Ir ao conteúdo
  • Cadastre-se

C Caixeiro Viajante com 3 dimensões


Victor Portugal
Ir à solução Resolvido por isrnick,

Posts recomendados

Fala pessoal, boa tarde. Estou com um trabalho para fazer e não estou conseguindo completá-lo, então, queria ver se vocês conseguem me ajudar.

O trabalho consiste no código do caixeiro viajante com 3 dimensões, vou deixar o meu código com 2 dimensões aqui para olharem e se possível, me ajudarem a 'colocar a terceira dimensão' nele.

Valeu!

 

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

struct cidade {
    char nome;
    float x, y;
};

int main(int argc, char *argv[]) { //argc quantidade de argumentos e argv os argumentos
    int i, j, n, letra = 65; //65 e a letra A da tabela ASCII
    printf("\nQuantas Cidades? ");
    scanf("%d", &n);
    struct cidade cid[n]; //vetor de estrutura de cidades
    float distancia[n][n], x1, x2, y1, y2;
    srand(time(NULL));
    for (i = 0; i < n; i++) {
        cid[i].nome = letra + i; //nome da cidade de A (65) ate A+n
        x1 = rand() % 100; //entre 0 e 99
        x2 = (rand() % 20) + 1; //1 e 20
        y1 = rand() % 100;
        y2 = (rand() % 20) + 1;
        cid[i].x = x1 / x2; //coordenada x da cidade 
        cid[i].y = y1 / y2; //coordenada y da cidade
    }
    for (i = 0; i < n; i++) {
        printf("\n%c(%.2f, %.2f)", cid[i].nome, cid[i].x, cid[i].y); //imprime as coordenadas da cidade
    }
    printf("\n\n");
    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++) {
            distancia[i][j] = sqrt((pow((cid[i].x - cid[j].x), 2) + pow((cid[i].y - cid[j].y), 2))); //calculo da distancia por pitagoras
            distancia[j][i] = distancia[i][j]; //espelhar a matriz
        }
    }
    for (i = 0; i < n; i++) {
        printf("\t%c", letra + i); //imprime o cabecalho
    }
    printf("\n\n");
    for (i = 0; i < n; i++) {
        printf("%c\t", letra + i); //imprime a primeira coluna com a letra da cidade
        for (j = 0; j < n; j++) {
            printf("%.2f\t", distancia[i][j]); //imprime a distancia entre cidades
        }
        printf("\n\n");
    }
    int xMin, yMin; //armazena as coordenadas da menor distancia
    float menorValor, caminho[n][n]; //menor distancia e caminho a seguir 
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            caminho[i][j] = 0; //inicializa a matriz de caminhos
        }
    }
    int todas = 0, k;
    char vetCam[n]; //nome das cidades
    printf("\nDe qual cidade deseja partir?\n0 a %d ", n - 1);
    scanf("%d", &i);
    int v = i; //cidade inicial tem que ser a final
    float tmp[n];
    for (k = 0; k < n; k++) {
        tmp[k] = distancia[i][k]; //vetor de distancias temporarias
        distancia[k][i] = 0; //zerando a coluna da cidade de partida 
    }
    while (todas < n) {
        vetCam[todas] = cid[i].nome;
        todas++;

        menorValor = 1000;
        for (j = 0; j < n; j++) {
            if ((distancia[i][j] < menorValor) && (distancia[i][j] != 0)) {
                xMin = i;
                yMin = j;
                menorValor = distancia[i][j];
            }
        }
        i = yMin;
        caminho[xMin][yMin] = distancia[xMin][yMin];
        if (n > todas + 1) {
            for (k = 0; k < n; k++) {
                distancia[k][i] = 0;
            }
        } else {
            caminho[i][v] = tmp[i];
        }
    }
    printf("\nCAMINHOS\n\n");
    for (i = 0; i < n; i++) {
        printf("\t%c", letra + i);
    }
    printf("\n\n");
    for (i = 0; i < n; i++) {
        printf("%c\t", letra + i);
        for (j = 0; j < n; j++) {
            printf("%.2f\t", caminho[i][j]);
        }
        printf("\n\n");
    }
    for (k = 0; k < n; k++) {
        printf("%c --> ", vetCam[k]);
    }
    vetCam[n - 1] = cid[v].nome;
    printf("%c", vetCam[n - 1]);
    printf("\n\n");
    return 0;
}

 

  • Curtir 1
Link para o comentário
Compartilhar em outros sites

  • 5 semanas depois...

Fala Victor, tudo bom?

Eu vi teu comentário no post do Cristiano mas isto aqui é muito avançado pra mim, porém, outro dia eu vi alguém falar sobre grafos e o algorítimo de Dijkstra. Ainda não me aprofundei nesse estudo mas vi um vídeo que eles aplicaram o algorítimo em robôs que jogavam futebol, o objetivo era fazer com que os robôs encontrassem o melhor caminho pra direcionar a bola até o gol do oponente.

 

Levando em consideração que o problema do Caixeiro viajante é achar a menor rota entre as cidades e então voltar a cidade de origem, talvez esse algorítimo te ajude.

 

PS: Existe uma chance enorme desse algorítimo já estar no seu código, eu só li sobre o conceito e vi algumas aplicações, não vi o código em C/C++. Se o código ja estiver no seu código, eu passo vergonha, mas tudo bem rs.

  • Curtir 2
Link para o comentário
Compartilhar em outros sites

  • Solução

Se entendi o que quer bastaria adicionar a dimensão z para indicar altura da cidade e usar a formula para calcular distância entre 2 pontos em 3 dimensões:

 

image.png.3979a2e04a451d592f19b841b0d3d47b.png

 

Se o código já está funcionando corretamente para 2 dimensões creio que o restante do código não muda, pois não usa mais as coordenadas das cidades, só as distâncias entre elas.

  • Curtir 2
  • Obrigado 1
Link para o comentário
Compartilhar em outros sites

@malloc_ Fala aí, então, a parte de encontrar a menor distância já está feito, eu estou com dificuldade de encaixar a terceira dimensão e principalmente a equação para calcular com 3 dimensões. Valeu aí!

@isrnick No caso eu adicionaria o altura(Z) nas variáveis e depois substituiria a equação no código por essa que você mandou, certo? O código está funcionando direitinho para 2 dimensões. Se eu entendi o que você quis dizer, acho que sei como fazer. Vou tentar aqui depois e volto para passar o feedback, valeu aí.

Abraço!

 

  • Curtir 3
Link para o comentário
Compartilhar em outros sites

@isrnick então, acho que a sua dica resolveu o meu problema. Vou deixar o código completo abaixo, caso alguém tenha mais dicas para melhorar o código e caso alguém precisa do código em algum momento né...

Valeu aí, parceiro. Abraço!

Segue código:

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

struct cidade {
    char nome;
    float x, y, z;
};

int main(int argc, char *argv[]) { //argc quantidade de argumentos e argv os argumentos
    int i, j, n, letra = 65; //65 e a letra A da tabela ASCII
    printf("\nQuantas Cidades? ");
    scanf("%d", &n);
    struct cidade cid[n]; //vetor de estrutura de cidades
    float distancia[n][n], x1, x2, y1, y2, z1, z2;
    srand(time(NULL));
    for (i = 0; i < n; i++) {
        cid[i].nome = letra + i; //nome da cidade de A (65) ate A+n
        x1 = rand() % 100; //entre 0 e 99
        x2 = (rand() % 20) + 1; //1 e 20
        y1 = rand() % 100;
        y2 = (rand() % 20) + 1;
        z1 = rand() % 100;
        z2 = (rand() % 20) + 1;
        cid[i].x = x1 / x2; //coordenada x da cidade 
        cid[i].y = y1 / y2; //coordenada y da cidade
        cid[i].z = z1 / z2; //coordenada z da cidade
    }
    for (i = 0; i < n; i++) {
        printf("\n%c(%.2f, %.2f, %.2f)", cid[i].nome, cid[i].x, cid[i].y, cid[i].z); //imprime as coordenadas da cidade
    }
    printf("\n\n");
    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++) {
            distancia[i][j] = sqrt((pow((cid[i].x - cid[j].x), 2) + pow((cid[i].y - cid[j].y), 2) + pow((cid[i].z - cid[j].z), 2))); //calculo da distancia por pitagoras
            distancia[j][i] = distancia[i][j]; //espelhar a matriz
        }
    }
    for (i = 0; i < n; i++) {
        printf("\t%c", letra + i); //imprime o cabecalho
    }
    printf("\n\n");
    for (i = 0; i < n; i++) {
        printf("%c\t", letra + i); //imprime a primeira coluna com a letra da cidade
        for (j = 0; j < n; j++) {
            printf("%.2f\t", distancia[i][j]); //imprime a distancia entre cidades
        }
        printf("\n\n");
    }
    int xMin, yMin, zMin; //armazena as coordenadas da menor distancia
    float menorValor, caminho[n][n]; //menor distancia e caminho a seguir 
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            caminho[i][j] = 0; //inicializa a matriz de caminhos
        }
    }
    int todas = 0, k;
    char vetCam[n]; //nome das cidades
    printf("\nDe qual cidade deseja partir?\n0 a %d ", n - 1);
    scanf("%d", &i);
    int v = i; //cidade inicial tem que ser a final
    float tmp[n];
    for (k = 0; k < n; k++) {
        tmp[k] = distancia[i][k]; //vetor de distancias temporarias
        distancia[k][i] = 0; //zerando a coluna da cidade de partida 
    }
    while (todas < n) {
        vetCam[todas] = cid[i].nome;
        todas++;

        menorValor = 1000;
        for (j = 0; j < n; j++) {
            if ((distancia[i][j] < menorValor) && (distancia[i][j] != 0)) {
                xMin = i;
                yMin = j;
                menorValor = distancia[i][j];
            }
        }
        i = yMin;
        caminho[xMin][yMin] = distancia[xMin][yMin];
        if (n > todas + 1) {
            for (k = 0; k < n; k++) {
                distancia[k][i] = 0;
            }
        } else {
            caminho[i][v] = tmp[i];
        }
    }
    printf("\nCAMINHOS\n\n");
    for (i = 0; i < n; i++) {
        printf("\t%c", letra + i);
    }
    printf("\n\n");
    for (i = 0; i < n; i++) {
        printf("%c\t", letra + i);
        for (j = 0; j < n; j++) {
            printf("%.2f\t", caminho[i][j]);
        }
        printf("\n\n");
    }
    for (k = 0; k < n; k++) {
        printf("%c --> ", vetCam[k]);
    }
    vetCam[n - 1] = cid[v].nome;
    printf("%c", vetCam[n - 1]);
    printf("\n\n");
    return 0;
}

 

  • Curtir 1
Link para o comentário
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisa ser um usuário 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 comunidades 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

×
×
  • Criar novo...