Problema Caixeiro Viajante

Programação Java
#1

Bom dia pessoal.

Preciso implementar o algoritmo do caixeiro viajante, mas não sei como e nem qual o método mais simples de fazer (força bruta ou método guloso). Sei que é necessário uma matriz de distâncias, mas na verdade não sei como percorrê-la para encontrar o menor caminho usando o método de força bruta ou o método guloso.
Eu tinha começado a fazer de um jeito, mas depois percebi que estava tentando fazer de maneira errada e totalmente mais complicada.

Obs: Não estou pedindo nenhum código pronto, apenas uma luz, um pontapé inicial sobre como implementar usando um dos dois métodos, pois não estou conseguindo enxergar a solução.
Também já procurei artigos na internet sobre sua implementação, mas na maioria achei solução usando algoritmos genéticos, ciclo Hamiltoniano, ciclo de não sei mais o quê, etc.

Qualquer ajuda é bem-vinda!
Abraços.

#2

O algoritmo do caixeiro viajante é praticamente impossível de se resolver por força bruta. Você pode até tentar, mas a medida que o número de cidades aumentarem, o tempo irá aumentar exponencialmente.

Para a implementação desse algoritmo, você precisa de uma estrutura que diga:
a) Quais cidades existem;
b) Qual é a distância entre duas cidades.

O problema pode ser simplificado (em termos de implementação) se você partir do pressuposto que todas as cidades estão interconectadas entre si. Essa estrutura pode ser um simples array onde as linhas e colunas representam as cidades e os números do array representam as distâncias. É possível usar um número especial, como 0, para indicar que não há conexão entre duas cidades.

Essa estrutura é chamada de matriz de adjacência e é uma das formas de se representar um grafo.

O objetivo do algoritmo é, geralmente, descobrir qual é o menor caminho que faça o caixeiro passar por todas as cidades sem repetições. Algumas variações do problema incluem especificar qual vai ser a cidade inicial ou a final.

Uma das formas de resolver isso, é gerando uma matriz com as cidades em ordem. Por exemplo, digamos que você tenha as cidades A, B, C, D e E, e que “A”, e “E”, sejam os pontos de origem de destino.

Você poderia gerar a seguinte matriz:
Cidade[] cidades = {A, C, D, B, E};

Indicando que primeiro ele viajará de A até C, depois de C até D, depois de D até B, depois de B até E. Aí, basta usar sua estrutura para somar essas distâncias diretamente. (Vai na linha da cidade A e na coluna da cidade C, e ve que distância está lá. Repete o processo para as demais, até ter a distância total). Por força bruta, você teria que testar todas as permutações possíveis da matriz “cidades”, até encontrar a menor.

Técnicas que normalmente resolvem isso são os algoritmos de busca estocástica. Eles não garantem o melhor resultado, mas dão bons resultados. Dê uma olhada em algoritmos genéticos, por exemplo.

#3

Aqui tem um exemplo que fiz com algoritmos genéticos. Está em C#:

#4

Boa tarde a todos.
Sou novo no fórum. Pesquisei e vi que é um fórum com bastante material.
Mas vou ao que interessa. Estou precisando resolver esse problema também, utilizando força bruta. Li as dicas do ViniGodoy e tentei fazer. Fiz uma matriz aleatória para gerar as distâncias, mas não sei como fazer todas as combinações de caminhos, conforme explicado.
Alguém poderia me ajudar ?

#5

Considerando que as cidades estão numa String contendo sua ordem, por exemplo:

  • “ADBC”, sendo de “A” até “D”, de “D” até “B”, de “B” até “C”, use o algoritmo abaixo para gerar todas as permutações possíveis:

http://introcs.cs.princeton.edu/java/23recursion/Permutations.java.html

Depois basta pegar a distância entre as cidades e calcular o menor caminho.

#6

Ah…
Tinha faltando “string” aí né rsrs
não tinha entendido bem…
Vou tentar fazer com ele.
Muito obrigado ViniGodoy.

#7

