Algoritmi Monte Carlo

Gli algoritmi Monte Carlo sono algoritmi basati sul campionamento randomizzato. Nell'informatica il termine random è sinonimo di casualità. Questa tipologia di algoritmi si distinguono da quelli basati sull'enumerazione completa, perché non analizzano tutte le possibili combinazioni dei dati e dei percorsi ( path ).

Sono pertanto algoritmi approssimati e incompleti ma efficienti. Consentono di ridurre la complessità computazionale e raggiungere risultati o soluzioni considerate accettabili, sub-ottimali, in un tempo di esecuzione ridotto e consumando una quantità inferiore di memoria, rispetto agli algoritmi completi.

L'efficacia della soluzione è determinata dalle caratteristiche campionamento, dalla quantità e dalla qualità dei campioni, dalle prove ripetute in circostanze ambientali simili e dal livello massimo delle iterazione prima di fornire la risposta migliore, fino a quel momento trovata.

Alcuni esempi di algoritmi appartenenti alla categoria Monte Carlo sono l'algoritmo simulated anneling. Atri algorimti approssimati si basano sul campionamento diretto oppure sulle catene di Markov. Generalmente, sono algoritmi caratterizzati dalla casualità random, dalla ciclicità e da forme più o meno avanzate di apprendimento online ( online machine learning ).