1

O exercício pede para que eu imprima, em um arquivo, todos os possíveis caminhos entre n cidades, sendo que o final é sempre o ponto de partida e que cada cidade seja representada como coordenadas (x,y). Essa primeira parte eu consegui fazer, tendo como resultado o seguinte arquivo:

24
(1,10)  (4,4)   (5,1)   (2,0)   (1,10)
(1,10)  (4,4)   (2,0)   (5,1)   (1,10)
(1,10)  (5,1)   (4,4)   (2,0)   (1,10)
(1,10)  (5,1)   (2,0)   (4,4)   (1,10)
(1,10)  (2,0)   (5,1)   (4,4)   (1,10)
(1,10)  (2,0)   (4,4)   (5,1)   (1,10)
(4,4)   (1,10)  (5,1)   (2,0)   (4,4)
(4,4)   (1,10)  (2,0)   (5,1)   (4,4)
(4,4)   (5,1)   (1,10)  (2,0)   (4,4)
(4,4)   (5,1)   (2,0)   (1,10)  (4,4)
(4,4)   (2,0)   (5,1)   (1,10)  (4,4)
(4,4)   (2,0)   (1,10)  (5,1)   (4,4)
(5,1)   (4,4)   (1,10)  (2,0)   (5,1)
(5,1)   (4,4)   (2,0)   (1,10)  (5,1)
(5,1)   (1,10)  (4,4)   (2,0)   (5,1)
(5,1)   (1,10)  (2,0)   (4,4)   (5,1)
(5,1)   (2,0)   (1,10)  (4,4)   (5,1)
(5,1)   (2,0)   (4,4)   (1,10)  (5,1)
(2,0)   (4,4)   (5,1)   (1,10)  (2,0)
(2,0)   (4,4)   (1,10)  (5,1)   (2,0)
(2,0)   (5,1)   (4,4)   (1,10)  (2,0)
(2,0)   (5,1)   (1,10)  (4,4)   (2,0)
(2,0)   (1,10)  (5,1)   (4,4)   (2,0)
(2,0)   (1,10)  (4,4)   (5,1)   (2,0)

Onde 24 é a quantidade de possibilidades.

Após essa primeira parte do exercício, preciso calcular o menor caminho possível, ou seja, com a menor distância, através da fórmula de distância Euclidiana, e imprimir esses caminhos, sendo que devo fazer isso para cada ponto de partida diferente (cidades iniciais diferentes). Para isso, implementei as seguintes funções:

float Distancia(Cidade cA, Cidade cB)
{
    int distanciaX = pow(cA.x - cB.x, 2);
    int distanciaY = pow(cA.y - cB.y, 2);
    float distancia = sqrt(distanciaX + distanciaY);
    return distancia;
}

float Distancias(Cidade *C, int numeroCidades)
{
    int i;
    float total = 0;
    for(i = 0; i < numeroCidades; i++)
    {
        if(i == numeroCidades - 1)
        {
            total = total + Distancia(C[i], C[0]);
            printf("Distancia: %f\n", Distancia(C[i], C[0]));
        }
        else
        {
            total = total + Distancia(C[i], C[i+1]);
            printf("Distancia: %f\n", Distancia(C[i], C[i+1]));
        }
    }
    return printf("Distancia Total: %f\n\n", total);
}

Eu peço para a função Distancias imprimir os resultados na tela para me ajudar inicialmente, pois, na verdade, é preciso imprimi-los em um outro arquivo. Após essas duas funções, utilizei uma função de permutação (utilizada em um outro exercício) para imprimir todos os caminhos possíveis, mostrados acima. A função é a seguinte:

void Troca(int *x, int *y)
{
    int aux;
    aux = *x;
    *x = *y;
    *y = aux;
}

void Permuta(FILE *saida, Cidade *C, int *sequencia, int inicio, int 
termino)
{
    int i, j;
    float distancias[TotalViagens(termino)];
    if(inicio == termino)
    {
        for(i = 0; i < termino; i++)
        {
            fprintf(saida, "(%d,%d)\t", C[sequencia[i]].x, 
C[sequencia[i]].y);
            distancias[i] = Distancias(C, termino);
        }
        fprintf(saida, "(%d,%d)\n", C[sequencia[0]].x, C[sequencia[0]].y);
    }
    else
    {
        for(j = inicio; j < termino; j++)
        {
            Troca((sequencia+inicio), (sequencia+j));
            Permuta(saida, C, sequencia, inicio+1, termino);
            Troca((sequencia+inicio), (sequencia+j));
        }
    }
}

Dentro dessa mesma função, criei a variável distancias para guardar os valores das distâncias de todas as viagens possíveis (considerando que o tamanho do vetor TotalViagens(termino) é calculado por essa função). Sendo assim, coloquei esse vetor distancias no loop que vai de 0 ao número total de cidades que, na função, é chamado de termino. Me perdi um pouco na lógica da função, mas a coloquei nesse loop pelo mesmo motivo do loop realizar a impressão de todas os caminhos possíveis, portanto, imagino eu que, logo após imprimir um caminho, a variável distancias[i] receberá o valor retornado pela função Distancias. O resultado que tenho é o cálculo da mesma distância todas as vezes (96 vezes para o total de 4 cidades e 24 caminhos possíveis). A saída que tenho é a seguinte:

Distancia: 6.708204
Distancia: 3.162278
Distancia: 3.162278
Distancia: 10.000000
.
.
.

Ou seja, é impresso aquele mesmo resultado 96 vezes.

Gostaria de saber porquê o número total de distâncias está multiplicado pelo número de cidades (24x4) e as possibilidades calculadas são sempre as mesmas.

2
  • Tenta procurar sobre BFS (Breadth-first search), ou busca em largura em português. Acho que resolve seu problema sem muita dor de cabeça. Commented 24/09/2017 às 22:34
  • Eu pesquisei um pouco sobre e vi que BFS tem a ver com grafos, certo? Mas nessa implementação que fiz, não implementei nada de grafo, apenas estrutura de coordenadas (x,y). A minha dúvida é mais sobre a lógica e o porquê de estar imprimindo todas essas 96 vezes
    – Renan
    Commented 26/09/2017 às 14:55

0

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

Pesquise outras perguntas com a tag .