伫列的特性.PPT

* 隨堂練習 1.請寫下 {43,68,10,35,27} 這個數字陣列用氣泡排序法排序時, 每一輪的結果。 2.請回顧第 13-3 節中提到的幾個計算最大公因數的程式, 並判斷何者是使用遞迴呼叫方式。 * 特別企劃－電腦如何下棋、玩遊戲？ 在1988年時, 當時世界西洋棋棋王 Gary Kasparov 還公開表示：電腦在 2000 年前是無法打敗大師級的西洋棋棋士。但結果棋王提出這個說法還不到十年, IBM 的深藍 (Deep Blue) 電腦就在一場 6 局的棋賽中, 以兩勝三和一負的成績打敗 Gary Kasparov。 * 特別企劃－電腦如何下棋、玩遊戲？ 雖然電腦在連續長時間的棋局中不會像人一樣產生疲倦、沮喪等負面情緒也是致勝因素之一, 但無論如何, 這場讓棋王吃鱉的比賽仍是人工智慧中遊戲理論(Game Theory) 應用的一大成就。 * 特別企劃－電腦如何下棋、玩遊戲？ 電腦之所以會下棋, 甚至還能下贏棋王, 其原理並不難, 基本上電腦是將每局棋各種可能的走法都建立成一個遊戲樹 (Game Tree) 的結構： * 特別企劃－電腦如何下棋、玩遊戲？ * 特別企劃－電腦如何下棋、玩遊戲？ 建好遊戲樹後, 下棋程式會用最小 - 最大值 (Min-Max, 取 Minimum、Maximum 的字首,也可寫成 Minimax) 演算法來決定要走哪一步。其方式是用一狀態函數來決定樹葉節點的『分數』, 以西洋棋為例, 決定分數的要素包括國王受保護的程度、棋子的數量、棋子的位置等。 * 特別企劃－電腦如何下棋、玩遊戲？ 若是玩象棋, 車傌炮的數量、位置的重要性可能大於兵卒, 所以車傌炮都沒死可得較多分數...；當然對手的狀態、棋子的種類也都要予以考慮, 例如自己的兩炮都存活時可加 5 分, 則對方的雙包也都存活時則減 5 分...。 * 特別企劃－電腦如何下棋、玩遊戲？ * 特別企劃－電腦如何下棋、玩遊戲？ 經過一番計算後, 即可得到各樹葉節點的『分數』, 接著就要用最大-最小值的方式來決定最佳走法, 所謂最大值即表示當輪到電腦下時, 電腦當然是會選擇分數最高的走法；但對手走的時候則當然是選分數最低 (電腦評分低的盤面, 就是對手有利的盤面) 的走法。 換言之, 輪電腦走時, 該節點的分數是取子節點分數的最大值 (Max)；而對手走時, 該節點的分數則是取子節點分數的最小值 (Min)。 * 特別企劃－電腦如何下棋、玩遊戲？ * 特別企劃－電腦如何下棋、玩遊戲？ 依此運作原理, 電腦能『思考』的遊戲樹愈深、愈廣, 其下法將愈無懈可擊。然而西洋棋的盤面變化何止千億種, 既使是像深藍這樣快速的電腦, 也很難在『有限時間內』完成足夠算出最佳走法的計算, 因此對這種變化萬千的棋局, 需套用 α-β 縮減法 (Alpha-Beta Cut-off) 來減少計算的數量。 * 特別企劃－電腦如何下棋、玩遊戲？ α-β 縮減法的道理也很簡單, 在評估各樹葉的分數時, 我們先由左至右依次計算, 對需取 Max 值的那一層節點, 由於其上的 MIN 節點只會取最小值, 所以這個最小值即為再上一層 MAX 節點的 α 值。 之後在評估其它孫子 MAX 層的分數時, 只要已算出一節點分數小於 α 值, 同一子樹下的其它 MAX 節點就不必再考慮了, 可跳過改算另一 MIN 子樹下的 MAX 節點, 如此將可節省不少計算時間。 * 特別企劃－電腦如何下棋、玩遊戲？ * 特別企劃－電腦如何下棋、玩遊戲？ * 特別企劃－電腦如何下棋、玩遊戲？ 至於 β 值的原理也相似, 只不過 β 值是用在 Min 層, 也就是說它是由其下的 Max 層取得的一個下限值。若上圖的例子再延伸到第 4 層時, 則只要第 3 層的 Max 節點出現大於β 值的結果, 其下的其餘子樹就不必再算了。 透過這種方式, 雖然可讓電腦需計算的狀況縮減大半, 但以深藍的計算能力, 仍只能計算到 12 步的遊戲樹, 也因此在變化更複雜的圍棋領域, 人腦仍是勝過電腦一籌。 * 特別企劃－電腦如何下棋、玩遊戲？ 除了 Min-Max 演算法外, 在人工智慧的領域仍有許多啟發式 (Heuristics) 的演算法正被研究與應用, 例如近年來相當熱門的基因演算法 (Genetic Algorithm), 配合運算也飛快成長的電腦硬體, 在這個世紀看到機器人大師教小朋友下圍棋也不再只是夢想了。 * 隨堂練習 1.請問 6 層的完滿二元樹共有幾個節點？ 2.請試將星期一到星期天的英文單字放在二元搜尋樹中, 若要讓搜尋任一個單字最多只要三個節點即可找到, 應如何擺放？ * 14-6 演算法簡介 前一章曾說過：解決問題的方法就是演算法, 但這是個廣義的說法。若要更嚴謹地地描述電腦程式所用的演算法, 則我