蒙特卡洛樹搜尋又稱隨機抽樣或統計試驗方法，屬於計算數學的一個分支，它是在上世紀四十年代中期為了適應當時原子能事業的發展而發展起來的。傳統的經驗方法由於不能逼近真實的物理過程，很難得到滿意的結果，而蒙特卡洛樹搜尋方法由於能夠真實地模擬實際物理過程，故解決問題與實際非常符合，可以得到很圓滿的結果。這也是以機率和統計理論方法為基礎的一種計算方法，是使用隨機數（或更常見的偽隨機數）來解決很多計算問題的方法。將所求解的問題同一定的機率模型相聯繫，用電子計算機實現統計模擬或抽樣，以獲得問題的近似解。
基本介紹
- 中文名：蒙特卡洛樹搜尋
- 外文名：The monte carlo search tree
- 別稱：隨機抽樣或統計試驗方法
- 屬於：計算數學的分支
- 時間：上世紀四十年代中期
- 學科：數學
理論發展,基本原理思想,解題步驟,構造或描述機率過程,實現從已知機率分布抽樣,建立各種估計量,套用,
理論發展
當科學家們使用計算機來試圖預測複雜的趨勢和事件時, 他們通常套用一類需要長串的隨機數的複雜計算。設計這種用來預測複雜趨勢和事件的數字模型越來越依賴於一種稱為蒙特卡洛樹搜尋的統計手段, 而這種模擬進一步又要取決於可靠的無窮盡的隨機數目來源。
最近，由美國喬治亞大學的費倫博格博士作出的一份報告證明了最普遍用以產生隨機數串的電腦程式中有5個在用於一個簡單的模擬磁性晶體中原子行為的數學模型時出現錯誤。科學家們發現, 出現這些錯誤的根源在於這5個程式產生的數串其實並不隨機, 它們實際上隱藏了一些相互關係和樣式, 這一點只是在這種微小的非隨機性歪曲了晶體模型的已知特性時才表露出來。貝爾實驗室的里德博士告誡人們記住偉大的諾伊曼的忠告:“任何人如果相信計算機能夠產生出真正的隨機的數序組都是瘋子。”
基本原理思想
當所要求解的問題是某種事件出現的機率，或者是某個隨機變數的期望值時，它們可以通過某種“試驗”的方法，得到這種事件出現的頻率，或者這個隨機變數的平均值，並用它們作為問題的解。這就是蒙特卡羅方法的基本思想。蒙特卡羅方法通過抓住事物運動的幾何數量和幾何特徵，利用數學方法來加以模擬，即進行一種數字模擬實驗。它是以一個機率模型為基礎，按照這個模型所描繪的過程，通過模擬實驗的結果，作為問題的近似解。可以把蒙特卡羅解題歸結為三個主要步驟：構造或描述機率過程；實現從已知機率分布抽樣；建立各種估計量。
解題步驟
構造或描述機率過程
對於本身就具有隨機性質的問題，如粒子輸運問題，主要是正確描述和模擬這個機率過程，對於本來不是隨機性質的確定性問題，比如計算定積分，就必須事先構造一個人為的機率過程，它的某些參量正好是所要求問題的解。即要將不具有隨機性質的問題轉化為隨機性質的問題。
實現從已知機率分布抽樣
構造了機率模型以後，由於各種機率模型都可以看作是由各種各樣的機率分布構成的，因此產生已知機率分布的隨機變數（或隨機向量），就成為實現蒙特卡羅方法模擬實驗的基本手段，這也是蒙特卡羅方法被稱為隨機抽樣的原因。最簡單、最基本、最重要的一個機率分布是(0,1)上的均勻分布（或稱矩形分布）。隨機數就是具有這種均勻分布的隨機變數。隨機數序列就是具有這種分布的總體的一個簡單子樣，也就是一個具有這種分布的相互獨立的隨機變數序列。產生隨機數的問題，就是從這個分布的抽樣問題。在計算機上，可以用物理方法產生隨機數，但價格昂貴，不能重複，使用不便。另一種方法是用數學遞推公式產生。這樣產生的序列，與真正的隨機數序列不同，所以稱為偽隨機數，或偽隨機數序列。不過，經過多種統計檢驗表明，它與真正的隨機數，或隨機數序列具有相近的性質，因此可把它作為真正的隨機數來使用。由已知分布隨機抽樣有各種方法，與從(0,1)上均勻分布抽樣不同，這些方法都是藉助於隨機序列來實現的，也就是說，都是以產生隨機數為前提的。由此可見，隨機數是我們實現蒙特卡洛樹搜尋的基本工具。
建立各種估計量
套用
通常蒙特卡洛樹搜尋通過構造符合一定規則的隨機數來解決數學上的各種問題。對於那些由於計算過於複雜而難以得到解析解或者根本沒有解析解的問題，蒙特卡洛樹搜尋是一種有效的求出數值解的方法。一般蒙特卡洛樹搜尋在數學中最常見的套用就是蒙特卡羅積分。
蒙特卡羅算法表示採樣越多，越近似最優解。舉個例子，假如筐里有100個蘋果，讓我每次閉眼拿1個，挑出最大的。於是我隨機拿1個，再隨機拿1個跟它比，留下大的，再隨機拿1個……我每拿一次，留下的蘋果都至少不比上次的小。拿的次數越多，挑出的蘋果就越大，但我除非拿100次，否則無法肯定挑出了最大的。這個挑蘋果的算法，就屬於蒙特卡羅算法。告訴我們樣本容量足夠大，則最接近所要求解的機率。
計算機技術的發展，使得蒙特卡洛樹搜尋在最近10年得到快速的普及。現代的蒙特卡洛樹搜尋，已經不必親自動手做實驗，而是藉助計算機的高速運轉能力，使得原本費時費力的實驗過程，變成了快速和輕而易舉的事情。它不但用於解決許多複雜的科學方面的問題，也被項目管理人員經常使用。
藉助計算機技術，蒙特卡洛樹搜尋實現了兩大優點：
一是簡單，省卻了繁複的數學報導和演算過程，使得一般人也能夠理解和掌握；
二是快速。簡單和快速，是蒙特卡羅方法在現代項目管理中獲得套用的技術基礎。
