人工智能第三章_搜索策略-2ppt課件

1、2022/7/171啟發(fā)式搜索啟發(fā)式知識(shí)指點(diǎn)OPEN表排序的普通圖搜索：全局排序?qū)PEN表中的一切節(jié)點(diǎn)排序，使最有希望的節(jié)點(diǎn)排在表首。A算法， A*算法掌握！部分排序僅對(duì)新擴(kuò)展出來(lái)的子節(jié)點(diǎn)排序，使這些新節(jié)點(diǎn)中最有希望者能優(yōu)先取出調(diào)查和擴(kuò)展；爬山法了解，對(duì)深度優(yōu)先法的改良；2022/7/172 簡(jiǎn)單的搜索戰(zhàn)略： g(n)0, f(n)= h(n), 部分排序只排序新擴(kuò)展出來(lái)的子節(jié)點(diǎn)，即部分排序 簡(jiǎn)單易行，適用于不要求最優(yōu)解答的問(wèn)題求解義務(wù)。 1爬山法實(shí)現(xiàn)啟發(fā)式搜索的最簡(jiǎn)一方法。 類似于人爬山只需好爬，總是選取最陡處，以求快速登頂。 求函數(shù)極大值問(wèn)題非數(shù)值解法，依賴于啟發(fā)式知識(shí)，試探性地逐漸向頂

2、峰逼近 適用于能逐漸求精的問(wèn)題。 爬山法特點(diǎn)： 只能向上，不準(zhǔn)后退，從而簡(jiǎn)化了搜索算法；表達(dá)在： * 從當(dāng)前形狀節(jié)點(diǎn)擴(kuò)展出的子節(jié)點(diǎn)相當(dāng)于找到上爬的途徑中，將h(n)最小的子節(jié)點(diǎn)對(duì)應(yīng)于到頂峰最近的上爬途徑作為下一次調(diào)查和擴(kuò)展的節(jié)點(diǎn)，其他子節(jié)點(diǎn)全部丟棄。 不需設(shè)置OPEN和CLOSE表，由于沒(méi)有必要保管任何待擴(kuò)展節(jié)點(diǎn)； 爬山法對(duì)于單一極值問(wèn)題登單一山峰非常有效而又簡(jiǎn)便,對(duì)于具有多極值的問(wèn)題無(wú)能為力會(huì)錯(cuò)登上次頂峰而失敗：不能到達(dá)最頂峰。回溯戰(zhàn)略和爬山法 2022/7/173 2回溯戰(zhàn)略 可以有效地抑制爬山法面臨的困難保管了每次擴(kuò)展出的子節(jié)點(diǎn)，并按h(n)值從小到大陳列。 相當(dāng)于爬山的過(guò)程中記住了途經(jīng)

3、的岔路口途徑搜索失敗時(shí)回溯后退，向另一途徑方向搜索 回溯戰(zhàn)略和爬山法 2022/7/174 2回溯戰(zhàn)略 遞歸過(guò)程實(shí)現(xiàn)回溯戰(zhàn)略的有效方式 算法就取名為BACKTRACK(n),參數(shù)n為當(dāng)前被擴(kuò)展的節(jié)點(diǎn)， 初次調(diào)用時(shí)n即為初始形狀節(jié)點(diǎn)s； 分二個(gè)部分：* 判別當(dāng)前節(jié)點(diǎn)n的形狀，* 作搜索任務(wù)擴(kuò)展節(jié)點(diǎn)n，遞歸調(diào)用該算法，處置前往結(jié)果。回溯戰(zhàn)略和爬山法 2022/7/175令PATH、SNL、n、n 為部分變量： PATH-節(jié)點(diǎn)列表，指示解答途徑； SNL-當(dāng)前節(jié)點(diǎn)擴(kuò)展出的子節(jié)點(diǎn)列表； MOVE-FIRST(SNL)-把SNL表首的節(jié)點(diǎn)移出，作為下一次要加以擴(kuò)展的節(jié)點(diǎn)； n、n-分別指示當(dāng)前調(diào)查和下一

4、次調(diào)查的節(jié)點(diǎn)。 該遞歸過(guò)程的算法就取名為BACKTRACK(n),參數(shù)n為當(dāng)前被擴(kuò)展的節(jié)點(diǎn)，算法的初次調(diào)用式是BACKTRACK(s),s即為初始形狀節(jié)點(diǎn)。算法的步驟如下：1 假設(shè)n是目的形狀節(jié)點(diǎn)，那么算法的本次調(diào)用勝利終了，前往空表；2 假設(shè)n是失敗形狀，那么算法的本次調(diào)用失敗終了，前往FAIL；3 擴(kuò)展節(jié)點(diǎn)n，將生成的子節(jié)點(diǎn)置于列表SNL，并按評(píng)價(jià)函數(shù)f(k) = h(k)的值從小到大排序k指示子節(jié)點(diǎn)；4 假設(shè)SNL為空，那么算法的本次調(diào)用失敗終了，前往FAIL；5 n= MOVE-FIRST(SNL)；6 PATH = BACKTRACK(n)；7 假設(shè)PATH =FAIL, 前往到語(yǔ)句

