Em um exercício, preciso imprimir todas os caminhos possíveis entre cidades, sendo que as cidades são representadas por coordenadas x
e y
e que a última cidade é a cidade de partida. Lembrando que deve ser encontrados os menores caminhos para cada cidade inicial diferente. Essa parte do exercício foi feita. Por exemplo, para quatro cidades, tenho a seguinte saída:
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)
Sendo que 24 é o total de possibilidades.
Após essa parte, preciso indicar qual o melhor caminho, ou seja, o caminho com a menor distância, usando a fórmula de distância Euclidiana entre dois pontos. Criei duas funções para realizarem esse cálculo, como pode ser visto logo abaixo:
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]);
}
else
{
total = total + Distancia(C[i], C[i+1]);
}
}
return total;
}
Para descobrir a menor distância, implementei a seguinte função:
float MenorDistancia(Cidade *C, int numeroCidade)
{
int i;
float distancias[numeroCidade];
float menor = distancias[0];
for(i = 0; i < numeroCidade; i++)
{
distancias[i] = Distancias(C, numeroCidade);
if(distancias[i] < menor)
menor = distancias[i];
}
return menor;
}
Mas agora estou em dúvida em como implementar essas funções no funcionamento do programa como um todo. A primeira dúvida que tenho é se as funções estão corretas mesmo. Caso estejam, gostaria de saber se posso utilizá-las logo na função que cria essas possibilidades de caminhos, que é a função seguinte:
void Permuta(FILE *saida, Cidade *C, int *sequencia, int inicio, int
termino)
{
int i, j;
if(inicio == termino)
{
for(i = 0; i < termino; i++)
{
fprintf(saida, "(%d,%d) ", C[sequencia[i]].x,
C[sequencia[i]].y);
}
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));
}
}
}
Queria saber se teria como usar as funções no mesmo loop que imprime os caminhos e/ou se há uma forma melhor de se fazer.
o(n!) ~~= o(n^n)
, por isso que falei do exponencial. Sobre calcular a permutação, eu sou mais a favor de percorrer o grafo de cidades em profundidade e, ao chegar no destino, imprimir a lista do caminho. Acho mais direto do que calcular permutação.