Ir ao conteúdo
  • Cadastre-se
Victor Portugal

C RESOLVIDO Caixeiro Viajante com 3 dimensões

Recommended Posts

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

Compartilhar este post


Link para o post
Compartilhar em outros sites

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

Compartilhar este post


Link para o post
Compartilhar em outros sites

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

Compartilhar este post


Link para o post
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

Compartilhar este post


Link para o post
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

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

×