❶ 蠻力法是什麼樣的演算法
《演算法設計與分析基礎》學習 --- 蠻力法 要重溫演算法思想，並以《演算法設計與分析基礎》這本書作為教材。該書每一章介紹一種演算法設計思想。今天從最簡單的開始寫起，打好基礎。以後再逐步深入，學習更深入的演算法。 蠻力法就是一種解決問題的最簡單最直觀的最容易理解方法，雖然它簡單，而且在實際應用中因為效率的原因可能不能派上用場，但是還是不能忽略它。正如書中作者所說，在解決小規模問題的時候也不失為一個方法，而且也是更復雜演算法的基礎。 一、選擇排序
以最簡單的思路解決排序問題，對於N個元素的數組，通過N次掃描數組，每次選擇出最小的元素放置到正確的位置，N趟掃描後即完成排序。 show sourceview source print? 01/* 02 蠻力法-選擇排序 03 將輸入數組排成非遞減數組 04 05 array:待排數組 06 n:數組大小，即[0,n-1] 07*/08void SelectionSort(int array[],unsigned int n) 09{ 10 int min; 11 for(int i=0;i<n-1;i++) 12 { 13 min=i; 14 for(int j=i+1;j<n;j++) 15 { 16 if(array[j]<array[min]) 17 min = j; 18 } 19 if(i!=min) 20 { 21 int temp = array[i]; 22 array[i] = array[min]; 23 array[min] = temp; 24 } 25 } 26}//SelectionSort
這是一個最差的排序方法，對於任何輸入都是 O(n*n)的時間復雜度。但是它的最大優點就是交換次數最少。 二、冒泡排序
又是一個經典的蠻力排序演算法。這里我僅僅對原始的冒泡做了點點改進，如果演算法已經排好序的話該演算法掃描一遍便完成排序。
show sourceview source print? 01/* 02 蠻力法-冒泡排序(稍微改進版) 03 將輸入數組排成非遞減數組 04 05 array:待排數組 06 n:數組大小，即[0,n-1] 07*/08void BubbleSort(int array[],unsigned int n) 09{ 10 int i=n-1; 11 int last; 12 while(i>0) 13 { 14 last = 0; 15 for(int j=0;j<i;j++) 16 { 17 if(array[j]>array[j+1]) 18 { 19 int temp = array[j]; 20 array[j] = array[j+1]; 21 array[j+1] = temp; 22 23 last = j; //記錄最近一次交換值的位置 24 } 25 } 26 i = last; 27 } 28}//BubbleSort
但是在最差的情況下，它還是O(n*n)的時間復雜度。 三、順序查找和字元串的蠻力匹配
順序查找，再簡單不過的查找演算法了，算是對蠻力思想的一種應用。以及字元串的蠻力匹配也是這樣的。
❷ 蒙特卡洛樹搜索 - 以蠻力對抗智慧
蒙特卡洛樹搜索（Monte Carlo tree search；簡稱：MCTS）是一種用於某些決策過程的啟發式搜索演算法，最引人注目的是在游戲中的使用。一個主要例子是計算機圍棋程序，它也用於其他棋盤游戲、即時電子游戲以及不確定性游戲。
比如圍棋，棋手需要針對盤面的情況，選擇下一步走哪個位置。這個決策過程可以認為是一個決策函數
a = f(s) ，即面對 可能的狀態s ， 決策函數f 會提供一個 行動a （落子位置）。當然，我們希望 f 盡可能優秀，其決策a能夠盡可能贏棋。
我們也可以將f構造為一顆決策樹。從盤面初始狀態開始（沒有棋子），令初始狀態為根節點，第一手棋有19*19=361個位置，因此根節點下面有361個子節點，第二手棋有360個可能的位置，即361個節點下，每個節點又有360個子節點......隨著雙方的落子，樹的分枝越來越多，每個分支最終會進入葉子狀態（對局結束，黑勝或白勝）。理論上可以列舉所有可能的情況，做一棵完整的決策樹，但實際上這個數據量大到不可能實現。因此，我們必須在有限的時間和空間之內，高效的構建一個子樹，這是一個不完整但 盡量好的決策樹 。
即便只是盡量好的決策，也是很困難的。因為一步棋的好壞通常不能立即判斷出來，最終的評判要到下完的時候才能決定誰贏，況且即便贏了棋，也不代表其中每一步都是好的。
但是，無論怎樣，必須提供某種方法讓AI知道一步棋好不好，也就是要提供一些 啟發 ，於是我們可以採用蒙特卡洛樹搜索方法。
剛才我們說到下一盤棋不能判定其中走法的好壞，但如果下很多次呢？比如在某個特定盤面s1情況下，進行n次對局（接著s1盤面往後走），如果統計下來黑棋贏得多，說明s1情況對黑棋比較有利。這就是蒙特卡洛方法的思想，用大量隨機事件逼近真實情況。
雖然通過蒙特卡羅方法可以近似估計一個狀態的好壞，但我們依然無法對太多狀態進行估算。因此，我們需要有選擇的集中力量對決策樹中的可能更有價值的那些節點進行估算。這就需要使用蒙特卡洛樹搜索，它提供了一種選擇機制，使我們能夠盡量選擇決策樹中比較有潛力的節點進行蒙特卡洛模擬，從而使得樹可以盡量集中在「較好」的策略上進行「生長」。
蒙特卡洛樹搜索有四個主要步驟：
從根節點R開始，選擇連續的子節點向下至葉子節點L。讓決策樹向最優的方向擴展，這是蒙特卡洛樹搜索的精要所在。也就是要選擇一個盡量」有潛力「的樹節點，那麼怎樣的節點是有潛力呢？ 一個是勝率高，另一個是被考察的次數少 。
勝率高的節點（狀態）意味著最後贏棋的概率較大，當然應該多花些精力分析其後續走法。被考察次數少的節點意味著該節點（狀態）尚未經過充分研究，有成為黑馬的可能。
具體來說，通常用UCB1（Upper Confidence Bound，上置信區間）公式來計算一個節點的」潛力「：
wi：第 i 次移動後取勝的次數
ni：第 i 次移動後模擬的次數
c：探索參數/權衡參數，理論上等於 根號2，在實際中通常可憑經驗選擇
t：模擬總次數，等於所有 ni 的和
看一個例子（參考 28 天自製你的 AlphaGo（五） ）
上圖中每個節點代表一個局面。而 A/B 代表這個節點被訪問 B 次，黑棋勝利了 A 次。例如一開始的根節點是 12/21，代表總共模擬了 21 次，黑棋勝利了 12 次。
圖中展示了蒙特卡洛樹搜索的四個步驟，我們先看左邊第一個樹（Selection）。假設根節點是輪到黑棋走。那麼我們首先需要在 7/10、5/8、0/3 之間選擇，採用上面的UCB1公式：
假設 C 比較小（比如C=1），上述3個分數為 1.25 1.245 1，於是我們選擇 7/10 節點（它得分1.25是最高的）。然後接下來 7/10 下面的 2/4 和 5/6 之間選擇。注意，由於現在是白棋走，需要把勝率估計倒過來。即圖上黑棋勝率是 2/4 和 5/6，則白棋勝率是 (1 - 2/4) 和 (1 - 5/6)：
那麼白棋應該選 2/4 節點。（圖中擴展的是 5/6 節點，這不是很合理）。
在所選的葉子節點L，如果已經能判定輸贏，則該輪游戲結束，否則創建一個或多個子節點並選取其中一個節點C。
看上圖第2個樹（Expansion），假設黑棋選擇了（當前的）葉子節點 3/3，然後創建了一個子節點，初始狀態 0/0。
從節點C開始，用隨機策略進行游戲，直到分出輸贏（獲得一次准確的回報）。這一步驟又稱為playout或者rollout。
雖然原則上蒙特卡洛方法是採用隨機策略，不過實際中也可以採用一些「有經驗」的策略，或者兩者的結合。所謂有經驗的策略就像一個有一定水平的棋手，ta 可以下出一些比較好的走法。我們可以在模擬的某個階段採用棋手的走法，另外一些階段採用隨機走法。
不過總的來說，模擬需要很快速的完成，這樣才能得到盡量多的模擬結果，使統計結果逼近真實的勝率。
看上圖第3個樹（Simulation），黑棋從 0/0 節點開始進行模擬游戲直到終局，假設黑棋輸，所以得分是 0/1。
使用隨機游戲的結果，更新從C到R的路徑上的節點信息。
看上圖第4個樹（Backpropagation），從 0/0 節點開始遍歷父節點，直到根節點R，這條路徑上的每個節點都添加一個 0/1。
當構建了一棵蒙特卡洛樹以後，需要用它來做決策時，應該選擇訪問量最大的節點，而不是勝率最高的節點，也不是UCB分數最高的節點。
訪問量不夠大的節點，即使勝率高，也不夠可靠（因為模擬次數不夠多）。而訪問量最大的節點，通常也有一定的勝率，想想UCB公式，如果勝率不高是不會經常被選中的（訪問量不會大）。所以採用訪問量最大的節點，AI的表現會更加穩定。
對於圍棋AI，僅使用蒙特卡洛樹搜索是不夠的，尤其是 AlphaGO 這樣的頂級AI，更多分析請參考：
左右互搏，青出於藍而勝於藍？阿爾法狗原理解析
28 天自製你的 AlphaGo（五）
AlphaGo背後的力量：蒙特卡洛樹搜索入門指南
蒙特卡洛樹搜索（MCTS）演算法
維基網路——蒙特卡洛樹搜索
維基網路——蒙特卡羅方法