5、4；8 將n加到PATH表首，算法的本次調(diào)用勝利終了，前往PATH。2022/7/176 2回溯戰(zhàn)略 三種失敗形狀： 不合法形狀如傳教士和野人問(wèn)題中所述的那樣 舊形狀重現(xiàn)如八數(shù)碼游戲中某一棋盤規(guī)劃的重現(xiàn)，會(huì)導(dǎo)致搜索算法死循環(huán)， 形狀節(jié)點(diǎn)深度超越預(yù)定限制例如八數(shù)碼游戲中，指示解答途徑不超越6步。 回溯條件 失敗形狀，由算法第2句指示； 搜索進(jìn)入“死胡同，由該算法的第(4)句定義?；厮輵?zhàn)略和爬山法 2022/7/177 2回溯戰(zhàn)略 解答途徑的生成從相應(yīng)于目的形狀節(jié)點(diǎn)的空表開(kāi)場(chǎng)，遞歸前往PATH。 影響回溯算法效率的關(guān)鍵要素回溯次數(shù)。 回溯搜索到失敗形狀時(shí)的一種彌補(bǔ)行為， 準(zhǔn)確選擇下一步搜索調(diào)查的節(jié)

6、點(diǎn)大幅度減少甚至防止回溯。 設(shè)計(jì)好的啟發(fā)式函數(shù)h(n)是至關(guān)重要的?；厮輵?zhàn)略和爬山法 2022/7/178課堂練習(xí):提高題在運(yùn)用遞歸回溯算法處理四皇后的問(wèn)題中，假設(shè)按行的序號(hào)從小到大試探性放置各列的皇后，請(qǐng)畫(huà)出搜索圖，并指出分別從算法第2步和第4步回溯的次數(shù)。2022/7/179 定義L，為表示明晰起見(jiàn),L表中只記載皇后所在列,皇后所在行可由在L表中的先后位置指示,例如L=(1 3)指示兩個(gè)皇后位置分別為第1行第1列和第2行第3列。搜索圖(樹(shù))如右圖所示:共回溯22次,其中算法第2步的回溯18次,算法第4次的回溯4次。2022/7/17103.4 問(wèn)題歸約和與或圖啟發(fā)式搜索問(wèn)題歸約是人求解問(wèn)題

7、常用的戰(zhàn)略：把復(fù)雜的問(wèn)題變換為假設(shè)干需求同時(shí)處置的較為簡(jiǎn)單的子問(wèn)題后再加以分別求解只需子問(wèn)題全部處理時(shí)，問(wèn)題才算處理；問(wèn)題的解答由子問(wèn)題的解答結(jié)合構(gòu)成。本節(jié)主要內(nèi)容：?jiǎn)栴}歸約的描畫(huà)了解與或圖搜索的根本過(guò)程了解與或圖的啟發(fā)式搜索掌握2022/7/1711問(wèn)題歸約法Problem Reduction Representation子問(wèn)題1子問(wèn)題n原始問(wèn)題子問(wèn)題集本原問(wèn)題2022/7/1712問(wèn)題歸約可以用三元組表示：S0，O，P，其中S0是初始問(wèn)題，即要求解的問(wèn)題；P是本原問(wèn)題集，其中的每一個(gè)問(wèn)題是不用證明的，自然成立的，如公理、知現(xiàn)實(shí)等，或已證明過(guò)的問(wèn)題；O是操作算子集，它是一組變換規(guī)那么，經(jīng)過(guò)一