Eu realmente não conheço muito de java.
Essa linha está correta ?
int N = Integer.parseInt(args[0]);

Tentei rodar mas ela apresentou erro.

#8

Consegui já.
tava vacilando aqui.
Obrigado

#9

A sintaxe está certa. Mas você está passando um inteiro de parâmetro na execução do seu programa?

#10

ViniGodoy,
desculpe o incomodo de novo…
mas como eu associo essas permutações a minha matriz bidimensional?
Deve ser algo simples, mas não consegui imaginar…
Nem precisa ter trabalho com código não, acho q qualquer dica, por simples q seja, deve me ajudar.
Se souber,
obrigado de novo.

#11

Você pode considerar na sua matriz que cada linha e coluna é uma cidade, e nos valores vc põe a distância entre as cidades.

Por exemplo, com as cidades 0, 1, 2 e 3 você teria uma matriz assim:

  0 1 2 3 
  --------
0 0 5 8 2
1 5 0 7 4
2 8 7 3 5
3 2 3 5 0

Assim, para viajar da cidade 0 até a cidade 1, você teria que percorrer 5 km (basta olhar na linha 0, coluna 1).

A distância da “volta” pode ser igual ou não. Por exemplo, veja que da cidade 1 para a 3 a distância é 4km, mas na volta, a distancia é só 3km. Verifique com o seu professor se ele quer considerar essa possibilidade, mas o algoritmo não muda em nada caso ele não queira.

Além dessa matriz, seu algoritmo terá que gerar as permutações possíveis entre as cidades. Nesse caso, você teria a String “0123” e as permutações seriam as possíveis rotas do caixeiro. No caso, para a String “0123” você teria a viagem:
Da cidade 0 até 1: 5km
Da cidade 1 até 2: 7km
Da cidade 2 até 3: 5km
Totalizando uma rota de 17km (verifique com seu professor se ele quer que o problema considere que o caixeiro termine na mesma cidade onde começou, o que acrescentaria mais uma rota de 3 até 0).

Ao encontrar a menor distância entre todas as permutações possíveis, você terá resolvido o problema.

#12

Entendi.
acho que juntando tudo, vou conseguir resolver.
muito obrigado pela ajuda. Obrigado pela explicação detalhada.

#13

Só verifique com seu professor quais restrições ele quer para o problema. Restrições comuns são:

  • Considerar a distância de ida e volta entre as cidades como iguais;
  • O usuário manualmente especificar o ponto de início ou de fim (ou ambos).

Não estranhe se para um número grande de cidades esse algoritmo for EXTREMAMENTE LENTO. Com 8 cidades você já vai ver que o computador tem trabalho para processar. O ideal, no futuro, é você adicionar no seu código uma forma de calcular o tempo total que o algoritmo levou processando.

Assim, a medida que você estudar os algoritmos de busca, vai poder compara-los em relação a performance. :wink:

De qualquer forma, a força bruta é um bom ponto de partida, pois é o único algoritmo capaz de resolver esse problema que dá como resultado a certeza do melhor caminho. Com esse número em mãos, você vai poder comparar os demais também em relação a qualidade da resposta.

#14

Sim. Vou verificar esses detalhes.
Entendi tudo o que me explicou, mas uma dúvida permanece.
seguindo o seu exemplo acima, vamos supor q fiz uma estrutura de repetição, acessei o primeiro valor q eu quero na matriz, joguei em uma variável para que eu possa somar outros valores futuramente. Até aí tudo bem. Mas não consegui captar a lógica para acessar a sequencia de elementos de cada permutação. (não sei se ficou clara minha dúvida). Pois não vvai ser como somar elementos de uma linha por exemplo, onde só preciso incrementar o contador em 1 unidade.
Entendendo isso, estaria resolvido. Desculpe se ficou complexa a pergunta.

#15

Digamos que você tenha o array “cidadesPermutadas” com todas as combinações possíveis. E esse array seja de Strings, como indiquei ali.

Digamos que você tenha um array bidimensional de doubles, com as distâncias, chamado distancias.

Para testar as duas primeiras cidades, da primeira permutação, você faria algo como:

