4

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.

5
  • 3
    Você sabe que tem um número exponencial de caminhos possíveis, correto? Isso se ignorar loops, que aí vai ao infinito... 21/09/2017 às 13:55
  • 2
    O que entendi do problema é que o número de caminhos possíveis é o fatorial do número de cidades. Correto? No exercício pede para que encontre esses caminhos possíveis e suas menores distâncias de 4 até 14 cidades. Para 14 cidades, sei que são muitas possibilidades. Usei o exemplo de 4 por ser menor.
    – Renan
    21/09/2017 às 13:59
  • ok, é fatorial, mas 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. 21/09/2017 às 14:05
  • 2
    Todos os caminhos possíveis para 14 cidades são 14! = 87178291200. Esse tipo de soluções rapidamente ficam inviáveis, e por isso é como de serem utilizados algoritmos de inteligencia artificial como simulated annealing entre outros
    – Isac
    21/09/2017 às 14:06
  • Sim. Realmente fica inviável. Mas acho que a real intenção do exercício é mostrar esses tipos de possibilidade.
    – Renan
    21/09/2017 às 14:10

0

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

Pesquise outras perguntas com a tag .