8、個(gè)操作算子把一個(gè)問(wèn)題化成假設(shè)干個(gè)子問(wèn)題。2022/7/1713問(wèn)題歸約表示方法就是由初始問(wèn)題出發(fā)，運(yùn)用操作算子產(chǎn)生一些子問(wèn)題，對(duì)子問(wèn)題再運(yùn)用操作算子產(chǎn)生子問(wèn)題的子問(wèn)題，這樣不斷進(jìn)展到產(chǎn)生的問(wèn)題均為本原問(wèn)題，那么問(wèn)題得解。 2022/7/1714看如下符號(hào)積分問(wèn)題：初始問(wèn)題f ( x ) dx變換規(guī)那么積分規(guī)那么本原問(wèn)題可直接求原函數(shù)和積分，如sin ( x ) dx，cos ( x ) dx等。一切問(wèn)題歸約的最終目的是產(chǎn)生本原問(wèn)題。2022/7/1715符號(hào)積分問(wèn)題sin3x + x4/(x2 + 1)dx=sin3xdx + (x4/(x2 + 1)dx=-(1 - cos2x)dcosx

9、+ (x2 - 1 + 1/(1 + x2)dx=(-dcosx + cos2xdcosx) + (x2dx - dx + (1/(1 + x2)dx= -cosx + cos3x/3 + x3/3 - x + arctgx2022/7/1716分子構(gòu)造識(shí)別問(wèn)題 如何區(qū)分分子式一樣但分子構(gòu)造不同的有機(jī)化合物成為重要而又困難的問(wèn)題。著名的專家系統(tǒng) DENDRAL能用于有效地識(shí)別分子構(gòu)造，該系統(tǒng)建立了一套重寫規(guī)那么去把分子式重寫為原子數(shù)較少的分子式和原子間結(jié)合關(guān)系的混合構(gòu)造 2022/7/1717問(wèn)題歸約的本質(zhì)： 從目的(要處理的問(wèn)題)出發(fā)逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題

10、歸約為一個(gè)平凡的本原問(wèn)題集合。2022/7/1718運(yùn)用問(wèn)題歸約戰(zhàn)略得到的形狀空間圖，也稱為“與或圖邏輯“與關(guān)系用圓弧將幾條節(jié)點(diǎn)間關(guān)聯(lián)弧銜接在一同表示問(wèn)題分解為子問(wèn)題；子問(wèn)題的形狀結(jié)合起來(lái)構(gòu)成問(wèn)題形狀。子問(wèn)題全部處理才會(huì)導(dǎo)致問(wèn)題的處理；邏輯“或關(guān)系：?jiǎn)栴}可以有多種分解方式；問(wèn)題子問(wèn)題能夠激活多個(gè)形狀變化操作；只需一種分解方式或形狀變化操作能導(dǎo)致最終的解答勝利即可；導(dǎo)致多個(gè)能夠的解答。與或圖2022/7/1719用AND-OR圖把問(wèn)題歸約為子問(wèn)題交換集合。如，假設(shè)問(wèn)題A既可經(jīng)過(guò)問(wèn)題C1與C2，也可經(jīng)過(guò)問(wèn)題C3、C4和C5，或者由單獨(dú)求解問(wèn)題C6來(lái)處理，如以下圖所示。圖中各節(jié)點(diǎn)表示要求解的問(wèn)題或子

11、問(wèn)題。與或圖2022/7/1720梵塔問(wèn)題問(wèn)題描畫(huà)：初始形狀下三個(gè)盤按A、B、C順序堆放在1號(hào)柱子上；目的形狀下三個(gè)盤以同樣次序順序堆放在3號(hào)柱子上；盤子的搬移規(guī)那么：每次只能搬一個(gè)盤子；較大盤不能壓放在較小盤之上；CAB初始形狀(1 1 1)目的形狀(3 3 3)CAB132132與或圖2022/7/1721梵塔問(wèn)題形狀空間圖(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(2,2,1)132CAB(2,2,3)123ABC目的形狀(3 3 3)CAB1322022/7/1722梵塔問(wèn)題形狀空間圖(1,1,1)(3,3,3)(1

12、,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(1,1,1)(3,1,1)(3,2,1)(2,2,1)(3,1,1)(3,2,1)(1,2,3)(1,3,3)(2,2,3)(1,2,3)(1,3,3)(3,3,3)2022/7/1723梵塔問(wèn)題(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(1,1,1)(3,1,1)(3,2,1)(2,2,1)(3,1,1)(3,2,1)(1,2,3)(1,3,3)(2,2,3)(1,2,3)(1,3,3)(3,3,3)123456789子問(wèn)題間有交互作用，問(wèn)題

13、分解留意正確的順序2022/7/1724與或圖搜索與或圖視為對(duì)普通圖(或圖)的擴(kuò)展； 引入K-銜接父子節(jié)點(diǎn)間可以存在“與關(guān)系結(jié)果解圖。解答途徑往往不復(fù)存在，代之以廣義的解途徑解圖。問(wèn)題歸約求解問(wèn)題的過(guò)程表示為與或圖搜索2022/7/1725與或圖搜索1)與或圖搜索的根本概念1、K-銜接從父節(jié)點(diǎn)到K個(gè)子節(jié)點(diǎn)的銜接，子節(jié)點(diǎn)間有“與關(guān)系；以圓弧指示這些子節(jié)點(diǎn)間的“與關(guān)系；一個(gè)父節(jié)點(diǎn)可以有多個(gè)K-銜接K-銜接間或關(guān)系當(dāng)一切的K都等于1時(shí)，與或圖蛻化為普通圖或圖。3個(gè)子節(jié)點(diǎn)2個(gè)子節(jié)點(diǎn)2022/7/1726與或圖搜索1)與或圖搜索的根本概念2、根、葉、終節(jié)點(diǎn)根節(jié)點(diǎn)無(wú)父節(jié)點(diǎn)的節(jié)點(diǎn)用于指示問(wèn)題初始形狀和普通圖

14、一樣葉節(jié)點(diǎn)無(wú)子節(jié)點(diǎn)的節(jié)點(diǎn)終節(jié)點(diǎn)能用于結(jié)合表示目的形狀的節(jié)點(diǎn)終節(jié)點(diǎn)必定是葉節(jié)點(diǎn)，反之不然；目的形狀終結(jié)點(diǎn)的集合。2022/7/1727一些關(guān)于與或圖的術(shù)語(yǔ)HMBCDEFGAN父節(jié)點(diǎn)與節(jié)點(diǎn)弧線或節(jié)點(diǎn)子節(jié)點(diǎn)終節(jié)點(diǎn)2022/7/1728與或圖搜索1)與或圖搜索的根本概念3、解圖的生成解圖純粹是一種“與圖解圖中，節(jié)點(diǎn)或節(jié)點(diǎn)組間不存在“或關(guān)系；一切葉節(jié)點(diǎn)都是終節(jié)點(diǎn)2022/7/1729與或圖搜索1)與或圖搜索的根本概念3、解圖的生成自根節(jié)點(diǎn)開(kāi)場(chǎng)選K-銜接;從該K-銜接指向的每個(gè)子節(jié)點(diǎn)出發(fā)，再選一K-銜接;如此反復(fù)進(jìn)展，直到一切K-銜接都指向終節(jié)點(diǎn)為止.2022/7/17302022/7/1731與或圖搜索

15、1)與或圖搜索的根本概念3、解圖的生成解圖純粹是一種“與圖解圖中，節(jié)點(diǎn)或節(jié)點(diǎn)組間不存在“或關(guān)系；一切葉節(jié)點(diǎn)都是終節(jié)點(diǎn)與或圖中存在“或關(guān)系，搜索到多個(gè)解圖；2022/7/1732與或圖搜索2) 解圖、解圖代價(jià)、能解節(jié)點(diǎn)和不能解節(jié)點(diǎn)的定義 (1)解圖與或圖記為G任一節(jié)點(diǎn)記為n到終節(jié)點(diǎn)集合的解圖記為G是G的子圖。(1)假設(shè)n是終節(jié)點(diǎn)，那么G就由單一節(jié)點(diǎn)n構(gòu)成；(2)假設(shè)n有一K-銜接指向子節(jié)點(diǎn)n1，n2，nk,且每個(gè)子節(jié)點(diǎn)都有到終節(jié)點(diǎn)集合的解圖，那么G由該k-銜接和一切這些相應(yīng)于子節(jié)點(diǎn)的解圖構(gòu)成;(3)否那么不存在n到終節(jié)點(diǎn)集合的解圖。 2022/7/1733與或圖搜索2) 解圖、解圖代價(jià)、能解節(jié)點(diǎn)