int indiceCidade1 = cidadesPermutadas[0].getChar(0) - '0';
int indiceCidade2 = cidadesPermutadas[0].getChar(1) - '0';
double distancia = distancias[indiceCidade1] + distancia[indiceCidade2];

Agora, bastaria criar as repetições para percorrer todas as cidades e todas as permutações.

#16

Com isso eu resolvo cara. (de verdade agora).
Muito obrigado pela atenção e explicação.

#17

Resolvi Obrigado!

#18

Põe sua resolução aí para a posteridade. Assim você ajuda aos próximos (ao invés de só pedir ajuda). :wink:

#19

Desculpe ViniGodoy. É porque “deu mas não deu” certo.
Tive que mudar tudo e fazer outras partes antes.
Não deixarei de postar quando terminar.
até mais!

#20

O código não está muito bom. Fiz tudo um código bem rápido, dentro do construtor mesmo. Eu vou mudá-lo, mas futuramente. Como não vou ter tempo por enquanto, vou postá-lo abaixo. Talvez ajude alguém.

[code][code]package dominio;

public class Rota {
private int linha=0;
private int coluna=0;
private int menorCaminho=9999;
private String sMenorCaminho="";

public Rota(String s, int tam, int matriz[][]){//s==String completa com todas a permutacoes tam==tamanho de cada caminho(sem retorno)
           
    for (int i = 0; i <=s.length()-tam; i+=tam) {//numa mesma string,estão todas as permutações em sequencia (s)
        
        String subString = s.substring(i, i+tam);//criada uma substring de s chamada "subString", que terá cada caminho
        int primeiraPosicao=0;            
        int caminhoCompleto=0;
        String sCaminhoCompleto="";
        String sCaminhoCompletoComRetorno="";
        String sPrimeiraPosicao="";
        for (int j = 0; j < subString.length(); j++) {//percorrerá todo "um caminho" ao fim do FOR   
            int caminho=0;
            String sCaminho="";
            if (j==subString.length()-1) {//CCriada com o mesmo intuito do ELSE, porém, caso seja a ultima posicao
                //entrará nessa condição, para que a linha da matriz seja J e a coluna seja o primeiro elemento da sequencia
                //ou seja, o retorno
                char cLinha = subString.charAt(j);
                String sLinha = String.valueOf(cLinha);
                linha = Integer.parseInt(sLinha);
                coluna = primeiraPosicao;
            }
            else{//parte que pegará a primeira string, converterá para int e associará ela a um numero de linha na matriz
                //uma posição adiante, pegará o número de colunas
                char cLinha = subString.charAt(j);
                String sLinha = String.valueOf(cLinha);
                linha = Integer.parseInt(sLinha);
                char cColuna = subString.charAt(j+1);
                String sColuna = String.valueOf(cColuna);
                coluna = Integer.parseInt(sColuna);
                if (j==0) {
                    char cPrimeiraPosicao = subString.charAt(j);
                    sPrimeiraPosicao  = String.valueOf(cPrimeiraPosicao);
                    primeiraPosicao = Integer.parseInt(sPrimeiraPosicao);                        
                }
            }
            caminho = matriz[linha][coluna];  
            char cCaminho = subString.charAt(j);
            sCaminho = String.valueOf(cCaminho);
            caminhoCompleto = caminhoCompleto+caminho;
            sCaminhoCompleto = sCaminhoCompleto+sCaminho;
        }
        sCaminhoCompletoComRetorno = sCaminhoCompleto+sPrimeiraPosicao;
        //Formou-se um caminho completo
        if (caminhoCompleto<menorCaminho) {
            menorCaminho = caminhoCompleto;
            sMenorCaminho = sCaminhoCompletoComRetorno;
        }
    }        
    
    for (int i = 0; i < tam; i++) {
        for (int j = 0; j < tam; j++) {
            System.out.print(matriz[i][j]+" ");
        }
        System.out.println();
    }
    System.out.println("O menor distância percorrida é: "+menorCaminho);
            
}

}[/code]