Algoritmos Las Vegas,Monte carlo

18 de fevereiro de 2005 14 respostas

HumbertoJrPJ 18 de fevereiro de 2005

Pessoal

Eu procurei bastante no GOOGLE inteiro algum material pra mim estudar algoritmos Não deterministicos(algoritmos como Las Vegas e Monte Carlo) em Java e não encontrei nada a respeito,será que alguerm poderia me dar uma dica?

Grato,

14 Respostas

DianaPJ 18 de fev. de 2005

Achei isso:

http://www.inf.ufpr.br/~murilo/prob-slides.pdf

[]'s

HumbertoJrPJ 18 de fev. de 2005

“Diana”:
Achei isso:

http://www.inf.ufpr.br/~murilo/prob-slides.pdf

[]'s

:sad: Pois é,obrigado Diana! A internet toda e tb só achei isso.

ErkoPJ 18 de fev. de 2005

aea blz?

cara tu achou algum algoritmo desse genero em C ou C++?

se achou algo me passa o link q eu tenhu interesse

depois é soh quebrar a cabeça pra traduzir pra JAVA

[]´s

HumbertoJrPJ 18 de fev. de 2005

“AnjoSupremo”:
aea blz?

cara tu achou algum algoritmo desse genero em C ou C++?

se achou algo me passa o link q eu tenhu interesse

depois é soh quebrar a cabeça pra traduzir pra JAVA

[]´s

Cara é o seguinte eu não achei praticamente NADA de codigo mesmo não.Só mesmo o link acima,um colega me falou que existe um livro que tem e pensei que alguem aqui da lista iria o me sugerir,mas não sei qual o titulo…

andredecotia 26 de dez. de 2011

Alguém já implementou Monte Carlo em Java? Como foi a experiência…?

getAdicted 26 de dez. de 2011

andredecotia:
Alguém já implementou Monte Carlo em Java? Como foi a experiência...?

Boa noite amigo,

Serve em C?

/* rand example: guess the number */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main (){

  int iSecret, iGuess;
  int n = 0, i, cont = 0;
  printf("TAM do vetor: ");
  scanf("%d",&n);
  double vet1[n],vet2[n],vet3[n],vet4[n], calc = 0, area = 1.0;
  /* initialize random seed: */
  srand ( time(0) );
  for(i = 0; i< n; i++){
    vet1[i] = (1.0*random())/(1.0+RAND_MAX);
  vet2[i] = (1.0*random())/(1.0+RAND_MAX);
}

for(i = 0; i<n; i++){
  vet3[i] = vet1[i] * vet1[i]; 
}


for(i=0; i<n; i++){
   if(vet2[i] < vet3[i]){
     cont++;
   }
}

 calc = (area*cont)/n;
 printf("%f\n",calc);

return 0;
}

[]'s

andredecotia 26 de dez. de 2011

Oi getAdicted, tudo jóia? Primeiramente, obrigado pela ajuda…

A verdade é q tou tentando traduzir alguns fontes que encontrei para Java… E gostaria d ver algo em Java mesmo se possível…

danielfariati 28 de dez. de 2011

Este algoritmo não é difícil de traduzir para o Java, mas parece estar incompleto.

O iSecret e iGuess nunca estão sendo usados (assim como o vetor 4).
Se o iSecret e o iGuess são as principais variáveis do algoritmo e nunca estão sendo usadas… algo está errado.

EDIT: Se estiverem realmente interessados no algoritmo, isso pode ajudar: http://www.javaquant.net/books/MCBook-1.2.pdf

getAdicted 28 de dez. de 2011

/* rand example: guess the number */
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;time.h&gt;

