Não sei porque não retorno o valor correto!
..
..
static int NUM_dists = 675;
static distancias dists[] = new distancias[NUM_dists];
final int NUM_CIDADES = 27;
..
...
Inicias todas as distancias no vetor dists[]
dists[0] = new distancias(new cidade("Aracaju", 476, 181),
new cidade("Belem", 361, 79), [color=red][i][b]1641[/b][/i][/color], "Distancia 0");
dists[1] = new distancias(new cidade("Aracaju", 276, 181),
new cidade("Belo Horizonte", 402, 273), [color=red][b]1248[/b][/color], "Distancia 1");
...
...
mais 674 iguais....
mas não retorna o valor em destaque vermelho
/** Essa é a classe que é responsável por criar uma rota.
* Essa rota é composta por todas as cidades selecionadas pelo
* usuário e são ligadas entre si por uma lista ligada.
*
* */
public class caminho {
/**Atributo que indica qual é primeira cidade do percurso. Sua filha indica a proxima cidade
*/
cidade cid_inicial;
/**Ponteiro para as cidades escolhidas pelo usuário no começo do programa.
* A cada cidade que vai sendo inserida, Escolhidas recebe a proxima.
*/
cidade Escolhidas;
/**Varíavel inteira que guarda o valor de custo total no pecurso que é composto pelas cidades
* e as distancias entre elas
*/
int distancia_total;
/**Ponteiro para a última cidade de um caminho
*/
cidade ultima;
/**Contrutor da classe caminho que inicia cid_inicial com null
*/
public caminho() {
cid_inicial = null;
}
/**Heurística que retorna qual é a cidade mais próxima no mapa da cidade atual passada como
* parametro.
* Utilizado apenas para um caminho de helicoptero.
*/
public cidade mais_perta(cidade atual) {
int distancia = -1;
int distancia2;
cidade aux = new cidade();
aux = Escolhidas;
cidade achada = new cidade(); // ponteiro que guarda a cidade com distancia menor
//Para até percorrer todas as cidades Escolhidas
while (aux != null) {
//calcula a distancia em linha reta entra a cidade atual e uma das Escolhidas
distancia2 = atual.calcula_distancia(aux.x, aux.y);
// Se a distancia encontrada for menor do que uma anterior que era a menor
// ou se for igual a -1 qdo for a primeira iterada
if (distancia == -1 || distancia2 < distancia) {
achada = aux;
distancia = distancia2;
}
aux = aux.filha;
}
// condições que tratam caso a cidade escolhida seja a primeira, do meio ou ultima da lista de Escolhidas
if (achada.filha == null && achada.mae != null) {
achada.mae.filha = null;
}
else if (achada.mae != null && achada.filha != null) {
achada.mae.filha = achada.filha;
achada.filha.mae = achada.mae;
}
else if (achada.mae == null && achada.filha != null) {
Escolhidas = achada.filha;
Escolhidas.mae = null;
}
else if (achada.mae == null && achada.filha == null) {
Escolhidas = null;
}
achada.filha = null;
achada.mae = null;
achada.distancia = distancia;
return achada;
}
/** Método que vai criando o percurso de acordo com a cidade mais perta da atual retornada do metodo anterior.
* Para percursos sem estradas.
*/
public cidade vizinho_proximo(cidade inicio) {
cidade aux = new cidade();
aux = inicio;
// So para ate todas as cidades forem inseridas.
while (Escolhidas != null) {
aux.filha = mais_perta(aux);
aux.filha.mae = aux;
aux = aux.filha;
}
// cidade que é a copia da primeira, pois o TSP volta ao inicio
cidade fim = new cidade(inicio.nome, inicio.x, inicio.y);
fim.distancia = fim.calcula_distancia(aux.x, aux.y);
aux.filha = fim;
fim.mae = aux.filha;
this.cid_inicial = inicio;
// coloca os valores das distancias em cada cidade
coloca_distancias();
return inicio;
}
/** Método que utiliza a inserção (sem estradas com helicoptero, em linha reta). O percurso começa com 3 cidades se ligando
formando um triangulo. As próximas cidades a serem inseridas no percurso, serão colocadas na
melhor aresta que torne o percurso com menor distancia.
*/
public cidade insercao(cidade inicial) {
this.cid_inicial = inicial;
// caso em que cria-se o triangulo entre as 3 cidades
if (Escolhidas.filha != null) {
cidade aux = cid_inicial;
aux.filha = Escolhidas;
distancia_total = aux.calcula_distancia(Escolhidas.x, Escolhidas.y);
aux = aux.filha;
Escolhidas = Escolhidas.filha;
distancia_total = distancia_total +
aux.calcula_distancia(Escolhidas.x, Escolhidas.y);
aux.filha = Escolhidas;
aux = aux.filha;
Escolhidas = Escolhidas.filha;
aux.filha = new cidade(cid_inicial.nome, cid_inicial.x, cid_inicial.y);
distancia_total = distancia_total +
aux.calcula_distancia(aux.filha.x, aux.filha.y);
// Insere as cidades no caminho até acabarem.
while (Escolhidas != null) {
insere_entre_cidades();
}
}
else {
// caso em q soh tem uma cidade selecionada e a inicial
cid_inicial.filha = Escolhidas;
Escolhidas.filha = new cidade(cid_inicial.nome, cid_inicial.x,
cid_inicial.y);
}
coloca_distancias();
return cid_inicial;
}
/** Heurística de inserção que insere uma cidade selecionada, no percurso fazendo com
* que o caminho após a inserção seja o menor possivel em custo
*/
public cidade insere_entre_cidades() {
// aux é a cidade a ser inserida
cidade aux = this.Escolhidas;
Escolhidas = Escolhidas.filha;
//ponteiro para a cidae q será mãe da cidade inserida
cidade nela_inserida = this.cid_inicial;
//ponteiro para varrer as cidades do caminho
cidade atual = this.cid_inicial;
boolean primeira = true;
int distancia_aux1 = -1;
int distancia_aux2 = -1;
int distancia_antiga = -1;
int distancia_primeira = distancia_total;
//Percorre todas as cidades do caminho
while (atual.filha != null) {
//distancia entre uma cidade e a nova
distancia_aux1 = atual.calcula_distancia(aux.x, aux.y);
//distancia entra filha dessa ultima e a nova
distancia_aux2 = atual.filha.calcula_distancia(aux.x, aux.y);
//distancias entre essas duas cidades
distancia_antiga = atual.filha.calcula_distancia(atual.x, atual.y);
//verifica se a distancia é menor ai seleciona a cidade
if (distancia_primeira + (distancia_aux1 + distancia_aux2) -
distancia_antiga < distancia_total || primeira) {
nela_inserida = atual;
distancia_total = distancia_primeira + (distancia_aux1 + distancia_aux2) -
distancia_antiga;
primeira = false;
}
atual = atual.filha;
}
//arruma os ponteiros das cidades após a inserção de uma nova entre duas cidades
aux.filha = nela_inserida.filha;
nela_inserida.filha = aux;
return atual;
}
/**Método para colocar as distancias em linha reta entre todas as cidades do percurso
*/
public void coloca_distancias() {
cidade aux = cid_inicial;
int acum = 0;
while (aux.filha != null) {
aux.filha.custo = aux.filha.calcula_distancia(aux.x, aux.y);
acum = acum + aux.filha.custo;
aux = aux.filha;
}
aux.acum = acum;
this.distancia_total = acum;
}
//*******************************************
/** Método que utiliza a heurística da inserção, e insere as novas cidades no caminho anterior
* a inserção.
*/
public cidade insere_com_rodovias(cidade inicial) {
cidade aux = Escolhidas;
Escolhidas = Escolhidas.filha;
cid_inicial = a_estrela2(inicial, aux, inicial);
//Insere até as cidades acabarem
while ( Escolhidas != null ){
//atualiza o valor da distancia total do caminho
this.distancia_total = this.distancia_total + nova_rodovia();
}
return cid_inicial;
}
/** Heurística da inserção caso o caminho seja percorrido por um carro, utilizando as rodovias e custos reais entra as cidades.
Retornando o custo do novo caminho encontrado
*/
public int nova_rodovia(){
cidade nova = Escolhidas;
Escolhidas = Escolhidas.filha;
//verifica se a nova cidade a ser incluida já está no caminho
if ( !inserida(nova)){
cidade aux = cid_inicial;
cidade nela_inserida = null;
// caminho que é o com menor custo
caminho melhor = new caminho();
melhor.distancia_total = -1;
// atual é um novo caminho.
caminho atual = new caminho();
// Percorre o caminho e vai utilizando a inserção para selecionar o caminho d menor custo que se juntará ao caminho sem a cidade nova
while (aux.filha != null) {
// atual é um caminho entre a cidade atual até a nova que depois volta para a filha da cidade atual
atual.a_estrela2(aux, nova, aux.filha);
// verifica se essa caminho é menor do que um anterior, caso seja, é o melhor caminho por enquanto
if (atual.distancia_total < melhor.distancia_total ||
melhor.distancia_total == -1) {
melhor = atual;
atual = new caminho();
nela_inserida = aux;
}
aux = aux.filha;
}
//Une o dois caminho o anterior sem a cidade nova com o caminho entre as duas cidade e a nova que correspondem
//ao de menor custo
melhor.ultima.filha = nela_inserida.filha.filha;
nela_inserida.filha = melhor.cid_inicial.filha;
return melhor.distancia_total - ultima.custo;
}
else return 0;
}
/** Método que verifica se a cidade já esta presente no percurso
*/
public boolean inserida ( cidade a){
cidade aux = cid_inicial;
while ( aux != null ){
if ( aux.nome == a.nome) return true;
else aux = aux.filha;
}
return false;
}
/** Método que implementa o A* entre 3 cidades, da cidade A para a cidade B e de B para a cidade C.
* onde A e C, são cidades mae e filha e B é a cidade a ser inserida
*/
public cidade a_estrela2(cidade a, cidade nova, cidade be) {
//Copia a cidade a
cidade primeira = new cidade(a, 0, 0, 0,"");
//Copia a cidade be
cidade b = new cidade(be, 0, 0, 0,"");
//Aponta para a primeira cidade
cidade aux = primeira;
//Realiza o A* entre duas cidade, da primeira até a nova a ser inserida
while (aux.nome != nova.nome) {
//Loop que percorre o vetor de distancias reais entre cidades
for (int i = 0; i < mapa.NUM_dists; i++) {
//Verifica se uma posição do vetor é igual a cidade atual percorrida
if (mapa.dists[i].cid1.nome == aux.nome) {
int linha_reta = nova.calcula_distancia(mapa.dists[i].cid2.x,
mapa.dists[i].cid2.y);
// Caso encontre significa que essa cidade está ligada a outra
// é inserida então numa fila de prioridade (ordenada pelo metodo ordena)
aux.ordena(new cidade(mapa.dists[i].cid2, linha_reta,
mapa.dists[i].valor, aux.acum, mapa.dists[i].rodovia));
}
// mesma condição, para verificar se uma cidade tem uma filha ou mais
else if (mapa.dists[i].cid2.nome == aux.nome) {
// implementar metodo que ordena mas nao pode ordenar primeira posicao
int linha_reta = nova.calcula_distancia(mapa.dists[i].cid1.x,
mapa.dists[i].cid1.y);
// cidade que copia, distancia em linha reta e custo d uma cidade a outra
aux.ordena(new cidade(mapa.dists[i].cid1, linha_reta,
mapa.dists[i].valor, aux.acum, mapa.dists[i].rodovia));
}
}
aux = aux.filha;
}
// nesse instante exectou o A* da primeira cidade até a segunda
aux.filha = null;
// Comaça o A* entre a cidade a ser inserida e a terceira cidade passada como parametro
// Mesmo processo do A* anterior
while (aux.nome != b.nome) {
for (int i = 0; i < mapa.NUM_dists; i++) {
if (mapa.dists[i].cid1.nome == aux.nome) {
int linha_reta = b.calcula_distancia(mapa.dists[i].cid2.x,
mapa.dists[i].cid2.y);
aux.ordena(new cidade(mapa.dists[i].cid2, linha_reta,
mapa.dists[i].valor, aux.acum, mapa.dists[i].rodovia));
}
else if (mapa.dists[i].cid2.nome == aux.nome) {
int linha_reta = b.calcula_distancia(mapa.dists[i].cid1.x,
mapa.dists[i].cid1.y);
aux.ordena(new cidade(mapa.dists[i].cid1, linha_reta,
mapa.dists[i].valor, aux.acum, mapa.dists[i].rodovia));
}
}
aux = aux.filha;
}
aux.filha = null;
this.ultima = aux;
//Recebe o custo acumulado da ultima cidade que é o custo total
this.distancia_total = ultima.acum;
//Após achar a ultima cidade, percorre das folhas até a raiz para atualizar os ponteiro
//das cidades filhas, pois ainda estão na fila de prioridade, o ponteiro pra cidade mãe
// é que indica a ordem do caminho de uma cidade a outra.
while (aux.mae != null) {
aux.mae.filha = aux;
aux = aux.mae;
}
cid_inicial = primeira;
return primeira;
}
}
Porque o custo de uma cidade a outra não é o valor que está em negrito e em vermelho?
O que está faltando?