【正文】 中加到每一個節(jié)點上 AND或 OR的標記是取決于該節(jié)點對其父節(jié)點的關系。第四章 可分解產(chǎn)生式系統(tǒng)的搜索策略 學習目標： 了解一般的與 /或圖搜索問題，掌握與 /或圖的啟發(fā)式搜索算法 AO*。如復合狀態(tài)分解后擁有一組 “與 ”關系的后繼節(jié)點；而分量狀態(tài)經(jīng)可應用規(guī)則作用后，生成一組“或 ”關系的后繼節(jié)點。 Note:若所有的連接符都是 1連接符， 則得到的就是與 /或圖的特例 普通有向圖。 6→3,3 4→3,1 6→4,2 3→2,1 4→2,2 2→1,1 使用這些規(guī)則把 6轉換成由 1組成的數(shù)字串。使用連接符的費用可以計算解圖的費用． ? 設從節(jié)點 n到終止節(jié)點集合 N的 解圖的費用 用 k(n, N)表示，則 k(n, N)遞歸定義如下： 1. 若 n是 N中的元素，則 k(n, N) =0； 3/11/2023 13 與 /或圖搜索 2. 若有從 n出發(fā)的一個連接符指向它的解圖后繼節(jié)點｛ n1， … ， ni｝，設此連接符的費用為Ci，則 : k(n, N)= Ci+ k(n1, N)+…+k(n i, N) ? 最佳解圖 ：具有最低費用的解圖 3/11/2023 14 設 k連接符的費用為 k，計算 k(n0, N) n0 n1 n3 n5 n6 n8 n7 a n0 n4 n5 n7 n8 b n0 n4 n5 n7 n8 c 3/11/2023 15 與 /或圖搜索 ? 假定 h*(n)是從 n出發(fā)的最佳解圖的費用， h(n)是 h*(n)的估計值。 3/11/2023 17 搜索過程還要標記能解節(jié)點（ SOLVED），為此給出如下定義： 能解節(jié)點（ SOLVED） ①終止節(jié)點是能解節(jié)點； ②若非終止節(jié)點有 “或 ”子節(jié)點時，其子節(jié)點有一能解，則該非終止節(jié)點是能解節(jié)點； ③若非終止節(jié)點有 “與 ”子節(jié)點時，若其子節(jié)點均能解，則該非終止節(jié)點是能解節(jié)點 。 結論：對節(jié)點 n的評價，實際上是對 初始節(jié)點 節(jié)點 n目標節(jié)點 這一條路徑的評價。初始節(jié)點 節(jié)點 n目標節(jié)點 39。 第一階段：自頂向下的圖生成過程。 3/11/2023 21 AO*算法解析： 第二階段：費用值計算過程。 8． Until S變空， do： 9． begin 10．從 S中刪除節(jié)點 m，滿足 m在 G中的后裔不 出現(xiàn)在 S中 與 /或圖搜索 …… 算法 AO* 3/11/2023 27 11． 按以下步驟修改 m的費用 q(m)： 對于每一從 m出發(fā)的指向節(jié)點集合 {n1i， … ， nki} 的連接符，計算 qi(m)=ci+q(n1i)+…+q(n ki)， q(m):＝ min {qi(m)}。 h (n0)＝ 0， h(n1)＝ 2， h(n2)＝ 4， h(n3)＝ 4， h(n4)＝ 1， h(n5)＝ 1， h(n6)＝ 2， h(n7)＝ h(n8)＝ 0（目標節(jié)點）。 圖 (e) 搜索得到的解圖 3/11/2023 35 Note （ 1）在第 6步擴展節(jié)點 n時，若不存在后繼節(jié)點（即陷入死胡同），則可在第 11步中對 m（即n）賦一個高的 q值，這個高的 q值會依次傳遞到 s，使得含有節(jié)點 n的子圖具有高的 q（ s），從而排除了被當作候選局部解圖的可能性。（要求：使用 AO*算法，畫出各次循環(huán)圖，標明各點費用 q(n)，畫出最后的最佳解圖，并指明最佳解圖的費用） 3/11/2023 38 練習 2’： 一個產(chǎn)生式系統(tǒng)使用下面一組重寫規(guī)則，這些重寫規(guī)則把左面的數(shù)字轉換成右邊的數(shù)字串。 3/11/2023 39 博弈樹搜索 博弈 ? 具有競爭或對抗性質的行為稱為博弈行為。 ? 博弈論 Game Theory 博弈論就是研究博弈行為中斗爭各方是否存在著最合理的行為方案，以及如何找到這個合理的行為方案的數(shù)學理論和方法。 ? 近代對于博弈論的研究，開始于策墨洛（ Zermelo），波雷爾（ Borel）及馮 1944年，馮 納什 （ John Forbes Nash Jr）利用不動點定理證明了均衡點的存在，為博弈論的一般化奠定了堅實的基礎。 3/11/2023 41 博弈分類 根據(jù)不同的基準有不同的分類 ? 合作博弈和非合作博弈。 ? 按照參與人對其他參與人的了解程度分為完全信息博弈和不完全信息博弈。于是 警方分開囚禁嫌疑犯，分別和二人見面，并向雙方提供以下相同的 選擇： ? 若一人認罪并作證檢舉對方（稱 “背叛 ”對方），而對方保持沉默，此人將即時獲釋，沉默者將判監(jiān) 10年。參與者某一策略所得利益，如果在任何情況下都比其他策略要低的話，此策略稱為 “嚴格劣勢 ”，理性的參與者絕不會選擇。 二人面對的情況一樣，所以二人的理性思考都會得出相同的結論 ——選擇背叛，結果二人同樣服刑 2年。均衡狀況會是兩個囚徒都選擇背叛，結果二人判決均比合作為高，總體利益較合作為低。 （ 2）信息完備，對壘雙方所得到的信息是一樣的， 不存在一方能看到，而另一方看不到的情況。 3/11/2023 45 ? 零和博弈 （ zero sum game）： 是指博弈的參與者中 ,一方之所得是它方之所失 ,總量上看 ,支付水平不起變化或者為零。 譬如，在戀愛中一方受傷的時候，對方并不是一定得到滿足。 比如目前的中美關系，就并非 “非此即彼 ”，而是可以合作雙贏。 自然的策略可以是：天旱、多雨、風調雨順。 3/11/2023 47 ? 雙人博弈： 夫妻吵架 夫妻雙方都有兩種策略，強硬或軟弱。如果有一只豬去踩踏板，另一只豬就有機會搶先吃到另一邊落下的食物。規(guī)則的核心指標是：每次落下的食物數(shù)量和踏板與投食口之間的距離。 結果：是小豬大豬都不去踩踏板了。 結果：小豬、大豬都會去踩踏板。 對于游戲規(guī)則的設計者來說，這個規(guī)則的成本相當高（每次提供雙份的食物）；而且因為競爭不強烈，想讓豬們?nèi)ザ嗖忍ぐ宓男Ч⒉缓谩５却卟坏檬?，而多勞者多得? 3/11/2023 53 ? 原版的 “智豬博弈 ”故事給了競爭中的弱者（小豬）以等待為最佳策略的啟發(fā)。 ? 許多人并未讀過 “智豬博弈 ”的故事，但是卻在自覺地使用小豬的策略。 ? 對于帶機遇性的任何博弈，因不具有完備信息，不屬這里討論范圍，但有些論述可推廣到某些機遇博弈中應用。而對于輪到對方走棋時，對于我方來說，必須能夠應付對手的每一種走棋。 分錢幣問題是一種簡單的博弈問題。 3/11/2023 58 Grundy博弈狀態(tài)空間圖 3/11/2023 59 ? 實現(xiàn)一種取勝的策略就是搜索一個解圖的問題，解圖就代表一種完整的博弈策略。 而圍棋更復雜了。 3/11/2023 62 二、極小極大過程 極小極大過程模擬的就是人的一種思維過程。 對在一定深度處的節(jié)點所代表的局面 進行評價優(yōu)劣的估計值． ? 靜態(tài)估值函數(shù)因游戲而異． 如果對自己（ MAX）有利，則取正值，越大，表示對我方越有利。 3/11/2023 64 極小極大過程基本思想： 當輪到我方走棋時，首先按照一定的搜索深度生成出給定深度以內(nèi)的所有狀態(tài)，計算所有葉節(jié)點的靜態(tài)估值函數(shù)值。 3/11/2023 65 ? 極小極大原則 MAX節(jié)點在其 MIN子節(jié)點的倒推值中選 max； MIN節(jié)點在其 MAX子節(jié)點的倒推值中選 min ? 倒推值 在極小極大過程中，第 i層節(jié)點根據(jù)第 i+1層節(jié)點的值使用極小極大原則而獲得的值。實現(xiàn)該倒推值的走步就是相對好的走步。 IF np∈ MIN，且對 np的任意子節(jié)點 nci， e（ nci）都有值 THEN e（ np） :＝ min{e（ nci） }， REMOVE（ np， CLOSED）； 若 MIN所有子節(jié)點均有值，則該 MIN取其極小值。 靜態(tài)估計函數(shù) e(p)： (1)若 p是 MAX獲勝的格局，則 e(p)＝ ∞； (2)若 p是 MIN獲勝的格局，則 e(p)＝－ ∞。