Jump to content
Samuel Cunha

Caixeiro viajante: caminho mais curto

Recommended Posts

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

 

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

  • Vote 1

Share this post


Link to post
Share on other sites
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 :cheesygrin:

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.