16、和不能解節(jié)點(diǎn)的定義 (2)解圖代價(jià) 以C(n)指示節(jié)點(diǎn)n到終節(jié)點(diǎn)集合解圖的代價(jià)，并令K-銜接的代價(jià)就為K, 那么 (1)假設(shè)n是終節(jié)點(diǎn)，那么C(n) = 0；(2)假設(shè)n有一K-銜接指向子節(jié)點(diǎn)n1，n2，nk,且這些子節(jié)點(diǎn)每個(gè)都有到終節(jié)點(diǎn)集合的解圖,那么C(n) = K + C(n1) + C(n2) + + C(nk) 352022/7/1734與或圖搜索2) 解圖、解圖代價(jià)、能解節(jié)點(diǎn)和不能解節(jié)點(diǎn)的定義 (3)能解節(jié)點(diǎn) (1) 終節(jié)點(diǎn)是能解節(jié)點(diǎn)；(2) 假設(shè)節(jié)點(diǎn)n有一K-銜接指向子節(jié)點(diǎn)n1，n2，nk,且這些子節(jié)點(diǎn)都是能解節(jié)點(diǎn)，那么n是能解節(jié)點(diǎn)； 能解節(jié)點(diǎn)能解節(jié)點(diǎn)能解節(jié)點(diǎn)能解節(jié)點(diǎn)2022/7

17、/1735與或圖搜索2) 解圖、解圖代價(jià)、能解節(jié)點(diǎn)和不能解節(jié)點(diǎn)的定義 (4)不能解節(jié)點(diǎn)(1)非終節(jié)點(diǎn)的葉節(jié)點(diǎn)是不能解節(jié)點(diǎn)；(2)假設(shè)節(jié)點(diǎn)n的每一個(gè)K-銜接都至少指向一個(gè)不能解節(jié)點(diǎn)，那么n是不能解節(jié)點(diǎn)。 能解節(jié)點(diǎn)不能解節(jié)點(diǎn)能解節(jié)點(diǎn)不能解節(jié)點(diǎn)不能解節(jié)點(diǎn)2022/7/1736與或圖的啟發(fā)式搜索與或圖中搜索的是解圖，不是解答途徑；評(píng)價(jià)函數(shù)f(n)=h(n)h(n)是對(duì)n到終節(jié)點(diǎn)集合解圖最小解圖代價(jià)的估計(jì)；與或圖中存在“或關(guān)系，會(huì)有多個(gè)候選的部分解圖；選擇部分解圖中能夠代價(jià)最小的用于下一步搜索。1)部分解圖代價(jià)f(n0) n0初始形狀節(jié)點(diǎn)遞歸地計(jì)算出f(n0),比直接用h(n0)估算更為準(zhǔn)確。父節(jié)點(diǎn)n的

18、K-銜接指向的子節(jié)點(diǎn)：n1，n2，nkf(n) = K + h(n1) + h(n2) + + h(nk)，替代h(n)2022/7/1737與或圖的啟發(fā)式搜索2) AO*算法符號(hào)闡明：G-搜索圖；G-被選中的待擴(kuò)展部分解圖；LGS-待擴(kuò)展部分解圖集；n0-根節(jié)點(diǎn)，即初始形狀節(jié)點(diǎn)；n-被選中的待擴(kuò)展節(jié)點(diǎn)；fi(n0)-第i個(gè)待擴(kuò)展部分解圖的能夠代價(jià)。2022/7/1738與或圖的啟發(fā)式搜索2) AO*算法算法劃分二個(gè)階段：1、初始化 建立只包含初始形狀節(jié)點(diǎn)n0的搜索圖G:=n0；待擴(kuò)展部分解圖集LGS:=；2、搜索循環(huán)選擇和擴(kuò)展LGS中的部分解圖；精化新部分解圖代價(jià)的估計(jì)；傳送節(jié)點(diǎn)的能解性。2

19、022/7/1739與或圖的啟發(fā)式搜索2、搜索循環(huán)選擇和擴(kuò)展LGS中的部分解圖；選擇LGS中fi(n0)最小的待擴(kuò)展解圖G；隨機(jī)選擇G中一個(gè)非終節(jié)點(diǎn)的葉節(jié)點(diǎn)作為n；擴(kuò)展n建立K-銜接，子節(jié)點(diǎn)ni并參與G；計(jì)算子節(jié)點(diǎn)ni的f(ni)=h(ni)假設(shè)n存在j個(gè)K-銜接LGS中刪除G將j個(gè)新的部分解圖參與LGS;2022/7/1740與或圖的啟發(fā)式搜索2、搜索循環(huán)選擇和擴(kuò)展LGS中的部分解圖；精化新部分解圖代價(jià)的估計(jì)用公式f(n) = K + h(n1) + h(n2) + + h(nk)取代原先的f(n);遞歸地作用到初始節(jié)點(diǎn)n0；傳送新部分解圖中節(jié)點(diǎn)的能解性標(biāo)志作為終節(jié)點(diǎn)的子節(jié)點(diǎn)為能解節(jié)點(diǎn)；遞歸

