Discussoes de Programacao e Tecnologia

Algoritmo Caminho Mais Proximo

2 respostas
W
Wipe

Ola pessoal

Estou com um problema de logica aqui para resolver ,
é o Seguinte :
Tenho 6 Cidades ,
a Distanco entre elas,
e Precisa percorre todas elas pelo menor caminho sem passar pela mesma cidade 2 x
e por fim chegar de volta a cidade inicial .

a Imagem mostra como seria partindo da cidade 6 :
[img]http://img405.imageshack.us/img405/9417/tabelazx.png[/img]

____________________________________________________________

o Caminho seria
6-1-3-4-5-2-6

Pois bem eu ja resolvi quase tudo falta so ele testar se ja passou pela cidade X e nao pegar a mesma 2 vezes , passei maior tempo tentando e nada . alguem me ajude pls abaixo o Codigo Fonte : 
// Funcao que Seleciona a cidade com menor distancia 
public class Teste
{ 
public static int pegaMenor(int distancias[])
	{
		int j=9;
		int d=1;
			for (int i=1; i<7; i++){ 
				if(distancias[i]<j && distancias[i]!=0){
					j=distancias[i];
					d=i;
				}
			}
		return(d);
	}
		
	

// funçao que cria a Lista de cidades possiveis para cada Cidade 
public static int[] listaCidades(int a){
		int [][] x = new int [7][7];
		int [] k = new int [7];
			x[1][1] = 0;
			x[2][2] = 0;
			x[3][3] = 0;
			x[4][4] = 0;
			x[5][5] = 0;
			x[6][6] = 0;
			x[1][2] = 2;
			x[1][3] = 1;
			x[1][4] = 4;
			x[1][5] = 9;
			x[1][6] = 1;
			x[2][1] = 2;
			x[2][3] = 5;
			x[2][4] = 9;
			x[2][5] = 7;
			x[2][6] = 2;
			x[3][1] = 1;
			x[3][2] = 5;
			x[3][4] = 3;
			x[3][5] = 8;
			x[3][6] = 6;
			x[4][1] = 4;
			x[4][2] = 9;
			x[4][3] = 3;
			x[4][5] = 2;
			x[4][6] = 6;
			x[5][1] = 9;
			x[5][2] = 7;
			x[5][3] = 8;
			x[5][4] = 2;
			x[5][6] = 2;
			x[6][1] = 1;
			x[6][2] = 2;
			x[6][3] = 6;
			x[6][4] = 6;
			x[6][5] = 2;
//cria e preenche vetor distancias		  
		 	 for (int i=1; i<7; i++){
		  		k[i]=x[a][i];
		 	 	}
		  	
	  return(k);	  
	}
       	  
       
	
								
	public static void main(String[] args)
		{   
			
			
		 int cidadeInicial=6;
		 int proximaCidade=0;
		
		 int [] distancias = new int [7];
		 int [] circuitoParcial =new int [7];
		
		// Adiciona a Primeira Cidade ao Circuito
		  circuitoParcial[1]=cidadeInicial;
		 
		  distancias=listaCidades(cidadeInicial);
		  
		 // Laço Principal
		 for(int i=2;i<7;i++)  {
		 	
		 	// pega a proxima cidade mais perto
		 	proximaCidade= pegaMenor(distancias);
		 	
		 	// imprime a proxima cidade na tela 
		 	System.out.println(proximaCidade+" proximaCidade:" );
		 	
		 	// Atualiza o vetor distancias
			 distancias=listaCidades(proximaCidade);
		 
		 
		 	 	
		 	// inclui a cidade vizitada no circuito 
			 circuitoParcial[i]=proximaCidade;
		 	
		 }		 	
  	  		   	
 		 // no final imprime o caminho percorrido 
	     System.out.println("caminho Percorrido : " ); 
	     for(int y=1;y<7;y++)  {
		 	 System.out.println( circuitoParcial[y] ); 
		 	 }
		  	
		 //System.out.println(b);	
		
		}	
					   		
	

}

Por favor me ajudem , é meu primeiro programa em Java .

Alura Desenvolvimento Back-End Java Sua Carreira em desenvolvimento back-end Java: dos fundamentos à arquitetura de sistemas...

2 Respostas

Bocchi
Bocchi

