Il metodo Montecarlo è un sistema numerico utilizzato per riprodurre e simulare una situazione reale o teorica. Con questo metodo è possibile generare gli eventi appartenenti ad una distribuzione di probabilità. Quello che state per leggere è un articolo che tratta di questo argomento nell’ottica di determinare alcune soluzioni a classi di problemi, normalmente risolti per mezzo di altri criteri o sistemi.
ATTENZIONE: quello che hai appena letto è solo un estratto, l'Articolo Tecnico completo è composto da ben 4474 parole ed è riservato agli ABBONATI. Con l'Abbonamento avrai anche accesso a tutti gli altri Articoli Tecnici che potrai leggere in formato PDF per un anno. ABBONATI ORA, è semplice e sicuro.
Certo che spiegato così sembra proprio un gioco per ragazzini.
Bravissimi!
Nel testo è ripetuto più volte che il linguaggio C è "veloce". Che io sappia la velocità di esecuzione di un programma è legata all'hardware utilizzato. Facendo riferimento al primo esempio (nonno, padre, figlio) lo spazio delle soluzioni è 10^5 elementi: se volessimo "testarli" tutti, con tempo di esecuzione di 10 microsecondi impiegheremmo 1 secondo (in realtà di meno se la soluzione non è proprio l'ultimo elemento). Tentando la sorte è solo probabile che ci riusciamo in un secondo, potremmo anche aspettare un tempo infinito visto che i numeri generati sono solo "pseudo-casuali".
In generale molti degli esempi presentati hanno una soluzione analitica che si calcola in un tempo definito e quindi non si capisce perché utilizzare un metodo che non garantisce la soluzione in un tempo ragionevole. L'utilizzo di tecniche basate su numeri casuali trova sicuramente la sua utilità in quei casi in cui non è possibile definire analiticamente una soluzione o lo spazio delle soluzioni da esplorare è proibitivo.
Il metodo presentato, poi, è semplicemente una ricerca casuale di una soluzione: si ripete l'estrazione tante volte finché non si indovina. Il metodo Monte Carlo è un'altra cosa: si ripete tante volte un esperimento (un numero elevato ma "predefinito"), poi sui risultati ottenuti si effettuano delle operazioni statistiche che restituiscono valori che "con elevata probabilità" riproducono il valore cercato.
Faccio un esempio: se ho un circuito con 20 componenti, tra resistori, induttori, condensatori, oguno con una precisione del +o- 5% e voglio vedere come cambiano le prestazioni del circuito al variare dei parametri, per farla semplice, con passo dell'1% ho 10^20 test diversi da fare. A questo punto si sceglie di generare 10^5 "estrazioni" (quindi un numero predefinito ) e valutare il numero di casi in cui il valore sotto osservazione (per esempio la banda passante) si discosta dal valore nominale oltre una soglia di riferimento (ad es. +o- 10%).
Infine una piccola nota di stile: limitiamoci a proporre una soluzione e lasciamo poi giudicare gli altri se quella che proponiamo è veramente una delle migliori, i commenti sono fatti apposta! Sicuramente, secondo il mio modesto parere, la proposta per "ampliare" il set di valori casuali è interessante ed ingegnosa però io dividerei per RAND_MAX forzando il tipo ad essere long double (80 bit penso bastino!) e poi moltiplicherei il numero (compreso fra 0 e 1) per il massimo valore che voglio utilizzare (al limite LDBL_MAX: oltre questo numero non credo si possa rappresentare nulla).
Sulla nota di stile sono d’accordo.
Per il resto, l’articolo è interessante. e fa ben il paio con l’altro.
ma in questo caso siamo sicuri che serva il metodo montecarlo? mi sembra che il numero di incognite sia basso e se ho ccapito il metodo serve quando ci sono grossi numeri e tante variabili. giusto?
avrei anche un’altra domanda riguardo alfio e bino. a me sembra lo stesso problema di padre e figlio. giusto?
concordo.
senti ma quel caso dei quadrati non simile al sudoku?
Altra cosa, come hai scelto i valori -50 e +50?
una domandal volo: ma non puoi mettere un break invece si usare ctrl+c?
a dimostrazione che tutto e matematica…..interessante l’algoritmo per superare il limite del valore di rand()……
Certo che il metodo Aleatorio e’ proprio bello e utile. L’altro giorno
mio figlio di 11 anni mi propose il seguente problema studiato a scuola
nelle ore di Matematica:
“Due amici comprano 8 litri di vino.
Esso e’ inizialmente contenuto in una bottiglia di 8 litri.
Hanno a disposizione un’altra bottiglia vuota da 5 litri e un’altra vuota da 3 litri.
Mediante travasi esatti (non a occhio), come fanno a dividere esattamente
il vino in due parti uguali (4 litri e 4 litri) ?”
Ci sono a disposizione: bottiglia di 8 litri (piena), di 5 litri (vuota), di 3 litri (vuota)
Il programma che segue ha fornito due soluzioni:
3 litri da B a C 0 0 8
5 litri da C a B 0 5 3
3 litri da B a A 3 2 3
3 litri da A a C 0 2 6
2 litri da B a A 2 0 6
5 litri da C a B 2 5 1
1 litri da B a A 3 4 1
3 litri da A a C 0 4 4
3 litri da B a C 0 0 8
3 litri da C a A 3 0 5
3 litri da A a B 0 3 5
3 litri da C a A 3 3 2
2 litri da A a B 1 5 2
5 litri da B a C 1 0 7
1 litri da A a B 0 1 7
3 litri da C a A 3 1 4
3 litri da A a B 0 4 4
Di seguito il programma, che usa la logica “A STATI”
FUNCTION Main()
LOCAL a, b, c
LOCAL caso, q
LOCAL t
CLEAR SCREEN
a = 0
b = 0
c = 8
? Space( 25 ), a, b, c
t = 0
DO WHILE .T.
t++
caso = hb_RandomInt( 1, 6 )
q = hb_RandomInt( 1, 5 )
// —————Da C a B———
IF caso = 1
IF c >= q .AND. b + q == 5
c = c – q
b = b + q
? q, “litri da C a B”, a, b, c, VisualizzaAsterisco( a, b, c )
ENDIF
IF c – q == 0 .AND. b + q = q .AND. a + q == 3
c = c – q
a = a + q
? q, “litri da C a A”, a, b, c, VisualizzaAsterisco( a, b, c )
ENDIF
IF c – q == 0 .AND. a + q = q .AND. a + q == 3
b = b – q
a = a + q
? q, “litri da B a A”, a, b, c, VisualizzaAsterisco( a, b, c )
ENDIF
IF b – q == 0 .AND. a + q = q .AND. c + q == 8
b = b – q
c = c + q
? q, “litri da B a C”, a, b, c, VisualizzaAsterisco( a, b, c )
ENDIF
IF b – q == 0 .AND. c + q = q .AND. b + q == 5
a = a – q
b = b + q
? q, “litri da A a B”, a, b, c, VisualizzaAsterisco( a, b, c )
ENDIF
IF a – q == 0 .AND. b + q = q .AND. c + q == 8
a = a – q
c = c + q
? q, “litri da A a C”, a, b, c, VisualizzaAsterisco( a, b, c )
ENDIF
IF a – q == 0 .AND. c + q <= 8
a = a – q
c = c + q
? q, "litri da A a C", a, b, c, VisualizzaAsterisco( a, b, c )
ENDIF
ENDIF
// ———————————-FINITO ?——————-
IF ( a == 4 .AND. b == 4 ) .OR. ( a == 4 .AND. c == 4 ) .OR. ( b == 4 .AND. c == 4 )
? "Tentativi ", t
RETURN NIL
ENDIF
ENDDO
RETURN NIL
FUNCTION VisualizzaAsterisco( a, b, c )
LOCAL ch
IF a == 0 .AND. b == 0 .AND. c == 8
ch = " *"
CLS
ELSE
ch = ""
ENDIF
RETURN ch