1. java
  2. android
  3. c#
  4. .net
  5. javascript
  6. php
  7. jquery
  8. html
  9. sql

Como resolver o problema do cacheiro viajante

Pessoal boa noite , estou implementando o código do caixeiro viajante no Java ,já estou conseguindo gerar os pontos aleatoriamente no JFRAME mas não estou conseguindo calcular a melhor rota , alguém poderia me ajudar? segue em anexo o código elaborado até o momento .

package caixeiro2017;

import javax.swing.JFrame;

public class Caixeiro2017 {

    public static void main(String[] args) {
       Pontos p = new Pontos(4,640,480);
       JFrame pto = new JFrame("Pontos Gerados");
       pto.add(p);
       pto.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
       pto.setSize(640,480);
       pto.setVisible(true);


    }

}
package caixeiro2017;

import java.awt.Graphics;
import java.util.Random;
import javax.swing.JPanel;

public class Pontos extends JPanel {
    private int[][] coordenadas;// guardar as coordenadas x e y de cada ponto 
    private double[][] custos;// objetivo mostrar a distancia de uma cidade para qualquer outro cidade
    private int vertices;
    private int largura;
    private int altura;


    public int[][] getCoordenadas() {
        return coordenadas;
    }

    public void setCoordenadas(int[][] coordenadas) {
        this.coordenadas = coordenadas;
    }

    public double[][] getCustos() {
        return custos;
    }

    public void setCustos(double[][] custos) {
        this.custos = custos;
    }

    public int getVertices() {
        return vertices;
    }

    public void setVertices(int vertices) {
        this.vertices = vertices;
    }

    public int getLargura() {
        return largura;
    }

    public void setLargura(int largura) {
        this.largura = largura;
    }

    public int getAltura() {
        return altura;
    }

    public void setAltura(int altura) {
        this.altura = altura;
    }

    public void paintComponent(Graphics g){
        super.paintComponent(g);
        //Plotando todos os vertices gerando aleatoriamente
        int x,y;
        for(int i = 0; i< this.vertices; i++){
            x = this.coordenadas[i][0];
            y = this.coordenadas[i][1];
            g.fillOval(x, y, 7, 7);

        }
        // traçando uma linha reta unindo todos os pontos 
        int x1, x2, y1, y2;

       for( int i= 0 ; i < this.vertices; i ++){
            for (int j = 0 ; j < this.vertices; j++){
               if(i!= j){

                    x1 = this.coordenadas[i][0];
                    x2 = this.coordenadas[j][0];


                    y1 = this.coordenadas[i][1];
                    y2 = this.coordenadas[j][1]; 

                    g.drawLine(x1, y1, x2, y2);

               }

            }

        }
    }

     public Pontos(int vertices, int largura, int altura) {
        this.vertices = vertices;
        this.largura = largura;
        this.altura = altura;

        this.coordenadas = new int[vertices][2];
        this.custos = new double[vertices][vertices];
        gerar_vertices();
        CalculaCustos();
    }

    private void gerar_vertices(){
        Random r = new Random();

        //Gerando todos os vértices
        int x,y;
        for(int i=0;i<this.vertices; i++){
            x = r.nextInt(this.largura);
            y = r.nextInt(this.altura);

            this.coordenadas[i][0] = x;
            this.coordenadas[i][1] = y;
        }
    }


    private void CalculaCustos(){

        double a, b, h, x1, y1 , x2, y2;

        for( int i= 0 ; i < this.vertices; i ++){
            for (int j = 0 ; j < this.vertices; j++){
                x1 = this.coordenadas[i][0];
                x2 = this.coordenadas[j][0];


                y1 = this.coordenadas[i][1];
                y2 = this.coordenadas[j][1];

                a = Math.abs(x2 -x1);
                b = Math.abs(y2 - y1);

                h  = Math.sqrt( a * a + b * b);

                this.custos[i][j] = h;


            }
        }
    }

}
package caixeiro2017;



public class vizinho_Mais_Proximo {

   private double[] custos;
   private int ponto_partida;
   private int[] rota;

    public vizinho_Mais_Proximo(double[] custos, int ponto_partida) {
        this.custos = custos;
        this.ponto_partida = ponto_partida;

        this.rota = new int [this.custos.length];// defidindo o tamanho do vetor rota 
        calcula_rota();


    }

    private void calcula_rota(){
        // ESVAZINDO OS VETOR ROTA
        for( int i= 0 ; i < this.custos.length; i ++)
        {
            this.rota[i] = -1;

        }

        // ponto de partida é a primeira posição do vetor
        this.rota[0]= this.ponto_partida;


    }


    public double[] getCustos() {
        return custos;
    }

    public void setCustos(double[] custos) {
        this.custos = custos;
    }

    public int getPonto_partida() {
        return ponto_partida;
    }

    public void setPonto_partida(int ponto_partida) {
        this.ponto_partida = ponto_partida;
    }

    public int[] getRota() {
        return rota;
    }

    public void setRota(int[] rota) {
        this.rota = rota;
    }



}
  1. Você vai ver essas setas em qualquer página de pergunta. Com elas, você pode dizer se uma pergunta ou uma resposta foram relevantes ou não.
  2. Edite sua pergunta ou resposta caso queira alterar ou adicionar detalhes.
  3. Caso haja alguma dúvida sobre a pergunta, adicione um comentário. O espaço de respostas deve ser utilizado apenas para responder a pergunta.
  4. Se o autor da pergunta marcar uma resposta como solucionada, esta marca aparecerá.
  5. Clique aqui para mais detalhes sobre o funcionamento do GUJ!

0 resposta

Não é a resposta que estava procurando? Procure outras perguntas com as tags java ou faça a sua própria pergunta.