【正文】 in SUCCESSORS(state) do v← MAX(v, MIN VALUE(s)) return v (a=action招數(shù) ) Function MINVALUE(state) returns a utility value if TERMINALTEST(state) then return UTILITY(state) v← +∞ for a, s in SUCCESSORS(state) do v← MIN(v, MAX VALUE(s)) return v 第 2章 搜索技術(shù) 62 ??剪枝 ? 極大極小值搜索的問(wèn)題是狀態(tài)數(shù)隨著棋局步數(shù)的數(shù)量而指數(shù)級(jí)增長(zhǎng) — 不幸的是沒有辦法消除這種指數(shù)級(jí)增長(zhǎng)，所幸的是可以有效將其減半 — 剪枝技術(shù) ? 應(yīng)用于極大極小值搜索樹中 — ??剪枝 ? 剪掉那些不可能影響最后決策的分支，返回和極大極小值算法同樣的結(jié)果 ? 例子的剪枝過(guò)程中 MAXMIN(n)= max(min(3,12,8), min(2,x,y), min(14,5,2))= max(3,min(2,x,y),2)=max(3,z,2)=3 第 2章 搜索技術(shù) 63 博弈樹的剪枝 (1) 第 2章 搜索技術(shù) 3 [∞, +∞] A B [∞,3] (a) [∞, +∞] 12 A B 3 [∞,3] (b) 64 博弈樹的剪枝 (2) 第 2章 搜索技術(shù) 12 A B [3, +∞] 3 8 [3,3] (c) 12 A B C [3, +∞] [∞,2] 3 8 2 [3,3] (d) 65 博弈樹的剪枝 (3) 第 2章 搜索技術(shù) [∞,14] 12 A B D C [3,14] [∞,2] 3 8 2 14 [3,3] (e) 12 A B D C [3,3] [∞,2] [2,2] 3 8 2 14 5 2 [3,3] (f ) 66 ??剪枝算法 (1) ? 在極大極小值算法基礎(chǔ)上增加了剪枝功能，即在返回值基礎(chǔ)上增加了判斷 Function ALPHABETASEARCH(state) returns an action inputs: state (current state in game) v← MAX VALUE(state, ∞, +∞) return the action in SUCCESSORS(state) with value v 第 2章 搜索技術(shù) 67 ??剪枝算法 (2) Function MAXVALUE(state,?, ? ) returns a utility value inputs: state ?, the value of the best alternative for MAX along the path to state ?, the value of the best alternative for MIN along the path to state if TERMINALTEST(state) then return UTILITY(state) v← ∞ for a, s in SUCCESSORS(state) do v← MAX(v, MIN VALUE(s,?, ? )) if v≥? then return v ? ← MAX( ?, v) return v 第 2章 搜索技術(shù) 68 ??剪枝算法 (3) Function MINVALUE(state, ?, ? ) returns a utility value inputs: state ?, the value of the best alternative for MAX along the path to state ? the value of the best alternative for MIN along the path to state if TERMINALTEST(state) then return UTILITY(state) v← +∞ for a, s in SUCCESSORS(state) do v← MIN(v, MAX VALUE(s, ?, ? )) if v≤? then return v ? ← MIN( ?, v) return v 第 2章 搜索技術(shù) 69 ??剪枝算法的說(shuō)明 ? ??剪枝 可以應(yīng)用樹的任何深度，許多情況下可以剪掉整個(gè)子樹 / 其原則是 —如果在節(jié)點(diǎn) n的父節(jié)點(diǎn)或者更上層的節(jié)點(diǎn)有一個(gè)更好的選擇 m，則在實(shí)際游戲 (搜索 )中永遠(yuǎn)不會(huì)到達(dá) n ? ?=到目前為止在路徑上任意點(diǎn)發(fā)現(xiàn)的 MAX最佳選擇 ? ?=到目前為止在路徑上任意點(diǎn)發(fā)現(xiàn)的 MIN最佳選擇 ? ??搜索不斷更新 ?/?值，當(dāng)某個(gè)節(jié)點(diǎn)的值分別比 ?/?值更差時(shí)剪掉該節(jié)點(diǎn)的剩余分支 第 2章 搜索技術(shù) 70 ??剪枝的效率 ? ??剪枝的效率很大程度上取決于檢查后繼節(jié)點(diǎn)的次序 —應(yīng)該先檢查那些可能最好的后繼 ? 如果能夠先檢查那些最好的后繼，則 ??剪枝算法只需檢查 O(bd/2)個(gè)節(jié)點(diǎn)以決定最佳招數(shù) / 極大極小值算法為 O(bd)—有效分支因子 b到 b的平方根 —效率大大提高 第 2章 搜索技術(shù) 71 本章復(fù)習(xí)提示 ? 用各種搜索算法解決問(wèn)題 (編程練習(xí) ) ? 具體搜索問(wèn)題的形式化表示 (初始狀態(tài) /后繼函數(shù) /搜索代價(jià)等 ) ? 了解各種搜索算法 (包括局部搜索和博弈搜索 )的思想、相關(guān)性質(zhì)和性能 ? 約束滿足問(wèn)題的相關(guān)概念 ? 嘗試使用搜索方式求解實(shí)際問(wèn)題 / 考慮具體任務(wù)的相關(guān)知識(shí) 第 2章 搜索技術(shù) 72 參考書目 ? Stuart Russell / Peter Norvig: AIMA 第 3章 / 第 4章 / 第 5章 / 第 6章 ? 陸汝鈐 編著 : 人工智能 (上冊(cè) ) 第 5章 / 第 6章 / 第8章 / 第 9章 ? 田盛豐、黃厚寬，人工智能與知識(shí)工程，中國(guó)鐵道出版社， 1999年 8月第 1版，第 4章 / 第 9章 ? Vipin Kumar, Algorithms for Constraint Satisfaction Problems, AI Magazine, V13, N1(1992), pp32~44 第 2章 搜索技術(shù) 73 附錄 A*算法可采納性的證明 第 2章 搜索技術(shù) 74 A*算法可采納性 ? 定理： ? A*算法是可采納的，即若存在從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg的路徑，則 A*算法必能結(jié)束在最佳路徑上 ? 證明的過(guò)程： ? 首先證明 A*算法必定成功結(jié)束 ? 其次證明 A*算法結(jié)束時(shí)中止于最佳路徑 第 2章 搜索技術(shù) 75 證明的步驟 ? 證明分為三步： (1)對(duì)于有限圖， A*算法一定成功結(jié)束 (2)對(duì)于無(wú)限圖， A*算法一定成功結(jié)束 (3)A*算法必定終止于最佳路徑上 ? 對(duì)于無(wú)限圖情況的證明，引入 2個(gè)引理 (1)如果 A*算法不終止，則存在 f值任意大的節(jié)點(diǎn) (2)A*算法結(jié)束前，仍有耗散值更小的節(jié)點(diǎn)待擴(kuò)展 第 2章 搜索技術(shù) 76 定理 1的證明 (1) ? 定理 1— 對(duì)于有限圖，如果從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg有路徑存在，則 A*算法一定成功結(jié)束 ? 證明： ? 首先證明算法必定會(huì)結(jié)束 ? 由于搜索圖為有限圖，如果算法能找到解，則會(huì)成功結(jié)束；如果算法找不到解，則必然會(huì)由于 Open表變空而結(jié)束。因此， A*算法必然會(huì)結(jié)束 第 2章 搜索技術(shù) 77 定理 1的證明 (2) ? 然后證明算法一定會(huì)成功結(jié)束 ? 由于至少存在一條由初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑，設(shè)此路徑為 ? S0= n0， n1