Estou implementando o algoritmo simulated annealing para resolver o problema do caixeiro viajante - sim, é trabalho de faculdade - e, se possível, gostaria de colher opiniões sobre uma questão.
Estou usando double para armazenar o valor da temperatura do sistema, e uma das condições de parada do algoritmo é quando a temperatura chega a (ou se aproxima de) zero. No meu caso estou implementando o laço da seguinte forma:
}[/code]
Porém o algoritmo às vezes não finaliza sua execução por causa da imprecisão do tipo de dados double. Eu tenho duas opções:
Usar BigDecimal, que é preciso mas é mais custoso. Tenho dúvidas se seria uma boa opção por causa da performance, uma vez que as instâncias do caixeiro viajante podem possuir dezenas de milhares de cidades;
Mudar a comparação para tolerar uma temperatura próxima de zero ao invés de exatamente igual. Nesse caso, qual seria o valor ideal?
Algoritmos de cálculo numérico não devem usar esse tipo de comparação contra um valor exato. (
while (Double.compare(system.temperature(), 0) <= 0) {
}
) .
Pra começar, Double.compare (t1, t2) <= 0 é um desperdício de tempo; use t1 <= t2.
Eles SEMPRE devem usar tolerâncias. Ou seja, o correto é usar, no seu caso,
while (Math.abs (system.temperature()) <= eps) {
}
onde eps é um valor que você deve configurar. Digamos que seja 1E-5, mas não conheço seu algoritmo tão detalhadamente que possa saber se 1E-5 é um valor muito baixo ou alto demais.
Isso é um trabalho de faculdade, correto?
Pois bem, existe necessidade de vc se preocupar com performance? Ainda mais que estamos falando de caixeiro-viajante, que é um problema complexo…
Não estou falando que foi ruim vc ter pensado nisso. Muito pelo contrário!!! É ótimo ver que vc se preocupa com esse tipo de coisa. Mostra que vc é/será um bom desenvolvedor, mas talvez o que realmente importa seja a lógica do algoritmo, e não esse tipo de coisa.
Estou te incentivando a manter o foco no problema, e não na solução. Se, para esse trabalho, o professor exigir que o algoritmo rode num tempo y, OK, você deve se preocupar com isso. Com contrário, se preocupe com o objetivo.
E outra coisa: pq vc não transforma esses valores decimais em valores inteiros? Tipo, vc sabe qual o menor valor que será de entrada?
Digamos que seja 0,0001 grau. Bastaria vc multiplicar TODOS os valores de temperatura por 10.000 e vc só precisará trabalhar com inteiros. Dai vc não precisar se preocupar com a aritmética de ponto flutuante do Java.
entanglement, obrigado pelas recomendações, ajudaram bastante.
Eu queria realmente saber qual o valor exato pra usar como tolerância; acho que vou ter que descobrir empiricamente.
[quote=clone_zealot]Isso é um trabalho de faculdade, correto?
Pois bem, existe necessidade de vc se preocupar com performance? Ainda mais que estamos falando de caixeiro-viajante, que é um problema complexo…
Não estou falando que foi ruim vc ter pensado nisso. Muito pelo contrário!!! É ótimo ver que vc se preocupa com esse tipo de coisa. Mostra que vc é/será um bom desenvolvedor, mas talvez o que realmente importa seja a lógica do algoritmo, e não esse tipo de coisa.
Estou te incentivando a manter o foco no problema, e não na solução. Se, para esse trabalho, o professor exigir que o algoritmo rode num tempo y, OK, você deve se preocupar com isso. Com contrário, se preocupe com o objetivo.[/quote]
Preciso me preocupar com performance porque meu trabalho é justamente uma análise de desempenho de diferentes algoritmos de busca na resolução do problema do caixeiro viajante, entre eles simulated annealing. Não é um trabalho qualquer na verdade, trata-se da minha monografia. Além do mais, como já falei antes, terei instâncias do problema que poderão conter dezenas de milhares de cidades - o algoritmo genético, por exemplo, passa umas duas horas rodando - e usar BigDecimal pode influenciar. Queria justamente saber se alguém já implementou o simulated annealing alguma vez pra me responder se essa preocupação é relevante ou não.
[quote=clone_zealot]E outra coisa: pq vc não transforma esses valores decimais em valores inteiros? Tipo, vc sabe qual o menor valor que será de entrada?
Digamos que seja 0,0001 grau. Bastaria vc multiplicar TODOS os valores de temperatura por 10.000 e vc só precisará trabalhar com inteiros. Dai vc não precisar se preocupar com a aritmética de ponto flutuante do Java.[/quote]
Ótima sugestão. No entanto o uso de números de ponto flutuante é mais cômodo de fato pois há uma fórmula do algoritmo que utiliza a constante de Boltzmann, e trabalhar com cálculos inteiros usando essa constante vai render um trabalho extra que eu não quero ter. A performance é importante sim, mas não a esse ponto, creio.
Se você vai usar uma máquina como um Core 2 Duo ou um Phenom ou mesmo um Pentium antigão, usar aritmética de ponto flutuante é muito, muito mais rápido que usar BigDecimal, porque o próprio processador implementa a aritmética de ponto flutuante (ou via “coprocessador”, ou via SSE2 ou SSE3).
Se não me engano, é mais rápido fazer uma multiplicação de ponto flutuante em vários desses processadores que fazer uma multiplicação inteira. Mas é questão de testar.
Usar BigDecimal ou BigInteger deve ser relegado a casos especiais.
- e, se possível, gostaria de colher opiniões sobre uma questão.