窮舉搜尋

窮舉搜尋（粵拼：kung4 geoi2 sau2 cam4；英文：brute-force search）係最原始嗰種搜尋演算法，指將手上嘅數據（事先以某啲方式排好咗）逐個逐個耖caau3，一路耖到搵到想要嗰個為止。

基本概念

睇埋：搜尋演算法

例如手上有一列以隨機次序排嘅數字，用家想要由呢個數列當中最大嗰個出嚟，用窮舉搜尋嘅話，睇嗰個人就要睇嗮個數列當中嘅每個數字，再俾出最大嗰個出嚟；呢段簡單嘅演算法用粵文寫出嚟嘅話會係^[1]：

1. 如果個列入面冇數字，噉就唔會有「最大嗰個數」。
2. 先假定個列入面第一個數字係最大嗰個。
3. 逐個逐個噉去睇個列入面啲數字，如果撞到個數字大過而家手上嗰個「最大數字」嘅話，將新撞到呢個數字設做「最大數字」。
4. 如果睇勻嗮個列入面啲數字嘅話，將手上嗰個「最大數字」交出嚟做答案。

上述呢個演算法用比較形式些少嘅虛擬碼寫出嚟嘅話會係噉：

// Input: A list of numbers L.
// Output: The largest number in the list L.
if L.size = 0 return null;
largest ← L[0];
for each item in L, do
   if item > largest, then
      largest ← item;
   return largest;

// 當中 "←" 代表指定敘述－「A ← B」即係將 A 嘅數值設做 B；
// 而 "return X" 會終止個演算法，並且將 X 嘅數值攞嚟做輸出。

廿一世紀嘅研究者一般都會嫌呢個演算法唔夠好，原因係呢個演算法喺最壞情況（worst-case）嗰陣要睇嗮成個列先至搞得掂（O(n)，當中 n 係條陣列嘅長度），所以又有人諗咗第啲演算法出嚟做呢樣工作－而呢啲新演算法好多時都曉淨係睇個數字列嘅一小部份就經已搵得出想要嗰個數字。

運算概念

睇埋：運算複雜度

• 分治演算法
• 貪心演算法
• 線性搜尋
• 難解問題

遊戲運算

睇埋：已解遊戲、決策樹同蒙地卡羅樹搜尋

玩遊戲嗰陣要做決策，最直接嘅方法就係窮舉搜尋：窮舉搜尋可以輕易解決簡單嘅遊戲—例如井字過三關噉，井字過三關嘅第一步得三個可能性咁少—

• 填中間、
• 填角落（填左上角、填右上角、填左下角同填右下角功能上等同）同
• 填側邊（填左側、填右側、填上側同填下側功能上等同）。

而可能性少就表示，電腦唔使嘥好多時間同第啲資源，就可以睇晒所有嘅可能性。相比之下，國際象棋淨係第一步白棋行嗰刻已經有 20 個可能性咁多，而跟住落嚟可能性嘅數量會有爆發性嘅增長，喺十步之前已經會超過 100 萬個可能性^{[註 1]}，廿一世紀初嘅電腦仲未有足夠嘅運算能力，做唔到「將咁多個可能性逐個逐個攞嚟睇，喺合理咁短嘅時間內畀答案」。

睇埋

• 最佳化
• 複雜度
• 局部搜尋
• 《神嘅九十億個名》

引咗

1. Instantly share code, notes, and snippets. GitHubGist.

註解

1. 有關可能性嘅數量點樣計法，可以睇吓階乘呢個數學概念。