Caixeiro viajante: caminho mais curto

[Samuel Cunha]

Boas pessoal. Estou a fazer um trabalho envolvendo o problema do caixeiro viajante. Este problema consiste em determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem. Primeiro fiz a minha matriz de forma manual e aleatoria. Eu já tenho boa parte do programa feito mas agora falta o mais dificil que é fazer o caminho mais curto, por exemplo temos 5 cidades e partimos da cidade1 voltando à mesma mas fazendo o percurso no menor trajeto possível, ou seja pretendo fazer vários trajetos fazendo swaps e depois identificar qual o mais curto. Será que poderiam dar uma dica para tentar fazer essa parte? 

Muito obrigado, deixo aqui parte do meu código feito.

Program TrabalhoProgramacao;                                     //Nome do Programa
 Uses Crt;
 const
     MAXCID = 25;                                                             //Constantes: constante do máximo de cidades
type
   matriz = array[1..MAXCID, 1..MAXCID] of integer;
var
 Opcao, numCidade : Integer;
 sair : boolean;
 distancias : matriz;
function LerCidades( var n : integer ) : Boolean;          // função para a leitura das cidades
begin
     writeln('Indique o numero de cidades ( maximo ', MAXCID, ' cidades:):');  // Indicação do número de cidades
     readln(n);
     if (n <= MAXCID) then
        LerCidades := true   // Lê o número introduzido
     else
         writeln('Introduziu mais que 25 cidades! Tente novamente!');
         LerCidades := false;
     readln;                                                          // Se o número de cidades for maior que 25 não executa
end;

procedure LimparMatriz( var distMatriz : matriz; nCidades : integer);  // procedimento para limpeza da matriz
var
   x, y : integer;
begin
     for x := 1 to nCidades do begin
         for y := 1 to nCidades do begin
             distMatriz[x][y] := 0;
         end;
     end;
end;

procedure EscreverMatriz( var distMatriz : matriz; nCidades : integer);  // procedimento para a escrita da matriz
var
   x, y : integer;
begin
     for x := 1 to nCidades do
         begin
              writeln;
                      for y := 1 to nCidades do
              begin
                   write( distMatriz[x][y]:2 );
              end;
     end;
end;
//Introduzir as distâncias
procedure PreencherManualMatriz( var distMatriz : matriz; nCidades : integer);             // procedimento para preenchimento da matriz de forma MANUAL
var
   x, y : integer;
begin
     writeln('           ************************************************************');
     writeln('           Atencao: distancias entre mesmas cidades e 0!');
     writeln('           ************************************************************');
     for x := 1 to (nCidades - 1) do
     begin
         writeln;
         for y := (x + 1) to nCidades do
         begin
               if x <> y then
                  begin
                       writeln('Introduza a distancia entre ', x ,  ' e ', y);
                       readln(distMatriz[x][y]);
                       distMatriz[y][x] := distMatriz[x][y];
                  end;
         end;
     end;
     EscreverMatriz(distancias, numCidade);
     readln;
end;
procedure PreencherRandomMatriz( var distMatriz : matriz; nCidades : integer);   // procedimento para preenchimento da matriz de forma ALEATÓRIA
var
   x, y : integer;
begin
     writeln('                   *********************************************');
     writeln('                   Atencao: distancias entre mesmas cidades e 0!');
     writeln('                   *********************************************');
     for x := 1 to (nCidades - 1) do
     begin
         writeln;
         for y := (x + 1) to nCidades do
         begin
                  begin
                       distMatriz[x][y] :=random(9);                // exemplo ate 9 quilometros de distancia
                       distMatriz[y][x] := distMatriz[x][y];
                  end;
         end;
     end;
     EscreverMatriz(distancias, numCidade);
     readln;
end;
Begin  // COMEÇO DO PROGRAMA
sair := false;
     while sair = false do
     begin
     clrscr;
            writeln(' opcao 1 : Ler as cidades');write('');
            writeln(' opcao 2 : Escrever matriz');
            (' opcao 3 : Preencher matriz manualmente');
            writeln(' opcao 4 : Preencher matriz aleatoriamente');
            writeln(' opcao 5 : Sair');
            readln(opcao);
            writeln;
Case Opcao of
    1 : LerCidades(numCidade);
    2 : EscreverMatriz(distancias, numCidade);
    3 : PreencherManualMatriz(distancias, numCidade);
    4 : PreencherRandomMatriz(distancias, numCidade);
    5 : sair := true;
                     else
                         begin
                              writeln('Opcao invalida! Tente novamente!');
                              writeln;
                              readln;
                         end;
end;
    end;
end

[Warrior]

Podes ser mais claro na tua dúvida?

[Samuel Cunha]

11 horas atrás, Warrior disse:

Podes ser mais claro na tua dúvida?

Sim vou tentar explicar melhor. No meu programa já tenho uma função que leia o número de cidades que eu quero e um procedure que leia as distâncias que eu quero. Posto isto a minha dúvida era, depois de ter posto as distâncias eu quero fazer um trajeto envolvendo estas cidades com as distâncias que pus e no fim fazer qual dos trajetos tem o caminho mais curto. Para fazer isto tenho que fazer arrays ou funções? Essa sim é a minha dúvida, não sei como fazer isso.

[Warrior]

Vais ter que usar as duas coisas, arrays e funções 🙂.

O teu objectivo é encontrar um algoritmo que resolva o problema. O problema do caixeiro viajante é NP-hard, o que significa que (em alguns casos) só tentando todas as soluções possíveis é que consegues descobrir qual o caminho mais curto. De que forma é que podes tentar todas as soluções possíveis? Pensa em algo recursivo.

Pela forma como colocas as questões e a linguagem que usas, temo que o problema seja um pouco puxado para o teu nível actual. Vais ter que te aplicar.

[Samuel Cunha]

2 horas atrás, Warrior disse:

Vais ter que usar as duas coisas, arrays e funções 🙂.

O teu objectivo é encontrar um algoritmo que resolva o problema. O problema do caixeiro viajante é NP-hard, o que significa que (em alguns casos) só tentando todas as soluções possíveis é que consegues descobrir qual o caminho mais curto. De que forma é que podes tentar todas as soluções possíveis? Pensa em algo recursivo.

Pela forma como colocas as questões e a linguagem que usas, temo que o problema seja um pouco puxado para o teu nível actual. Vais ter que te aplicar.

Muito obrigado, já consegui fazer o que pretendia 😁

[Warrior]

Óptimo! Deixa o código completo se quiseres comentários.