人工智能與或圖搜索.ppt

《人工智能與或圖搜索.ppt》由會員分享，可在線閱讀，更多相關《人工智能與或圖搜索.ppt（35頁珍藏版）》請在裝配圖網上搜索。

第四章與或圖搜索 4 1問題歸約法4 2與或圖4 3與或圖搜索4 4AO 算法4 5博弈樹的搜索 4 1問題歸約法 當問題復雜時 可把初始問題分解成若干簡單的子問題 若子問題仍復雜 可再進一步分解 直到這些子問題的解可直接得到 這種問題的描述和求解方法 稱為問題歸約法 可直接解答的問題稱為本原問題 它是不必證明的 自然成立的 歸約法的問題表示可由下列三部分組成 1 一個初始問題的描述 2 一組把問題變成子問題的算子 3 一組本原問題的描述問題歸約由問題出發(fā) 運用操作算子產生一些子問題 對子問題再運用操作算子產生子問題的一些子問題 一直進行到產生的子問題都為本原問題 則問題得解 由于一問題所產生的若干子問題內的關系是并列的 同時的 所以 用與或圖便能表示問題歸約的狀態(tài)空間 即對問題歸約的描述可以很方便地用一個與或圖的結構來表示它 4 2與或圖 與節(jié)點 一個歸約算子能夠把單個問題變?yōu)閹讉€子問題組成的集合 這時只有當所有子問題都有解 該父輩節(jié)點才有解 這種關系稱為 與 關系 對應的節(jié)點稱為與節(jié)點 或節(jié)點 幾個算子適用于同一個問題 從而產生不同的后繼問題集合 這時只要有一個后繼集合有解 則意味該父輩問題有解 此時關系是 或 關系 對應節(jié)點稱為或節(jié)點 與節(jié)點由與運算連接 如圖 a 中Q和R 并用一條弧線將相關的邊連接起來 這種弧線及所相關的邊被稱為超弧 或節(jié)點由或運算連接 如圖4 1 b 中Q和R 與或圖是一種普遍圖 這種圖被稱為超圖 也就是說 超圖是存在超弧的圖 一超弧所相關的邊數(shù) K 被稱為該超弧的度 實現(xiàn)的連接為K 連接 K 連接符 假設節(jié)點N被某個算子歸約為一個包含K個子問題的替換集合 K 1 我們用一個叫做K 連接符的超弧線把它們和節(jié)點N連接起來 每個K 連接符從一個父節(jié)點指向一個含有K個后繼節(jié)點的集合 并說N有一個外向連接符K 問題歸約描述對應的結構就是一個與或圖 原始問題描述對應于起始節(jié)點 或根節(jié)點 本原問題所對應的節(jié)點叫做葉節(jié)點 在某些特殊情況下 不出現(xiàn)任何與節(jié)點 所有超弧的度都為1 此時的圖成了普通圖 問題歸約描述也就成為狀態(tài)空間描述 從圖4 2所示的與或圖中 節(jié)點n0有兩個連接符 1 連接符指向節(jié)點n1 2 連接符指向節(jié)點集合 n4 n5 對于節(jié)點n0來講 n1可稱為或節(jié)點 n4 n5可稱為與節(jié)點 圖4 2 與或圖 4 3與或圖搜索 在與或圖上執(zhí)行搜索的過程 其目的在于表明起始節(jié)點是有解的 也就是說 搜索不是去尋找目標節(jié)點 而是尋找一個解圖 一個節(jié)點被稱為是能解節(jié)點 SOLVED 其遞歸定義為 1 終節(jié)點是能解節(jié)點 直接與本原問題相關聯(lián) 2 若非終節(jié)點有 或 子節(jié)點時 當且僅當其子節(jié)點至少有一個能解 該非終節(jié)點才能解 3 若非終節(jié)點有 與 子節(jié)點時 當且僅當其子節(jié)點均能解 該非終節(jié)點才能解 一個節(jié)點被稱為是不能解節(jié)點 UNSOLVED 其遞歸定義為 1 沒有后裔的非終節(jié)點是不能解的節(jié)點 2 若非終節(jié)點有 或 子節(jié)點時 當且僅當所有子節(jié)點均不能解時 該非終節(jié)點才不能解 3 若非終節(jié)點有 與 子節(jié)點時 當至少有一子節(jié)點不能解時 該非終節(jié)點才不能解 一個解圖就是那些能解節(jié)點的子圖 是包含一節(jié)點 n 到目的節(jié)點集合 N 的 連通的能解節(jié)點的子圖 其定義如下 一個與或圖G中 從節(jié)點n到節(jié)點集N的解圖記為G G 是G的子圖 1 若n是N的一個元素 則G 由單個節(jié)點n組成 2 若n有一個指向節(jié)點集 n1 nk 的外向連接符K 使得從每一個節(jié)點ni到N有一個解圖 i 1 k 則G 由節(jié)點n 連接符K 以及 n1 nk 中的每一個節(jié)點到N的解圖所組成 3 否則n到N不存在解圖 如果n s為初始節(jié)點 則此解圖即為所求解問題的解圖 在對普通圖的解路求解或搜索中 一般須計算或估計其路徑代價 同樣地 在搜索與或圖解圖的過程中 也需要進行耗散值的計算 設連接符的耗散值規(guī)定為 k 連接符的耗散值 k 若解圖的耗散值記為k n N 則可遞歸計算如下 1 若n是N的一個元素 則k n N 0 2 若n有一個外向連接符指向后繼節(jié)點集合 n1 ni 并設該連接符的耗散值為Cn 則k n N Cn k n1 N k ni N 具有最小耗散值的解圖稱為最佳解圖 其值也用h n 標記 求解問題的解圖的值為h s 解圖的求法是 從節(jié)點n開始 正確選擇一個外向連接符 如此進行下去直到由此產生的每一個后繼節(jié)點成為集合N中的一個元素為止 圖4 3給出了上圖所示與或圖中n0 n7 n8 的三個解圖 解圖的耗散值分別為8 7 5 圖4 3 三個解圖 與或圖搜索與狀態(tài)空間圖搜索的不同 搜索目的是證明起始節(jié)點是否可解 而可解節(jié)點是遞歸定義的 取決于后繼節(jié)點是否可解 即搜索是否找到可解的葉節(jié)點 因此 搜索有可解標示過程和不可解標示過程 初始節(jié)點被標示為可解 則搜索成功結束 初始節(jié)點被標示為不可解 則搜索失敗 一旦發(fā)現(xiàn)不可解節(jié)點 應把該節(jié)點從圖中刪去 4 4AO 算法 假設 估價函數(shù)q n h n G為當前擴展生成的與或圖 G 為一后選局部解圖 是G的一個子圖 h n 是節(jié)點n的啟發(fā)函數(shù) 而q n 是節(jié)點n的估價函數(shù) 是從節(jié)點n到一組終葉節(jié)點的一個最優(yōu)解圖的一個代價估計 過程AO 1 建立一個搜索圖G G s 計算q s h s IFGOAL s THENM s SOLVED 開始時圖G只包括s 耗散值估計為h s 若s是終節(jié)點 則標記上能解 2 Untils已標記為SOLVED do 3 Begin4 G FIND G 根據(jù)連接符標記 指針 找出一個待擴展的局部解圖G G的連接符將在第11步中標記 5 n G 中的任一非終節(jié)點 選一個非終節(jié)點作為當前節(jié)點 6 EXPAND n 生成子節(jié)點集 ni G ADD ni G 計算q ni h ni 如果ni G IFGOAL ni THENM ni SOLVED 對G中原未出現(xiàn)的n的子節(jié)點添加到G中 并計算其耗散值 若n的子節(jié)點為終節(jié)點則加能解標記 7 S n 建立含n的單一節(jié)點集合S 待修正的節(jié)點集合 8 UntilS為空 do 9 begin10 REMOVE m S 當mc S 從集合S中移出一節(jié)點m 要求這個m在圖G中的子節(jié)點mc 不出現(xiàn)在S中 從底層開始修正 11 根據(jù)下面方法修改m的耗散值q m 對m指向節(jié)點集 n1i n2i nki 的每一個連接符i分別計算qi qi m Ci q n1i q nki q m minqi m 對m的i個k 連接符 取計算結果最小的那個連接符的耗散值為節(jié)點m的q m 加指針到minqi m 的連接符上 或把指針修改到minqi m 的連接符上 即原來指針與新確定的不一致時應刪去 IFM nji SOLVED THENM m SOLVED j 1 2 k 若該連接符的所有子節(jié)點都是能解的 則m也標上能解 12 IFM m SOLVED q m q0 m THENADD ma S m能解或修正的耗散值與原先估算q0不同 則把m的所有先輩節(jié)點ma 添加到S中 修正向上傳遞 13 end14 end AO 搜索算法可以理解為兩個主要過程的重復 首先 是一個自上而下的圖生長過程 4 6步 先通過有標記的連接符 找到目前為止最好的一個局部解圖 然后對其中一個非終節(jié)點進行擴展 并對其后繼節(jié)點賦估計耗散值和加能解標記 第2過程是一個自下而上的估價函數(shù)值的修正 連接符的標記和SOLVED的標注過程 耗散值的修正從剛被擴展的節(jié)點n開始 其修正耗散值q n 取對h n 的所有估計值中最小的一個 然后根據(jù)耗散值遞歸計算公式逐級向上修正其先輩節(jié)點的耗散值 只有下層節(jié)點耗散值修正后 才可能影響到上一層節(jié)點的耗散值 因此必須自底向上一直修正到初始節(jié)點 假設各節(jié)點的啟發(fā)函數(shù)值分別為 h n0 3 h n1 2 h n2 4 h n3 4 h n4 1 h n5 1 h n6 2 h n7 h n8 0 目標節(jié)點 k 連接符的耗散值 k 應用AO 算法 經過四個循環(huán) 可找到解圖 在第一次循環(huán)中 擴展節(jié)點n0 下一次循環(huán)擴展節(jié)點n1 接著擴展節(jié)點n5 最后擴展節(jié)點n4 在節(jié)點n4被擴展之后 節(jié)點n0便被標注SOLVED 此時 通過向下跟蹤有標記的連接符 便獲得了此狀態(tài)空間的解圖 圖4 4 AO 搜索過程每個節(jié)點旁邊標記的是啟發(fā)函數(shù)h n 值 不帶括號 或估價函數(shù)q n 的修正值 帶括號 短箭頭用來標記連接符 標明侯選局部解圖 已經標注SOLVED的節(jié)點用實心圓來表示 4 5博弈樹的搜索 博弈一直是啟發(fā)式搜索的一個重要應用領域 早在20世紀60年代就已經出現(xiàn)若干個博弈系統(tǒng) 美國IBM公司的 深藍 系統(tǒng)已達到了國際特級大師級的水平 97年勝了卡斯帕羅夫 2001年 德國的 更弗里茨 軟件擊敗了世界排名10位中的9位 本節(jié)所指博弈問題是指二人完備博弈 1 由二人對壘 二人嚴格地輪流走步 自己的走步自己選擇 2 任何一方都完全知道對方過去的走步情況和今后可能的走步 不包括碰運氣的情況 由于在決定自己走步時只需考慮對自己有利的一步 或 而考察對方時 則應考慮對方所有可能的走步 與 因此 能夠利用與或圖搜索算法來解決博弈問題 另外 由于兩人嚴格地輪流走步 使博弈狀態(tài)圖呈現(xiàn)出嚴格的與或圖的交替層次 所以 可設計特殊的與或圖搜索算法 博弈樹搜索算法 使搜索更有效 4 5 1Grundy博弈 例 假設桌上放有一堆 7個 錢幣 由兩人輪流進行分堆 要求每人每次只把其中某堆錢幣分成數(shù)目不相等的兩小堆 最后不能分下去的人為負 該問題的描述 綜合數(shù)據(jù)庫 用無序數(shù)字序列x1 x2 xn表示n堆錢幣不同的個數(shù) 再用兩個說明符號MIN方和MAX方代表選手 無序數(shù)列和符號M組合 x1 x2 xn M 就代表該由某個選手走步的狀態(tài) MAX方代表努力贏的一方 或盡力將其贏的幾率最大化的一方 而MIN方代表力圖使MAX方偏離取勝目標的另一方 博弈雙方總是偏向最有利于自己的狀態(tài)前進 反過來說 也就是MIN方和MAX方總是移向最不利于對方的狀態(tài) 規(guī)則 圖4 5 Grundy博弈問題狀態(tài)空間圖 設初始狀態(tài)為 7 MIN 則該問題的狀態(tài)空間圖如圖4 5所示 圖中所有終節(jié)點均表示要走步的選手必輸?shù)那闆r 取勝方的目標是設法使棋局發(fā)展為結束在對方走步時的終節(jié)點上 因此節(jié)點A是MAX的搜索目標 而節(jié)點B C則為MIN的搜索目標 搜索策略要考慮的問題是 以MAX方的角度 對MIN走步后的每一個MAX節(jié)點 該狀態(tài)由MIN控制 必須證明MAX對MIN所有可能走的每一個棋局對弈后都能夠獲勝 即MAX必須考慮應付MIN的所有招法 這是一個與的含義 因此含有MAX符號的節(jié)點可看成與節(jié)點 對MAX走步后的每一個MIN節(jié)點 該狀態(tài)由MAX控制 只需要證明MAX有一步能走贏就可以 即MAX只要考慮能走出一步棋使MIN無法招架就成 因此含有MIN符號的節(jié)點可看成或節(jié)點 于是對弈過程的搜索圖就呈現(xiàn)出與或圖表示的形式 從搜索圖可以看出 MAX方存在完全取勝的策略 圖中所示部分就代表了這種策略 這時不論MIN怎么走 MAX方均可取勝 因而尋找MAX的取勝的策略便和求與或圖的解圖 能解 能勝 一致起來 即MAX要獲勝 必須對所有與節(jié)點取勝 但只需對一個或節(jié)點取勝 這就是一個解圖 因此實現(xiàn)一種取勝的策略就是搜索一個解圖的問題 解圖就代表一種完整的博弈策略 4 5 2博弈樹的極大極小搜索法 極大極小搜索法是考慮雙方對弈若干步之后 從可能的走步中選一步相對好的走步來走 即在有限的搜索深度范圍內進行求解 這需定義一個評價函數(shù)f 以便對棋局的勢態(tài) 節(jié)點 作出優(yōu)劣估值 一般規(guī)定有利于MAX的勢態(tài) f n 取正值 有利于MIN的勢態(tài) f n 取負值 勢均力敵 f n 0 若f n 表示MAX方獲勝 若f n 表示MIN方獲勝 假定開始由MAX選擇走一步棋 如何選擇一步好棋 首先 對給定的格局MAX給出可能的走法 然后MIN對MAX的每一步走法 又給出可能的走法 這樣進行若干次 一定深度 得到一組端節(jié)點 每個端節(jié)點有相應的靜態(tài)函數(shù)值 然后由底向上逐級計算倒推估值 在MIN處取其下層估值中最小者 在MAX處取其下層估值最大者 一直到MAX的開始棋局 取其下層估值中最大的格局作為要走的第一步 圖4 6是一個表示考慮兩步棋的例子 圖中端節(jié)點的數(shù)字是用靜態(tài)函數(shù)f n 計算得到 其他節(jié)點應用倒推的方法取值 圖中A B C是MIN方要走步的節(jié)點 MAX方應考慮其最壞的情況 故其估值應分別取其子節(jié)點估值中最小者 而s是MAX走步的節(jié)點 可考慮最好的情況 故其估值應取A B C值中最大者 這樣 確定了f s 2 也就是說 相對較優(yōu)的走步是走向B 因為從B出發(fā) 對手不可能產生比f s 2更差的效果 當用端節(jié)點的靜態(tài)估計函數(shù)值求倒推值時 兩位選手應采用不同的策略 從下往上逐層交替使用極大和極小的選值方法 故稱為極大極小過程 圖4 6 f n 求值過程 下面說明極大極小過程MINLMAX 思維過程 1 T s MAX OPEN s CLOSED 開始時樹由初始節(jié)點構成 OPEN表只含有S 2 LOOP1 IFOPEN THENGOLOOP2 3 n FIRST OPEN REMOVE n OPEN ADD n CLOSED 將n放到CLOSED表的前面 使第5步操作時深度大的節(jié)點優(yōu)先被取出 OPEN表先進先出 CLOSED表后進先出 4 IFn可直接判定為贏 輸或平局THENf n 0 GOLOOP1ELSEEXPAND n ni ADD ni T IFd ni kTHENADD ni OPEN GOLOOP1ELSE計算f ni ni達到深度k 計算各端節(jié)點f值 5 LOOP2 IFCLOSED NIL THENGOLOOP3ELSEnd FIRST CLOSED 6 IF nd MAX f nci MIN 有值 THENf nd max f nci REMOVE nd CLOSED GOLOOP2 若MAX所有子節(jié)點均有值 則該MAX取其極大值 ELSEIF nd MIN f nci MAX 有值 THENf nd min f nci REMOVE nd CLOSED GOLOOP2 若MIN所有子節(jié)點均有值 則該MIN取其極小值 7 ELSEGOLOOP1 若有子節(jié)點的值待確定 進入其它分支繼續(xù)進行節(jié)點的擴展 8 LOOP3 IFf s NILTHENEXIT END M Move T s有值 或則結束或標記走步 例 在九宮格棋盤上 甲乙 MAX和MIN 二人輪流在空格中放入自己的棋子 一次一枚 誰先使自己的三子成一線就獲勝 設甲先走用 表示 乙用 表示 p表示某種格局 f p 表示對格局的評價值 為便于討論 將棋盤的整行 整列或整條對角線稱為贏線 如果一條贏線上只有 方的棋子或為空 而沒有對方的棋子 那么這條贏線就稱為 方的贏線 f p 定義如下 1 MAX勝 f p 2 MIN勝 f p 3 若p不是可定勝負的格局 則f p fMAX p fMIN p 其中 fMAX p 表示當前棋局所有空格都放上MAX的棋子后 MAX的三個棋子成線的總數(shù) 同理 fMIN p 表示當前棋局所有空格都放上MIN的棋子后 MIN的三個棋子成線的總數(shù) 設考慮走兩步的搜索過程 利用棋盤對稱性的條件 則第一次調用算法產生的搜索樹如圖4 7所示 圖中端節(jié)點下面是計算的f p 值 非端節(jié)點的倒推值標記在圓圈內 為了使初始節(jié)點具有最大的倒推值 可以看出第1步的最好走法是把棋子下到中央位置 圖4 7 一字棋第1階段的搜索樹 設MAX走完第一步后 MAX的對手是在 上的格子下子 這時MAX就要在新的格局下調用算法 第2次產生的搜索樹如圖4 8所示 圖4 8 一字棋第2階段的搜索樹 類似地第3次的搜索樹如圖4 9所示 至此MAX走完最好的走步后 不論MIN怎么走 都無法挽回敗局 因此只好認輸了 否則還要進行下面的搜索 圖4 9 一字棋第3階段的搜索樹 4 5 3 搜索過程 在極大極小過程中 把生成樹和棋局估值兩個過程完全分離 即先生成全部的搜索樹 然后再進行端節(jié)點靜態(tài)估值和倒推值計算 這使效率大大降低 如圖4 9中 其中一個MIN節(jié)點要全部生成A B C D四個節(jié)點 然后還要逐個計算其靜態(tài)估值 最后在求倒推值階段 才賦給這個MIN節(jié)點的倒推值 若兩個過程同時進行 再根據(jù)一定的條件判斷 有可能盡早剪掉一些無用的分支 那么就可能減少搜索工作量 這是 搜索過程的基本思想 如 生成節(jié)點A后 馬上進行靜態(tài)估值 得知f A 后 就可以斷定再生成其余節(jié)點及進行靜態(tài)計算是多余的 可以馬上對MIN節(jié)點賦倒推值 絲毫不會影響MAX的最好優(yōu)先走步的選擇 為了使生成和估值過程緊密結合 采用有界深度優(yōu)先策略進行搜索 這樣當生成達到規(guī)定深度的節(jié)點時 就立即計算其靜態(tài)估值函數(shù) 而一旦某個非端節(jié)點有條件確定其倒推值時就立即計算賦值 圖4 10 一字棋第1階段 剪枝方法 從圖4 10中標記的節(jié)點生成順序號 也表示節(jié)點編號 看出 生成并計算完第6個節(jié)點后 第1個節(jié)點倒推值完全確定 可立即賦給倒推值 1 這時對初始節(jié)點來說 雖然其他子節(jié)點尚未生成 但由于S屬極大值層 可以推斷其倒推值不會小于 1 我們稱極大值層的這個下界值為 即可以確定S的 1 這說明S實際的倒推值絕不會比 1更小 具體的取值還取決于其他后繼節(jié)點的倒推值 因此繼續(xù)生成搜索樹 當?shù)?個節(jié)點生成出來并計算得靜態(tài)估值為 1后 就可以斷定第7個節(jié)點的倒推值不可能大于 1 我們稱極小值層的這個上界值為 即可確定節(jié)點7的 1 有了極小值層的 值 很容易發(fā)現(xiàn)若 時 節(jié)點7的其他子節(jié)點不必再生成 這不影響高一層極大值的選取 因S的極大值不可能比這個 值還小 再生成無疑是多余的 因此可以進行剪枝 于是 在搜索過程中通過記錄并比較倒推值的上下界并進行比較 就可以實現(xiàn)修剪操作 稱這種操作為 剪枝 類似的還有 剪枝 統(tǒng)稱為 剪枝技術 在實際修剪中 還可以隨時修正 但極大值層的倒推值下界值 永不下降 實際的倒推值取其后繼節(jié)點最終確定的倒推值中最大的一個倒推值 而極小值層的倒推值上界值 永不上升 其倒推值取其后繼節(jié)點最終確定的倒推值中最小的一個倒推值 總結上述敘述 在一個分支上進行 剪枝的規(guī)則描述如下 1 剪枝 若任一極小值層節(jié)點的 值小于或等于它任一先輩極大值層節(jié)點的 值 即 先輩層 后繼層 則可以終止該極小值層中這個MIN節(jié)點以下的搜索 并設置這個MIN節(jié)點的最終的倒推值為 極小值層節(jié)點的剪枝 2 剪枝 若任一極大值層節(jié)點的 值大于或等于它任一先輩極小值層節(jié)點的 值 即 后繼層 先輩層 則可以終止該極大值層中這個MAX節(jié)點以下的搜索過程 并設置這個MAX節(jié)點的最終倒推值為 極大值層節(jié)點的剪枝 過程 保存 和 值 并且當滿足條件時便進行剪枝 當初始節(jié)點的全部后繼節(jié)點的最終倒推值都給出時 過程即結束 而最好的優(yōu)先走步就是走向具有最高倒推值的那個后繼節(jié)點 顯然剪枝后選得的最好優(yōu)先走步 其結果與不剪枝的MAXMIN方法所得的完全相同 因而 過程具有較高的效率 比較是在極大值層節(jié)點和極小值層節(jié)點間進行的 比較時是與先輩層節(jié)點 已經有了值的那些節(jié)點 不僅限于父輩 只有一個節(jié)點的值固定以后 其值才能夠向其父節(jié)點傳遞 剪枝搜索得到的最佳走步與極大極小方法得到的結果一致 但效率會提高 生成搜索圖和剪枝過程同時進行 注意幾個問題 圖4 11給出了d 4的博弈樹的 搜索過程 其中括號中的數(shù)字表示求靜態(tài)估值及倒推值過程的次序編號 該圖詳細表示出 剪枝過程的若干細節(jié) 初始節(jié)點的最終倒推值是1 該值等于某一個端節(jié)點的靜態(tài)估值 圖4 11 搜索過程的博弈樹 剪枝 剪枝 剪枝 剪枝