Bom existem varias maneiras de resolver o seu problema, a primeira que eu pensei foi em criar um vetor booleano com o tamanho das cidades contendo false se ela ainda nao foi visitada e true se ela ja foi, o codigo ficaria assim :

public class Teste
{
public static int pegaMenor(int distancias[], boolean[] visitadas)
    {
        int j=Integer.MAX_VALUE;
        int d=1;
            for (int i=0; i<6; i++){
                if(distancias[i]<j && distancias[i]!=0 && !visitadas[i]){
                    j=distancias[i];
                    d=i;
                }
            }
        return(d);
    }



// funçao que cria a Lista de cidades possiveis para cada Cidade
public static int[] listaCidades(int a){
        int [][] x = new int [6][6];
        int [] k = new int [6];
            x[0][0] = 0;
            x[1][1] = 0;
            x[2][2] = 0;
            x[3][3] = 0;
            x[4][4] = 0;
            x[5][5] = 0;
            x[0][1] = 2;
            x[0][2] = 1;
            x[0][3] = 4;
            x[0][4] = 9;
            x[0][5] = 1;
            x[1][0] = 2;
            x[1][2] = 5;
            x[1][3] = 9;
            x[1][4] = 7;
            x[1][5] = 2;
            x[2][0] = 1;
            x[2][1] = 5;
            x[2][3] = 3;
            x[2][4] = 8;
            x[2][5] = 6;
            x[3][0] = 4;
            x[3][1] = 9;
            x[3][2] = 3;
            x[3][4] = 2;
            x[3][5] = 6;
            x[4][0] = 9;
            x[4][1] = 7;
            x[4][2] = 8;
            x[4][3] = 2;
            x[4][5] = 2;
            x[5][0] = 1;
            x[5][1] = 2;
            x[5][2] = 6;
            x[5][3] = 6;
            x[5][4] = 2;
//cria e preenche vetor distancias
             for (int i=0; i<6; i++){
                k[i]=x[a][i];
             }

      return(k);
    }




    public static void main(String[] args)
        {


         int cidadeInicial=5;
         int proximaCidade=0;

         int [] distancias = new int [6];
         int [] circuitoParcial =new int [6];
         boolean [] visitadas = new boolean[6];

        // Adiciona a Primeira Cidade ao Circuito
          circuitoParcial[0]=cidadeInicial;
          visitadas[cidadeInicial] = true;

          distancias=listaCidades(cidadeInicial);

         // Laço Principal
         for(int i=1;i<6;i++)  {

            // pega a proxima cidade mais perto
            proximaCidade= pegaMenor(distancias,visitadas);
            visitadas[proximaCidade] = true;

            // imprime a proxima cidade na tela
            System.out.println(proximaCidade+" proximaCidade:" );

            // Atualiza o vetor distancias
             distancias=listaCidades(proximaCidade);



            // inclui a cidade vizitada no circuito
             circuitoParcial[i]=proximaCidade;

         }

         // no final imprime o caminho percorrido
         System.out.println("caminho Percorrido : " );
         for(int y=0;y<6;y++)  {
             System.out.println( circuitoParcial[y]+1 );
             }

         //System.out.println(b);

        }

Ahh outra coisa eu notei que você aloca 7 posicoes no vetor/matriz porem só utiliza 6 no java o vetores começam na posição 0, modifiquei isso abraços!.

W
Wipe

Bocchi

Muito obrigado cara tua ajuda foi nota 1000
abraços vlw !

Criado 15 de agosto de 2010
Ultima resposta 15 de ago. de 2010
Respostas 2
Participantes 2

Topicos relacionados

Como saber se um mes tem 4 ou 5 semanas?[RESOLVIDO] 31 respostas Como converter inteiro para string! 13 respostas Comando SELECT para selecionar intervalo de data SQL SERVER 12 respostas &, &&, |, ||. Qndo usar? 6 respostas O método split 12 respostas
Alura Git Flow: entenda o que é, como e quando utilizar Entenda o que é Git Flow, como funciona seu fluxo com branches como Master, Develop, Feature, Release e Hotfix, além de vantagens e desvantagens.
Casa do Codigo Ontologias e Web Semantica: Do conceito a aplicacao Por Ivam Galvao Filho — Casa do Codigo