Generazione numeri casuali CON PROBABILITA'

[fracarro]

Salve ragazzi. Sto implementando un generatore di grafi e ho trovato qualche difficoltà nell'assegnazione dei pesi ai nodi. Il problema è questo. Io ho n nodi ad ognuno dei quali ha associato un grado (numero di archi incidenti). Ora dato un range [LB,...,UB] di valori interi, il mio obiettivo sarebbe quello di associare ad ogni nodo del grafo un peso tra LB e UB che però sia calcolato in modo pseudocasuale tenendo presente anche il grado del nodo. In parole povere maggiore è il grado del nodo maggiori sono le possibilità che gli sia associato un peso alto. Al contrario se un nodo ha grado 2 (il minimo nel grafo che costruisco) il suo peso dovrebbe tendere al valore LB.

Qualcuno di voi ha idea di come scrivere una funzione per generare numeri random in un intervallo in modo non uniforme ma bensì dipendente da un parametro (il grado in questo caso)?

[Torav]

Beh devi assegnare una funziona di probabilità. Se per esempio vuoi generare una gaussiana in un intervallo puoi utilizzare la trasformazione di Box Muller. Di generatori di numeri pseudocasuali con distribuzioni folli ce ne sono quanti vuoi, prima devi definire la tua però!

[fracarro]

Beh devi assegnare una funziona di probabilità. Se per esempio vuoi generare una gaussiana in un intervallo puoi utilizzare la trasformazione di Box Muller. Di generatori di numeri pseudocasuali con distribuzioni folli ce ne sono quanti vuoi, prima devi definire la tua però!

Non ho particolari esigente. Una semplice funzione crescente nell'intervallo dei valori va benissimo. Sapresti indicarmi come generare questi numeri casuali tipo con la Box Muller?

[fracarro]

Up.
Nessuno mi sa aiutare? A me va bene qualsiasi funzione di probabilità purchè mi garantisca che più grande è in valore che do in input alla funzione di generazione dei numeri maggiori saranno le probabilità di beccare un peso alto (vicino al limite superiore).

[Torav]

Beh devi dare un'espressione a questa distribuzione di probabilità che vuoi. Non può crescere all'infinito altrimenti non è una distribuzione di probabilità perché il suo integrale deve essere 1. Se dai una espressione ragionevole puoi utilizzare metodi come questo (http://en.wikipedia.org/wiki/Pseudorandom_number_generator#Non-uniform_generators) per generare la tua distribuzione partendo da una distribuzione uniforme

[lupoxxx87]

magari è un po' macchinoso ma....

• scali il grado del nodo (non so quale sia il dominio dei gradi) nel range (0, 1]

• così facendo ottieni un numero nel range, in relazione lineare con il grado del nodo (grado minimo = 0, grado massimo = 1)

• generi un numero casuale in (0,1]

• moltiplichi il numero casuale e il numoro legato al grado del nodo. otterrai quindi un numero in (0,1]

• scali il numero in [LB, ..., UB]


può andare ?

[fracarro]

Beh devi dare un'espressione a questa distribuzione di probabilità che vuoi. Non può crescere all'infinito altrimenti non è una distribuzione di probabilità perché il suo integrale deve essere 1. Se dai una espressione ragionevole puoi utilizzare metodi come questo (http://en.wikipedia.org/wiki/Pseudorandom_number_generator#Non-uniform_generators) per generare la tua distribuzione partendo da una distribuzione uniforme

Grazie per il link dal quale se ho capito bene è possibile ottenere quello che mi interessa generando numeri casuali (con probabilità uniforme). Mi perdo però quando comincia a parlare di Gaussiana. Non è che potresti scrivermi la riga di codice per questa generazione usando la Gaussiana per esempio? Grazie comunque dell'aiuto.

magari è un po' macchinoso ma....

• scali il grado del nodo (non so quale sia il dominio dei gradi) nel range (0, 1]

• così facendo ottieni un numero nel range, in relazione lineare con il grado del nodo (grado minimo = 0, grado massimo = 1)

• generi un numero casuale in (0,1]

• moltiplichi il numero casuale e il numoro legato al grado del nodo. otterrai quindi un numero in (0,1]

• scali il numero in [LB, ..., UB]


può andare ?

Dovrebbe funzionare. Ci provo prima possibile grazie..

[Torav]

Mettiamo che tu abbia un array in di N interi distribuiti uniformemente tra 1 e MAX_RAND ed un array out che vuoi riempire con N numeri distribuiti gaussianamente (varianza 1 e media 0), allora:


int i;
double x, y, r, phi;
for(i = 0; i < N; i++) {
x = in[i] / (MAX_RAND + 1.);
y = in[N/2 + i] / (MAX_RAND + 1.);

r = sqrt(-2.0 * log(x));
phi = 2 * PI * y;
out[i] = r * cos(phi);
out[N/2 + i] = r * sin(phi);
}