20、地傳送節(jié)點(diǎn)的能解性到初始節(jié)點(diǎn)n0 。f(n)=h(n)2022/7/17412022/7/1742與或圖的啟發(fā)式搜索2) AO*算法AO*算法運(yùn)用例搜索過(guò)程中，啟發(fā)式函數(shù)h(ni)的 估算如下：h(n0)=3h(n1)=2h(n2)=1h(n3)=1h(n4)=4h(n5)=2h(n6)=2h(n7)=1h(n8)=1h(n13)=3012354678910111213141516171819202022/7/1743初始化候選的待擴(kuò)展部分解圖集LGS:0302022/7/1744012354循環(huán)1候選的待擴(kuò)展部分解圖集LGS:32114202022/7/1745012354循環(huán)1候選的待擴(kuò)展

21、部分解圖集LGS:321142031201235432114202022/7/1746012354循環(huán)1候選的待擴(kuò)展部分解圖集LGS:10211420512f(n) = K + h(n1) + h(n2) + + h(nk)取代原先的f(n);f1(n0) = 2 + h(n1) + h(n2)=5f2(n0) = 3 + h(n3) + h(n4)+h(n5)=102022/7/1747012354循環(huán)2候選的待擴(kuò)展部分解圖集LGS:102114205678211122022/7/1748012354循環(huán)2候選的待擴(kuò)展部分解圖集LGS:1021142057811012215623422022

22、/7/1749012354循環(huán)2候選的待擴(kuò)展部分解圖集LGS:10411420778110123166234225252022/7/1750012354候選的待擴(kuò)展部分解圖集LGS:104114207781101231662342131430循環(huán)32022/7/1751012354候選的待擴(kuò)展部分解圖集LGS:104114207781101261965342131430循環(huán)33622022/7/1752012354循環(huán)4候選的待擴(kuò)展部分解圖集LGS:1041142077811012619653421314301402022/7/1753012354循環(huán)5候選的待擴(kuò)展部分解圖集LGS:10411

23、42077811012619653421314301401502022/7/1754012354循環(huán)5候選的待擴(kuò)展部分解圖集LGS:1051142087812012619653421314301401504712022/7/1755012354循環(huán)6候選的待擴(kuò)展部分解圖集LGS:105114208781201261965342131430140150902022/7/1756012354搜索勝利！候選的待擴(kuò)展部分解圖集LGS:105114208781201261965342131430140150902022/7/1757與或圖的啟發(fā)式搜索4算法運(yùn)用的假設(shè)干問(wèn)題1、從部分解圖G中選擇加以擴(kuò)展的

24、節(jié)點(diǎn)n與或圖搜索的是解圖而非解途徑；選擇f(n) = h(n)的值最小的節(jié)點(diǎn)n加以擴(kuò)展并不一定會(huì)加速搜索過(guò)程；應(yīng)選擇導(dǎo)致解圖代價(jià)發(fā)生較大變化的節(jié)點(diǎn)n優(yōu)先加以擴(kuò)展；使搜索的留意力快速地聚焦到實(shí)踐代價(jià)較小的候選解圖上；簡(jiǎn)單情況下，可隨機(jī)選擇加以擴(kuò)展的節(jié)點(diǎn)。2022/7/1758與或圖的啟發(fā)式搜索4算法運(yùn)用的假設(shè)干問(wèn)題2、算法AO*與A*的比較解圖解答途徑，估計(jì)代價(jià)最小的部分解圖加以優(yōu)先擴(kuò)展OPEN表中f(n)最小的節(jié)點(diǎn)；只思索評(píng)價(jià)函數(shù)f(n)=h(n)同時(shí)計(jì)算分量g(n)和h(n)，運(yùn)用LGS存放待擴(kuò)展部分解圖，并根據(jù)fi(n0)值排序運(yùn)用OPEN表和CLOSE表分別存放待擴(kuò)展節(jié)點(diǎn)和已擴(kuò)展節(jié)點(diǎn)，并

25、根據(jù)f(n)值排序OPEN表。2022/7/1759與或圖的啟發(fā)式搜索4算法運(yùn)用的假設(shè)干問(wèn)題3、解圖代價(jià)的反復(fù)計(jì)算某些子節(jié)點(diǎn)能夠會(huì)有多個(gè)父節(jié)點(diǎn)；這種子節(jié)點(diǎn)到終節(jié)點(diǎn)集合的解圖代價(jià)在計(jì)算自根節(jié)點(diǎn)n0出發(fā)的解圖時(shí)被反復(fù)累計(jì)。1781781415125178142216241182022/7/1760博弈 博弈提供了一個(gè)可構(gòu)造的義務(wù)領(lǐng)域，在這個(gè)領(lǐng)域中，具有明確的勝利和失敗；博弈問(wèn)題對(duì)人工智能研討提出了嚴(yán)峻的挑戰(zhàn)。例如，如何表示博弈問(wèn)題的形狀、博弈過(guò)程和博弈知識(shí)等。 這里講的博弈是二人博弈，二人零和、全信息、非偶爾博弈，博弈雙方的利益是完全對(duì)立的。 2022/7/1761所謂“二人零和，是指在博弈中只需

