C Caixeiro Viajante com 3 dimensões

[Victor Portugal]

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;
}

 

[malloc_]

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.

[isrnick]

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:

 

 

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.

[Victor Portugal]

@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!

 

[Victor Portugal]

@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;
}