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.