26、“敵、我二方。且雙方的利益完全對(duì)立，其博得函數(shù)之和為零，即 1+2=0 式中，1為我方博得(利益)；2為敵方博得(利益)。 即：博弈的雙方有三種結(jié)局： (1)我勝：10；敵負(fù)：2= -10。 (2)我負(fù)：1= -20。 (3)平局：1=0，2=0。 博弈問(wèn)題對(duì)人工智能研討提出了嚴(yán)峻的挑戰(zhàn)。例如，如何表示博弈問(wèn)題的形狀、博弈過(guò)程和博弈知識(shí)等。 2022/7/1762所謂“全信息，是指博弈雙方都了解當(dāng)前的格局及過(guò)去的歷史。 所謂“非偶爾，是指博弈雙方都可根據(jù)得失大小進(jìn)展分析，選取我方博得最大，敵方博得最小的對(duì)策，而不是偶爾的隨機(jī)對(duì)策。 2022/7/17631對(duì)壘的雙方MAX和MIN輪番采取行動(dòng)，

27、博弈的結(jié)果只能有3種情況：MAX勝、MIN?。籑AX敗，MIN勝；和局。2在對(duì)壘過(guò)程中，任何一方都了解當(dāng)前的格局和過(guò)去的歷史。3任何一方在采取行動(dòng)前都要根據(jù)當(dāng)前的實(shí)踐情況，進(jìn)展得失分析，選擇對(duì)本人最為有利而對(duì)對(duì)方最不利的對(duì)策，在不存在“碰運(yùn)氣的偶爾要素，即雙方都很明智地決議本人的行動(dòng)。這類博弈如一字棋、象棋、圍棋等。博弈的特點(diǎn) 2022/7/1764另外一種博弈是機(jī)遇性博弈，是指不可預(yù)測(cè)性的博弈，如擲硬幣游戲等。 2022/7/1765例：假設(shè)有七枚錢幣，任一選手只能將已分好的一堆錢幣分成兩堆個(gè)數(shù)不等的錢幣，兩位選手輪番進(jìn)展，直到每一堆都只需一個(gè)或兩個(gè)錢幣，不能再分為止，哪個(gè)選手遇到不能再分的

28、情況，那么為輸。 2022/7/1766用數(shù)字序列加上一個(gè)闡明表示一個(gè)形狀，其中數(shù)字表示不同堆中錢幣的個(gè)數(shù)，闡明表示下一步由誰(shuí)來(lái)分，如7，MIN表示只需一個(gè)由七枚錢幣組成的堆，由MIN走，MIN有3種可供選擇的分法，即6，1，MAX，5，2，MAX，4，3，MAX，其中MAX表示另一選手，不論哪一種方法，MAX在它的根底上再作符合要求的劃分。2022/7/1767以下圖已將雙方能夠的方案完全表示出來(lái)了，無(wú)論MIN開(kāi)場(chǎng)時(shí)怎樣走法，MAX總可以獲勝，取勝的戰(zhàn)略用雙線箭頭表示。2022/7/1768實(shí)踐的情況沒(méi)有這么簡(jiǎn)單，任何一種棋都不能夠?qū)⒁磺星闆r列盡，因此，只能模擬人“向前看幾步，然后做出決策，

29、決議本人走哪一步最有利。只能給出幾層走法，然后按照一定的估算方法，決議走哪一步棋。在雙人完備信息博弈過(guò)程中，雙方都希望本人可以獲勝。因此當(dāng)一方走步時(shí)，都是選擇對(duì)本人最有利，而對(duì)對(duì)方最不利的走法。2022/7/1769假設(shè)博弈雙方為MAX和MIN。在博弈的每一步，可供他們選擇的方案都有很多種。從MAX的觀念看，可供本人選擇的方案之間是“或的關(guān)系，緣由是自動(dòng)權(quán)在本人手里，選擇哪個(gè)方案完全由本人決議，可供本人選擇的方案之間是“或的關(guān)系，而對(duì)那些可供MIN選擇的方案之間是“與的關(guān)系，這是由于自動(dòng)權(quán)在MIN手中，任何一個(gè)方案都能夠被MIN選中，MAX必需防止那種對(duì)本人最不利的情況出現(xiàn)。 2022/7/1

30、770以下圖是把雙人博弈過(guò)程用圖的方式表示出來(lái)，這樣就可以得到一棵AND-OR樹(shù)，這種AND-OR樹(shù)稱為博弈樹(shù)。在博弈樹(shù)中，那些下一步該MAX走的節(jié)點(diǎn)稱為MAX節(jié)點(diǎn)，而下一步該MIN走的節(jié)點(diǎn)稱為MIN節(jié)點(diǎn)。2022/7/1771以下圖 所示是向前看兩步，共四層的博弈樹(shù)，用表示MAX，用表示MIN，端節(jié)點(diǎn)上的數(shù)字表示它對(duì)應(yīng)的估價(jià)函數(shù)的值。在MIN處用圓弧銜接，用0表示其子節(jié)點(diǎn)取估值最小的格局。 圖中節(jié)點(diǎn)處的數(shù)字，在端節(jié)點(diǎn)是估價(jià)函數(shù)的值，稱它為靜態(tài)值，在MIN處取最小值，在MAX處取最大值，最后MAX選擇箭頭方向的走步。 2022/7/1772博弈樹(shù)特點(diǎn)：(1)博弈的初始形狀是初始節(jié)點(diǎn)；(2)博弈