int main (){
  int n = 0, i, cont = 0;
  printf(&quot;TAM do vetor: &quot;);
  scanf(&quot;%d&quot;,&n);
  double vet1[n],vet2[n],vet3[n],calc = 0, area = 1.0;
  /* initialize random seed: */
  srand ( time(0) );
  for(i = 0; i&lt; n; i++){
    vet1[i] = (1.0*rand())/(1.0+RAND_MAX);
  vet2[i] = (1.0*rand())/(1.0+RAND_MAX);
}

for(i = 0; i&lt;n; i++){
  vet3[i] = vet1[i] * vet1[i]; 
}


for(i=0; i&gt;&lt;n; i++){
   if(vet2[i] &gt;&lt; vet3[i]){
     cont++;
   }
}

 calc = (area*cont)/n;
 printf(&quot;%f\n&quot;,calc);

system(&quot;pause&quot;);
return 0;
}

Desculpem, jah faz um tempinho que tive Matemática para Simulação de Sistemas na faculdade, eu soh copiei e colei aqui.

Eu dei uma refatorada e agora está compilando, se não me falha a memória, o Profº dizia que 4 casas decimais após a virgula jah seria uma boa simulação. Eu vou colocar alocação dinamina nesse código para aceitar um N maior que 10000.

[EDIT]O material recomendado acima, pelo amigo, eh muito bom.[EDIT/]

[]'s

danielfariati 28 de dez. de 2011

Implementei os algoritmos em Java, pra quem estava pedindo.
Fiz da maneira mais simples possível, já que não sei o nível de complexidade que estão buscando.

Uma dica é criarem um array com todos os números já testados, para não tentar o mesmo número duas vezes…
Eu faria agora, mas estou no trabalho :P.

Monte Carlo:

public static void monteCarlo(int maximoIteracoes) {
	int secret = (int) (Math.random() * 100);
	int iteracoes = 0;
	int guess;

	do {
		guess = (int) (Math.random() * 100);
		iteracoes++;
	} while (secret != guess && iteracoes < maximoIteracoes);

	if (secret == guess) {
		System.out.println("MONTE CARLO: Foram necessarias " + iteracoes + " iterações para descobrir o número.");
	} else {
		System.out.println("MONTE CARLO: O número não foi descoberto nas " + maximoIteracoes + " iterações realizadas!");
	}
}

Las Vegas:

public static void lasVegas() {
	int secret = (int) (Math.random() * 100);
	int iteracoes = 0;
	int guess;

	do {
		guess = (int) (Math.random() * 100);
		iteracoes++;
	} while (guess != secret);

	System.out.println("LAS VEGAS: Foram necessarias " + iteracoes + " iterações para descobrir o número.");
}

andredecotia 28 de dez. de 2011

Oh legal…

danielfariati / getAdicted vcs poderiam comentar em qual situação usaram Monte Carlo?

danielfariati 28 de dez. de 2011

andredecotia:
Oh legal…

danielfariati / getAdicted vcs poderiam comentar em qual situação usaram Monte Carlo?

Modifiquei um pouco o código para mostrar quando utilizar Monte Carlo é melhor que Las Vegas…

import java.util.ArrayList;

public class AlgoritmosDiversos {

	public static final long MAX_SECRET = 9999999;

	public static void main(String[] args) {
		lasVegas();
		monteCarlo(100);
	}

	public static void lasVegas() {
		long runningTime = System.currentTimeMillis();

		long secret = (int) (Math.random() * MAX_SECRET);
		long guess;
		int iteracoes = 0;

		ArrayList<Long> guessList = new ArrayList<Long>();

		do {
			guess = (long) (Math.random() * MAX_SECRET);

			if (!guessList.contains(guess)) {
				guessList.add(guess);
				iteracoes++;
			}
		} while (guess != secret);

		runningTime = System.currentTimeMillis() - runningTime;
		System.out.println("LAS VEGAS: Foram necessarias " + iteracoes + " iterações para descobrir o número.");
		System.out.println("LAS VEGAS: O algoritmo ficou " + runningTime + "ms em execução.");
	}

