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

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

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

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

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

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

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

8、個操作算子把一個問題化成假設干個子問題。2022/7/1713問題歸約表示方法就是由初始問題出發，運用操作算子產生一些子問題，對子問題再運用操作算子產生子問題的子問題，這樣不斷進展到產生的問題均為本原問題，那么問題得解。 2022/7/1714看如下符號積分問題：初始問題f ( x ) dx變換規那么積分規那么本原問題可直接求原函數和積分，如sin ( x ) dx，cos ( x ) dx等。一切問題歸約的最終目的是產生本原問題。2022/7/1715符號積分問題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分子構造識別問題 如何區分分子式一樣但分子構造不同的有機化合物成為重要而又困難的問題。著名的專家系統 DENDRAL能用于有效地識別分子構造，該系統建立了一套重寫規那么去把分子式重寫為原子數較少的分子式和原子間結合關系的混合構造 2022/7/1717問題歸約的本質： 從目的(要處理的問題)出發逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題

10、歸約為一個平凡的本原問題集合。2022/7/1718運用問題歸約戰略得到的形狀空間圖，也稱為“與或圖邏輯“與關系用圓弧將幾條節點間關聯弧銜接在一同表示問題分解為子問題；子問題的形狀結合起來構成問題形狀。子問題全部處理才會導致問題的處理；邏輯“或關系：問題可以有多種分解方式；問題子問題能夠激活多個形狀變化操作；只需一種分解方式或形狀變化操作能導致最終的解答勝利即可；導致多個能夠的解答。與或圖2022/7/1719用AND-OR圖把問題歸約為子問題交換集合。如，假設問題A既可經過問題C1與C2，也可經過問題C3、C4和C5，或者由單獨求解問題C6來處理，如以下圖所示。圖中各節點表示要求解的問題或子

11、問題。與或圖2022/7/1720梵塔問題問題描畫：初始形狀下三個盤按A、B、C順序堆放在1號柱子上；目的形狀下三個盤以同樣次序順序堆放在3號柱子上；盤子的搬移規那么：每次只能搬一個盤子；較大盤不能壓放在較小盤之上；CAB初始形狀(1 1 1)目的形狀(3 3 3)CAB132132與或圖2022/7/1721梵塔問題形狀空間圖(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梵塔問題形狀空間圖(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梵塔問題(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子問題間有交互作用，問題

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

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

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

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

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

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

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

20、地傳送節點的能解性到初始節點n0 。f(n)=h(n)2022/7/17412022/7/1742與或圖的啟發式搜索2) AO*算法AO*算法運用例搜索過程中，啟發式函數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初始化候選的待擴展部分解圖集LGS:0302022/7/1744012354循環1候選的待擴展部分解圖集LGS:32114202022/7/1745012354循環1候選的待擴展

21、部分解圖集LGS:321142031201235432114202022/7/1746012354循環1候選的待擴展部分解圖集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循環2候選的待擴展部分解圖集LGS:102114205678211122022/7/1748012354循環2候選的待擴展部分解圖集LGS:1021142057811012215623422022

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

23、42077811012619653421314301401502022/7/1754012354循環5候選的待擴展部分解圖集LGS:1051142087812012619653421314301401504712022/7/1755012354循環6候選的待擴展部分解圖集LGS:105114208781201261965342131430140150902022/7/1756012354搜索勝利！候選的待擴展部分解圖集LGS:105114208781201261965342131430140150902022/7/1757與或圖的啟發式搜索4算法運用的假設干問題1、從部分解圖G中選擇加以擴展的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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