31、樹(shù)的“與節(jié)點(diǎn)和“或節(jié)點(diǎn)是逐層交替出現(xiàn)的；(3)整個(gè)博弈過(guò)程一直站在某一方的立場(chǎng)上，所以能使本人一方獲勝的結(jié)局都是本原問(wèn)題，相應(yīng)的節(jié)點(diǎn)也是可解節(jié)點(diǎn)，一切使對(duì)方獲勝的節(jié)點(diǎn)都是不可解節(jié)點(diǎn)。 2022/7/1773在人工智能中可以采用搜索方法來(lái)求解博弈問(wèn)題，下面就來(lái)討論博弈中兩中最根本的搜索方法。 2022/7/1774極大極小過(guò)程 極大極小過(guò)程是思索雙方對(duì)弈假設(shè)干步之后，從能夠的走法中選一步相對(duì)好的走法來(lái)走，即在有限的搜索深度范圍內(nèi)進(jìn)展求解。需求定義一個(gè)靜態(tài)估價(jià)函數(shù)f,以便對(duì)棋局的態(tài)勢(shì)做出評(píng)價(jià)。 2022/7/1775這個(gè)函數(shù)可以根據(jù)棋局的態(tài)勢(shì)特征進(jìn)展定義。假定對(duì)弈雙方分別為MAX和MIN，規(guī)定：

32、有利于MAX方的態(tài)勢(shì)：f(p)取正值 有利于MIN方的態(tài)勢(shì)：f(p)取負(fù)值 態(tài)勢(shì)平衡的時(shí)候：f(p)取零其中p代表棋局。2022/7/1776MINMAX根本思想：(1)當(dāng)輪到MIN走步的節(jié)點(diǎn)時(shí)取與時(shí)，MAX應(yīng)思索最壞的情況即f(p)取極小值。(2)當(dāng)輪到MAX走步的節(jié)點(diǎn)時(shí)取或時(shí)，MAX應(yīng)思索最好的情況即f(p)取極大值。(3)評(píng)價(jià)往回倒推時(shí)，相應(yīng)于兩位棋手的對(duì)抗戰(zhàn)略，交替運(yùn)用1和2兩種方法傳送倒推值。所以這種方法稱為極大極小過(guò)程。 2022/7/1777用一字棋闡明極大極小過(guò)程，設(shè)只進(jìn)展兩層，即每方只走一步。一字棋游戲規(guī)那么如下：設(shè)有一個(gè)三行三列的棋盤，如下圖，兩個(gè)棋手輪番走步，每個(gè)棋手走步

33、時(shí)往空格上擺一個(gè)本人的棋子，誰(shuí)先使本人的棋子成三子一線為贏。設(shè)MAX方的棋子用標(biāo)志，MIN方的棋子用標(biāo)志，并規(guī)定MAX方先走步。2022/7/1778 為了不致于生成太大的博弈樹(shù)，假設(shè)每次僅擴(kuò)展兩層。估價(jià)函數(shù)定義如下： 設(shè)棋局為P，估價(jià)函數(shù)為e(P)。(1)假設(shè)格局p對(duì)任何一方都不是獲勝的，那么 e(p) = (一切空格都放上 MAX 的棋子之后三子成一線的總數(shù)) 一切空格都放上 MIN 的棋子后三子成一線的總數(shù)(2)假設(shè)p是MAX獲勝，那么 e(p) = +3 假設(shè)p是MIN獲勝，那么 e(p) = - 2022/7/1779假設(shè)p為以下圖所示，且 e(P)=e(+P)-e(-P)=5-4=

34、12022/7/1780假設(shè)由MAX先走棋，且我們站在MAX立場(chǎng)上。以下圖給出了MAX的第一著走棋生成的博弈樹(shù)。圖中節(jié)點(diǎn)旁的數(shù)字分別表示相應(yīng)節(jié)點(diǎn)的靜態(tài)估值或倒推值。由圖可以看出，對(duì)于MAX來(lái)說(shuō)最好的一著棋是S3，由于S3比S1和S2有較大的估值。2022/7/1781以下圖 所示是向前看兩步，共四層的博弈樹(shù)，用表示MAX，用表示MIN，端節(jié)點(diǎn)上的數(shù)字表示它對(duì)應(yīng)的估價(jià)函數(shù)的值。在MIN處用圓弧銜接，用0表示其子節(jié)點(diǎn)取估值最小的格局。 圖中節(jié)點(diǎn)處的數(shù)字，在端節(jié)點(diǎn)是估價(jià)函數(shù)的值，稱它為靜態(tài)值，在MIN處取最小值，在MAX處取最大值，最后MAX選擇箭頭方向的走步。 2022/7/1782-過(guò)程 上面討

35、論的極大極小過(guò)程先生成一棵博弈搜索樹(shù)，而且會(huì)生成規(guī)定深度內(nèi)的一切節(jié)點(diǎn)，然后再進(jìn)展估值的倒推計(jì)算，這樣使得生成博弈樹(shù)和估計(jì)值的倒推計(jì)算兩個(gè)過(guò)程完全分別，因此搜索效率較低。假設(shè)能邊生成博弈樹(shù)，邊進(jìn)展估值的計(jì)算，那么能夠不用生成規(guī)定深度內(nèi)的一切節(jié)點(diǎn)，以減少搜索的次數(shù)，這就是下面要討論的-過(guò)程。 2022/7/1783思索：假設(shè)邊生成博弈樹(shù)，邊進(jìn)展估值的計(jì)算會(huì)帶來(lái)什么益處。2022/7/1784-過(guò)程就是把生成后繼和倒推值估計(jì)結(jié)合起來(lái)，及時(shí)剪掉一些無(wú)用分支，以此來(lái)提高算法的效率。下面依然用一字棋進(jìn)展闡明?，F(xiàn)將原圖左邊所示的一部分重畫(huà)在中。2022/7/1785前面的過(guò)程實(shí)踐上類似于寬度優(yōu)先搜索，將每層