	public static void monteCarlo(long maximoIteracoes) {
		long runningTime = System.currentTimeMillis();

		long secret = (long) (Math.random() * MAX_SECRET);
		long guess;
		int iteracoes = 0;

		ArrayList<Long> guessList = new ArrayList<Long>();

		do {
			guess = (long) (Math.random() * MAX_SECRET);

			if (!guessList.contains(guess)) {
				guessList.add(guess);
				iteracoes++;
			}
		} while (secret != guess && iteracoes < maximoIteracoes);

		if (secret == guess) {
			System.out.println("MONTE CARLO: Foram necessarias " + iteracoes + " iterações para descobrir o número.");
		} else {
			System.out.println("MONTE CARLO: O número não foi descoberto nas " + maximoIteracoes + " iterações realizadas!");
		}

		runningTime = System.currentTimeMillis() - runningTime;
		System.out.println("MONTE CARLO: O algoritmo ficou " + runningTime + "ms em execução.");
	}

}

Como verá se rodar o programa, o algoritmo Las Vegas ficará rodando por muito tempo até encontrar a solução (mas com certeza encontrará).
Pode ser usado quando você precisar saber exatamente a resposta, sem estimativas.

O Monte Carlo terá um número limitado de tentativas, evitando este tempo gigantesco de espera (mas pode não encontrar a solução).
Pode ser usado quando apenas uma estimativa for o bastante, não o valor exato. Ou então quando não puder ficar esperando tanto tempo para saber a solução.
(Isto pode não ter ficado claro no meu algoritmo, pois ele não está fazendo estimativas de qual é o número correto, apenas comparando dados)

Eu nunca precisei utilizar o Monte Carlo, para ser sincero.
Talvez alguém que já tenha utilizado em aplicações reais possa dar uma explicação melhor (e corrigir se falei besteira :P).

EDIT: To pensando em fazer um algoritmo que faça previsões, mais tarde, quando chegar em casa… Mas não garanto nada

andredecotia 28 de dez. de 2011

EDITED: Executando o código…

danielfariati 29 de dez. de 2011

Modifiquei o código para ele prever, com os números que sobraram, qual o mais provável de ser o número secreto.
Consigo pensar em várias maneiras de melhorar esse código e subir a chance dele acertar a previsão, mas não quero deixar muito complexo :P.
O problema dele é com os extremos… Tipo se o número secreto for 1.
Mas já serve para demontrar melhor o que o Monte Carlo faz :P.

OBS: Ele só faz a previsão se não conseguir encontrar o número correto nas iterações que fez antes.

import java.util.ArrayList;

public class AlgoritmosDiversos {

	public static final double MAX_SECRET = 10;

	public static void main(String[] args) {
		monteCarlo(5);
	}

	public static void monteCarlo(long maximoIteracoes) {
		long runningTime = System.currentTimeMillis();

		long secret = (long) (Math.random() * MAX_SECRET) + 1;
		long guess;
		int iteracoes = 0;

		ArrayList<Long> remainingList = new ArrayList<Long>();

		for (long i = 1; i <= MAX_SECRET; i++) {
			remainingList.add(i);
		}

		do {
			guess = (long) (Math.random() * MAX_SECRET) + 1;

			if (remainingList.contains(guess)) {
				remainingList.remove(guess);
				iteracoes++;
			}
		} while (secret != guess && iteracoes < maximoIteracoes);

		if (secret == guess) {
			System.out.println("MONTE CARLO: Foram necessarias " + iteracoes + " iterações para descobrir o número.");
		} else {
			long prediction = remainingList.get(remainingList.size() / 2);

			System.out.println("MONTE CARLO: O número não foi descoberto nas " + maximoIteracoes + " iterações realizadas!");
			System.out.println("MONTE CARLO: Previsão: " + prediction);
			System.out.println("MONTE CARLO: Número real: " + secret);
		}

		runningTime = System.currentTimeMillis() - runningTime;
		System.out.println("MONTE CARLO: O algoritmo ficou " + runningTime + "ms em execução.");
	}

}

Criado 18 de fevereiro de 2005

Ultima resposta 29 de dez. de 2011

Respostas 14

Participantes 6

14 Respostas

Topicos relacionados