36、格局均生成，如今用深度優(yōu)先搜索來(lái)處置。比如在節(jié)點(diǎn)A處，假設(shè)已生成5個(gè)子節(jié)點(diǎn)，并且A處的倒推值等于-1，我們將此下界叫做MAX節(jié)點(diǎn)的值，即-1。 2022/7/1786如今輪到節(jié)點(diǎn)B，產(chǎn)生它的第一后繼節(jié)點(diǎn)C，C的靜態(tài)值為-1，可知B處的倒推值-1，此為上界MIN節(jié)點(diǎn)的值，即B處-1，這樣B節(jié)點(diǎn)最終的倒推值能夠小于-1，但絕不能夠大于-1，因此，B節(jié)點(diǎn)的其他后繼節(jié)點(diǎn)的靜態(tài)值不用計(jì)算，自然不用再生成，反正B決不會(huì)比A好，所以經(jīng)過(guò)倒推值的比較，就可以減少搜索的任務(wù)量2022/7/1787上圖表示了值小于等于父節(jié)點(diǎn)的值時(shí)的情況，實(shí)踐上當(dāng)某個(gè)MIN節(jié)點(diǎn)的值不大于它的先輩的MAX節(jié)點(diǎn)不一定是父節(jié)點(diǎn)的值時(shí)，那

37、么MIN節(jié)點(diǎn)就可以終止向下搜索。 同樣，當(dāng)某個(gè)節(jié)點(diǎn)的值大于等于它的先輩MIN節(jié)點(diǎn)的值時(shí)，那么該MAX節(jié)點(diǎn)就可以終止向下搜索。2022/7/1788 再看一個(gè)例子，如以下圖所示。其中最下面一層端節(jié)點(diǎn)旁邊的數(shù)字是假設(shè)的估值。 2022/7/1789經(jīng)過(guò)上面的討論可以看出，-過(guò)程首先使搜索樹(shù)的某一部分到達(dá)最大深度，這時(shí)計(jì)算出某些MAX節(jié)點(diǎn)的值，或者是某些MIN節(jié)點(diǎn)的值。隨著搜索的繼續(xù)，不斷修正個(gè)別節(jié)點(diǎn)的或值。對(duì)任一節(jié)點(diǎn)，當(dāng)其某一后繼節(jié)點(diǎn)的最終值給定時(shí)，就可以確定該節(jié)點(diǎn)的或值。2022/7/1790當(dāng)該節(jié)點(diǎn)的其他后繼節(jié)點(diǎn)的最終值給定時(shí)，就可以對(duì)該節(jié)點(diǎn)的或值進(jìn)展修正。留意、值修正有如下規(guī)律：(1)MAX

38、節(jié)點(diǎn)的值永不下降；(2)MIN節(jié)點(diǎn)的值永不添加。2022/7/1791 因此可以利用上述規(guī)律進(jìn)展剪枝，普通可以停頓對(duì)某個(gè)節(jié)點(diǎn)搜索，即剪枝的規(guī)那么表述如下： (1)假設(shè)任何MIN節(jié)點(diǎn)的值小于或等于任何它的先輩MAX節(jié)點(diǎn)的值，那么可停頓該MIN節(jié)點(diǎn)以下的搜索，然后這個(gè)MIN節(jié)點(diǎn)的最終倒推值即為它已得到的值。 該值與真正的極大極小值的搜索結(jié)果的倒推值能夠不一樣，但是對(duì)開(kāi)場(chǎng)節(jié)點(diǎn)而言，倒推值是一樣的，運(yùn)用它選擇的走步也是一樣的。(2)假設(shè)任何MAX節(jié)點(diǎn)的值大于或等于它的MIN先輩節(jié)點(diǎn)的值，那么可以停頓該MAX節(jié)點(diǎn)以下的搜索，然后這個(gè)MAX節(jié)點(diǎn)處的倒推值即為它已得到的值。2022/7/1792當(dāng)滿足規(guī)那么1而減少了搜索時(shí)，進(jìn)展了剪枝；而當(dāng)滿足規(guī)那么2而減少了搜索時(shí)，進(jìn)展了剪枝。保管和值，并且一旦能夠就進(jìn)展剪枝的整個(gè)過(guò)程通常稱為-過(guò)程，當(dāng)初始節(jié)點(diǎn)的全體后繼節(jié)點(diǎn)的最終倒推值全部給出時(shí)，上述過(guò)程便終了。在搜索深度一樣的條件下，采用這個(gè)過(guò)程所獲得的走步總跟簡(jiǎn)單的極大極小過(guò)程的結(jié)果是一樣的，區(qū)別只在于-過(guò)程通常只用少得多的搜索便可以找到一個(gè)理想的走步。 2022/7/1793約束滿足搜索 約束滿足問(wèn)題CSP就是為一組變量尋覓滿足約束的賦值。如，N-皇后問(wèn)題就是一個(gè)約束滿足問(wèn)題。這里的問(wèn)題就是為