AI03人工智能-搜索算法

人工智能導(dǎo)論

Introduction

toArtificialIntelligence

第三章史忠植

中國(guó)科學(xué)院計(jì)算技術(shù)研究所/搜索算法SearchAlgorithms2023/10/20史忠植人工智能導(dǎo)論：搜索算法12023/10/20史忠植人工智能導(dǎo)論：搜索算法2內(nèi)容提要3.1概述3.2

盲目搜索

3.3啟發(fā)式搜索

3.4博弈搜索3.5小結(jié)

問(wèn)題求解AI中每個(gè)研究領(lǐng)域都有其各自的特點(diǎn)和規(guī)律,但就求解問(wèn)題的過(guò)程看,都可抽象為一個(gè)問(wèn)題求解過(guò)程。問(wèn)題求解過(guò)程實(shí)際上是一個(gè)搜索,廣義地說(shuō),它包含了全部計(jì)算機(jī)科學(xué)。任何問(wèn)題求解技術(shù)都包括兩個(gè)重要的方面:表示和搜索表示是基本的,搜索必須要在表示的基礎(chǔ)上進(jìn)行。表示關(guān)系到搜索的效率。本章討論的表示主要包括:狀態(tài)空間表示問(wèn)題空間表示2023/10/20史忠植人工智能導(dǎo)論：搜索算法3搜索1974年，Nilsson歸納出的AI研究的基本問(wèn)題知識(shí)的模型化和表示常識(shí)性推理、演繹和問(wèn)題解決啟發(fā)式搜索人工智能系統(tǒng)和語(yǔ)言搜索是人工智能中的一個(gè)基本問(wèn)題,是推理不可分割的一部分,直接關(guān)系到智能系統(tǒng)的性能和運(yùn)行效率AI為什么要研究search?問(wèn)題沒(méi)有直接的解法;需要探索地求解;2023/10/20史忠植人工智能導(dǎo)論：搜索算法4什么是搜索根據(jù)問(wèn)題的實(shí)際情況不斷尋找可利用的知識(shí),構(gòu)造出一條代價(jià)較少的推理路線,使問(wèn)題得到圓滿解決的過(guò)程稱為搜索包括兩個(gè)方面：

找到從初始事實(shí)到問(wèn)題最終答案的一條推理路徑

找到的這條路徑在時(shí)間和空間上復(fù)雜度最小2023/10/20史忠植人工智能導(dǎo)論：搜索算法5搜索策略盲目搜索:也稱為無(wú)信息搜索，即只按預(yù)定的控制策略進(jìn)行搜索,在搜索過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略啟發(fā)式搜索:在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息,用于指導(dǎo)搜索朝著最有希望的方向進(jìn)行,加速問(wèn)題的求解過(guò)程并找到最優(yōu)解2023/10/20史忠植人工智能導(dǎo)論：搜索算法6搜索策略一般搜索策略可以通過(guò)下面4個(gè)準(zhǔn)則來(lái)評(píng)價(jià)：（1）完備性：如果存在一個(gè)解答，該策略是否保證能夠找到？（2）時(shí)間復(fù)雜性：需要多長(zhǎng)時(shí)間可以找到解答？（3）空間復(fù)雜性：執(zhí)行搜索需要多大存儲(chǔ)空間？（4）最優(yōu)性：如果存在不同的幾個(gè)解答，該策略可以發(fā)現(xiàn)是否最高質(zhì)量的解答？2023/10/20史忠植人工智能導(dǎo)論：搜索算法72023/10/20史忠植人工智能導(dǎo)論：搜索算法8內(nèi)容提要3.1概述3.2

盲目搜索

3.3啟發(fā)式搜索

3.4博弈搜索3.5小結(jié)

盲目搜索盲目搜索一般是按預(yù)定的搜索策略進(jìn)行搜索。由于這種搜索總是按預(yù)定的路線進(jìn)行，沒(méi)有考慮到問(wèn)題本身的特性，所以這種搜索具有很大的盲目性，效率不高，不便于復(fù)雜問(wèn)題的求解。深度優(yōu)先搜索寬度優(yōu)先搜索迭代加深搜索2023/10/20史忠植人工智能導(dǎo)論：搜索算法910深度優(yōu)先搜索(Dephth-first)深度優(yōu)先搜索生成節(jié)點(diǎn)并與目標(biāo)節(jié)點(diǎn)進(jìn)行比較是沿著樹的最大深度方向進(jìn)行的，只有當(dāng)上次訪問(wèn)的節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)，而且沒(méi)有其他節(jié)點(diǎn)可以生成的時(shí)候，才轉(zhuǎn)到上次訪問(wèn)節(jié)點(diǎn)的父節(jié)點(diǎn)。轉(zhuǎn)移到父節(jié)點(diǎn)后，該算法會(huì)搜索父節(jié)點(diǎn)的其它的子節(jié)點(diǎn)。防止搜索過(guò)程沿著無(wú)益的路徑擴(kuò)展下去，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度——深度界限。2023/10/20史忠植人工智能導(dǎo)論：搜索算法11深度優(yōu)先搜索示意圖SLOMFPQNFFF2023/10/20史忠植人工智能導(dǎo)論：搜索算法12開始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？擴(kuò)展n，把n的后繼節(jié)點(diǎn)放入OPEN表的前端，提供返回節(jié)點(diǎn)n的指針失敗成功是否是否節(jié)點(diǎn)n的深度等于最大深度？否深度優(yōu)先算法框圖2023/10/20史忠植人工智能導(dǎo)論：搜索算法13有界深度(4)優(yōu)先的八數(shù)碼問(wèn)題深度優(yōu)先搜索樹1238456712384567（目標(biāo)狀態(tài)）（初始狀態(tài)）深度優(yōu)先搜索樹2023/10/20史忠植人工智能導(dǎo)論：搜索算法14八數(shù)碼有界深度優(yōu)先搜索樹2023/10/20史忠植人工智能導(dǎo)論：搜索算法(1)把初始節(jié)點(diǎn)S0放入OPEN表(2)如果OPEN表為空,則問(wèn)題無(wú)解,退出(3)把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出,放入CLOSED表(4)考查節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn).若是,則求得了問(wèn)題的解,退出(5)若節(jié)點(diǎn)n不可擴(kuò)展,則轉(zhuǎn)第(2)步(6)擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)放入OPEN表的首部,并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針,轉(zhuǎn)第(2)步深度優(yōu)先搜索過(guò)程2023/10/20史忠植人工智能導(dǎo)論：搜索算法1516SLOMFPQNFFF寬度優(yōu)先搜索示意圖2023/10/20史忠植人工智能導(dǎo)論：搜索算法17（1）把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答)。（2）如果OPEN是個(gè)空表，則沒(méi)有解，失敗退出；否則繼續(xù)。（3）把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。（4）擴(kuò)展節(jié)點(diǎn)n。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第(2)步。（5）把n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。（6）如果n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出；否則轉(zhuǎn)向第(2)步。寬度優(yōu)先搜索算法2023/10/20史忠植人工智能導(dǎo)論：搜索算法18開始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？擴(kuò)展n，把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針失敗成功是否是否寬度優(yōu)先算法框圖2023/10/20史忠植人工智能導(dǎo)論：搜索算法19八數(shù)碼難題（8-puzzleproblem）1238456712384567（目標(biāo)狀態(tài)）（初始狀態(tài)）規(guī)定：將牌移入空格的順序?yàn)椋簭目崭褡筮呴_始順時(shí)針旋轉(zhuǎn)。不許斜向移動(dòng)，也不返回先輩節(jié)點(diǎn)。從圖可見(jiàn)，要擴(kuò)展26個(gè)節(jié)點(diǎn)，共生成46個(gè)節(jié)點(diǎn)之后才求得解（目標(biāo)節(jié)點(diǎn)）。寬度優(yōu)先算法例子2023/10/20史忠植人工智能導(dǎo)論：搜索算法20八數(shù)碼寬度優(yōu)先搜索樹2023/10/20史忠植人工智能導(dǎo)論：搜索算法迭代加深搜索對(duì)于有界深度搜索策略，有下面幾點(diǎn)需要說(shuō)明：1）在有界深度搜索算法中，深度限制dm是一個(gè)很重要的參數(shù)。2）深度限制dm不能太大。3）有界深度搜索的主要問(wèn)題是深度限制值dm的選取。問(wèn)題：但是對(duì)很多問(wèn)題，我們并不知道該值到底為多少，直到該問(wèn)題求解完成了，才可以確定出深度限制dm。2023/10/20史忠植人工智能導(dǎo)論：搜索算法21迭代加深搜索改進(jìn)方法---迭代加深搜索算法先任意給定一個(gè)較小的數(shù)作為dm，然后按有界深度算法搜索，若在此深度限制內(nèi)找到了解，則算法結(jié)束；如在此限度內(nèi)沒(méi)有找到問(wèn)題的解，則增大深度限制dm，繼續(xù)搜索。迭代加深搜索是一種回避選擇最優(yōu)深度限制問(wèn)題的策略，它是試圖嘗試所有可能的深度限制：首先深度為0，然后深度為1，然后為2，等等，一直進(jìn)行下去。問(wèn)題迭代加深搜索看起來(lái)會(huì)很浪費(fèi)，因?yàn)楹芏喙?jié)點(diǎn)都要擴(kuò)展多次。2023/10/20史忠植人工智能導(dǎo)論：搜索算法222023/10/20史忠植人工智能導(dǎo)論：搜索算法23內(nèi)容提要3.1概述3.2

盲目搜索

3.3啟發(fā)式搜索

3.4博弈搜索3.5小結(jié)

啟發(fā)式搜索前面討論的方法都是盲目的搜索方法,即都沒(méi)有利用問(wèn)題本身的特性信息,在決定要被擴(kuò)展的節(jié)點(diǎn)時(shí),都沒(méi)有考慮該節(jié)點(diǎn)在解的路徑上的可能性有多大,它是否有利于問(wèn)題求解以及求出的解是否為最優(yōu)啟發(fā)式搜索要用到問(wèn)題自身的某些特性信息,以指導(dǎo)搜索朝著最有希望的方向前進(jìn)啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉鳎赡芸梢哉业阶顑?yōu)解2023/10/20史忠植人工智能導(dǎo)論：搜索算法24啟發(fā)式搜索啟發(fā)性信息和估價(jià)函數(shù)用于指導(dǎo)搜索過(guò)程,且與具體問(wèn)題有關(guān)的控制性信息稱為為啟發(fā)性信息用于評(píng)價(jià)節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù).記為

f(x)=g(x)+h(x)g(x)為從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x已經(jīng)實(shí)際付出的代價(jià)h(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估價(jià)代價(jià),體現(xiàn)了問(wèn)題的啟發(fā)性信息,稱為啟發(fā)函數(shù)f(x)表示從初始節(jié)點(diǎn)經(jīng)過(guò)節(jié)點(diǎn)x到達(dá)目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑的代價(jià)估價(jià)值,其作用是用來(lái)評(píng)估OPEN表中各節(jié)點(diǎn)的重要性,決定其次序2023/10/20史忠植人工智能導(dǎo)論：搜索算法25啟發(fā)式搜索例：八數(shù)碼問(wèn)題，評(píng)價(jià)函數(shù)f(n)=d(n)+W(n)d(n):節(jié)點(diǎn)n的深度;W(n):與目標(biāo)相比,錯(cuò)位的數(shù)字?jǐn)?shù)目;1238476528316475初始狀態(tài)目標(biāo)狀態(tài)2023/10/20史忠植人工智能導(dǎo)論：搜索算法262831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標(biāo)123456八數(shù)碼啟發(fā)式搜索2023/10/20史忠植人工智能導(dǎo)論：搜索算法27啟發(fā)式搜索啟發(fā)式就是要猜測(cè)：從節(jié)點(diǎn)n開始，找到最優(yōu)解的可能性有多大？從起始節(jié)點(diǎn)開始，經(jīng)過(guò)節(jié)點(diǎn)n，到達(dá)目標(biāo)節(jié)點(diǎn)的最佳路徑的費(fèi)用是多少？gh2023/10/20史忠植人工智能導(dǎo)論：搜索算法28局部擇優(yōu)搜索(爬山法)搜索過(guò)程如下:(1)把初始節(jié)點(diǎn)S0放入OPEN表,計(jì)算f(S0)(2)如果OPEN表為空,則問(wèn)題無(wú)解,退出(3)把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出,放入CLOSED表(4)考查節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn).若是,則求得了問(wèn)題的解,退出(5)若節(jié)點(diǎn)n不可擴(kuò)展,則轉(zhuǎn)第(2)步(6)擴(kuò)展節(jié)點(diǎn)n,用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值,并按估價(jià)值從小到大的順序依次放入OPEN表的首部,并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針,轉(zhuǎn)第(2)步2023/10/20史忠植人工智能導(dǎo)論：搜索算法29局部擇優(yōu)搜索(爬山法)爬山法的三個(gè)問(wèn)題：局部最大。高地：也稱為平頂，在某一局部點(diǎn)周圍f(x)為常量。此時(shí)，搜索就無(wú)法確定要搜索的最佳方向，會(huì)產(chǎn)生隨機(jī)走動(dòng)，這使得搜索效率降低。山脊：山脊可能具有陡峭的斜面，所以搜索可以比較容易地到達(dá)山脊的頂部，但是山脊的頂部到山峰之間可能傾斜的很平緩。除非正好有合適的操作符直接沿著山脊的頂部移動(dòng)，該搜索可能會(huì)在山脊的兩面來(lái)回震蕩，搜索的前進(jìn)步伐會(huì)很小。2023/10/20史忠植人工智能導(dǎo)論：搜索算法30全局擇優(yōu)搜索(有序搜索/最好優(yōu)先)搜索過(guò)程如下:(1)把初始節(jié)點(diǎn)S0放入OPEN表,計(jì)算f(S0)(2)如果OPEN表為空,則問(wèn)題無(wú)解,退出(3)把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出,放入CLOSED表(4)考查節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn).若是,則求得了問(wèn)題的解,退出(5)若節(jié)點(diǎn)n不可擴(kuò)展,則轉(zhuǎn)第(2)步(6)擴(kuò)展節(jié)點(diǎn)n,用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值,并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針,把這些子節(jié)點(diǎn)都送入OPEN表,然后對(duì)OPEN表中的全部節(jié)點(diǎn)按估價(jià)值從小到大的順序進(jìn)行排列(7)轉(zhuǎn)第(2)步2023/10/20史忠植人工智能導(dǎo)論：搜索算法31A*算法將狀態(tài)空間一般搜索過(guò)程進(jìn)行如下的限制,就是A*算法把OPEN表中的節(jié)點(diǎn)按估價(jià)函數(shù)f(x)=g(x)+h(x)的值從小到大進(jìn)行排序g(x)是對(duì)g*(x)的估價(jià),g(x)>0h(x)是h*(x)的下界,即對(duì)所有的x,h(x)<=h*(x)其中:

g*(x)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的最小代價(jià)

h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià),若有多個(gè)目標(biāo)節(jié)點(diǎn),則為其中最小的一個(gè)2023/10/20史忠植人工智能導(dǎo)論：搜索算法32A*算法f*(S)f*(S)=g*(S)+h*(S)=h*(S)從S無(wú)約束地到達(dá)目標(biāo)的最佳路經(jīng)上的耗散值;g(n)一般取實(shí)際走過(guò)的路徑的費(fèi)用和.g(n)

g*(n)隨著算法的執(zhí)行，由于指針的變動(dòng)，g(n)會(huì)下降.h

0沒(méi)有啟發(fā)式信息;nSg*(n)h*(n)g2023/10/20史忠植人工智能導(dǎo)論：搜索算法33A*算法8數(shù)碼問(wèn)題h(n)=“不在位”的將牌數(shù)h(n)=將牌“不在位”的距離和2

831

647512345768將牌1：1將牌2：1將牌6：1將牌8：22023/10/20史忠植人工智能導(dǎo)論：搜索算法34A*算法2023/10/20史忠植人工智能導(dǎo)論：搜索算法35A*算法2023/10/20史忠植人工智能導(dǎo)論：搜索算法36A*算法可納性對(duì)于可解狀態(tài)圖(即從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在)所說(shuō),如果一個(gè)搜索算法能在有限步內(nèi)終止,并且能找到最優(yōu)解,則稱該搜索算法是可納的.定理:A*算法是可納的,即在有限步內(nèi)終止,并且找到最優(yōu)解證明思路對(duì)于有限圖,A*算法一定會(huì)在有限步內(nèi)終止對(duì)應(yīng)無(wú)限圖,只要從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在,A*算法也必然終止A*算法一定終止在最優(yōu)路徑上2023/10/20史忠植人工智能導(dǎo)論：搜索算法37A*算法的最優(yōu)性最優(yōu)性A*算法的搜索效率在很大程度上取決于h(x),在滿足h(x)<=h*(x)的前提下,h(x)的值越大越好.H(x)所攜帶的啟發(fā)性信息越多,搜索時(shí)所擴(kuò)展的節(jié)點(diǎn)數(shù)越少,搜索效率就越高2023/10/20史忠植人工智能導(dǎo)論：搜索算法38A*算法的單調(diào)性單調(diào)性限制單調(diào)性限制是指h(x)滿足如下兩個(gè)條件h(Sg)=0設(shè)xj是節(jié)點(diǎn)xi

的任意子節(jié)點(diǎn),則有h(xi)-h(xj)<=c(xi,xj)其中:Sg是目標(biāo)節(jié)點(diǎn),c(xi,xj)是節(jié)點(diǎn)xi到子節(jié)點(diǎn)xj的邊代價(jià)A*算法的h(x)滿足單調(diào)性限制時(shí),可有下面的結(jié)論若A*算法選擇節(jié)點(diǎn)xn進(jìn)行擴(kuò)展,則g(xn)=g*(x)由A*算法所擴(kuò)展的節(jié)點(diǎn)序列其f值是非遞減的2023/10/20史忠植人工智能導(dǎo)論：搜索算法392023/10/20史忠植人工智能導(dǎo)論：搜索算法40內(nèi)容提要3.1概述3.2

盲目搜索

3.3啟發(fā)式搜索

3.4博弈搜索3.5小結(jié)

博弈一向被認(rèn)為是富有挑戰(zhàn)性的智力活動(dòng)，如下棋、打牌、作戰(zhàn)、游戲等等。博弈的研究不斷為人工智能提出新的課題，可以說(shuō)博弈是人工智能研究的起源和動(dòng)力之一。博弈的特性是：兩個(gè)棋手交替地走棋；比賽的最終結(jié)果，是贏、輸和平局中的一種；可用圖搜索技術(shù)進(jìn)行，但效率很低；博弈的過(guò)程，是尋找置對(duì)手于必?cái)B(tài)的過(guò)程；雙方都無(wú)法干預(yù)對(duì)方的選擇。博弈2023/10/20史忠植人工智能導(dǎo)論：搜索算法4120世紀(jì)60年代，研制出的西洋跳棋和國(guó)際象棋達(dá)到了大師級(jí)的水平。1958年麥卡錫提出博弈樹α－β剪枝算法1997年，IBM公司研制的“深藍(lán)”國(guó)際象棋程序，采用博弈樹搜索算法，該程序戰(zhàn)勝了國(guó)際象棋世界冠軍卡斯帕羅夫。博弈2023/10/20史忠植人工智能導(dǎo)論：搜索算法42與深藍(lán)下棋的卡斯帕羅夫1997“深藍(lán)”贏了卡斯帕羅夫2023/10/20史忠植人工智能導(dǎo)論：搜索算法43對(duì)各個(gè)局面進(jìn)行評(píng)估評(píng)估的目的：對(duì)后面的狀態(tài)提前進(jìn)行考慮，并且以各種狀態(tài)的評(píng)估值為基礎(chǔ)作出最好的走棋選擇。評(píng)估的方法：用評(píng)價(jià)函數(shù)對(duì)棋局進(jìn)行評(píng)估。贏的評(píng)估值設(shè)為+∞，輸?shù)脑u(píng)估值設(shè)為-∞，平局的評(píng)估值設(shè)為0。評(píng)估的標(biāo)準(zhǔn)：由于下棋的雙方是對(duì)立的，只能選擇其中一方為評(píng)估的標(biāo)準(zhǔn)方。極大極小搜索過(guò)程2023/10/20史忠植人工智能導(dǎo)論：搜索算法44命名博弈的雙方，一方為“正方”，對(duì)每個(gè)狀態(tài)的評(píng)估都是對(duì)應(yīng)于該方的輸贏的。例如，贏2個(gè)，輸1個(gè)等，都是指正方的。正方每走一步，都在選擇使自己贏得更多的節(jié)點(diǎn)，因此這類節(jié)點(diǎn)稱為“MAX”節(jié)點(diǎn)；另一方為“反方”，對(duì)每個(gè)狀態(tài)的評(píng)估都是對(duì)應(yīng)于對(duì)手的輸贏的。例如，贏2個(gè)，輸一個(gè)，其實(shí)是指自己輸2個(gè)，贏1個(gè)的。反方每走一步，都在選擇使對(duì)手輸?shù)酶嗟墓?jié)點(diǎn)，因此這類節(jié)點(diǎn)稱為“MIN”節(jié)點(diǎn)。極大極小搜索過(guò)程2023/10/20史忠植人工智能導(dǎo)論：搜索算法45極大極小搜索過(guò)程2023/10/20史忠植人工智能導(dǎo)論：搜索算法46015-333-3022-30-23541-30689-30-33-3-3-21-36-3031601MAXMINMAXMIN極大極小搜索過(guò)程2023/10/20史忠植人工智能導(dǎo)論：搜索算法47-剪枝法的引入在極大極小法中，必須求出所有終端節(jié)點(diǎn)的評(píng)估值，當(dāng)預(yù)先考慮的棋步比較多時(shí)，計(jì)算量會(huì)大大增加。為了提高搜索的效率，引入了通過(guò)對(duì)評(píng)估值的上下限進(jìn)行估計(jì)，從而減少需進(jìn)行評(píng)估的節(jié)點(diǎn)范圍的

-剪枝法。

-搜索過(guò)程2023/10/20史忠植人工智能導(dǎo)論：搜索算法48MAX節(jié)點(diǎn)的評(píng)估下限值

作為正方出現(xiàn)的MAX節(jié)點(diǎn)，假設(shè)它的MIN子節(jié)點(diǎn)有N個(gè)，那么當(dāng)它的第一個(gè)MIN子節(jié)點(diǎn)的評(píng)估值為時(shí)，則對(duì)于其它的子節(jié)點(diǎn)，如果有高過(guò)的，就取那最高的值作為該MAX節(jié)點(diǎn)的評(píng)估值；如果沒(méi)有，則該MAX節(jié)點(diǎn)的評(píng)估值為。MIN節(jié)點(diǎn)的評(píng)估上限值

作為反方出現(xiàn)的MIN節(jié)點(diǎn)，假設(shè)它的MAX子節(jié)點(diǎn)有N個(gè)，那么當(dāng)它的第一個(gè)MAX子節(jié)點(diǎn)的評(píng)估值為時(shí)，則對(duì)于其它子節(jié)點(diǎn)，如果有低于的，就取那個(gè)低于的值作為該MIN節(jié)點(diǎn)的評(píng)估值；如果沒(méi)有，則該MIN節(jié)點(diǎn)的評(píng)估值取。

-搜索過(guò)程2023/10/20史忠植人工智能導(dǎo)論：搜索算法49MAX節(jié)點(diǎn)

MIN節(jié)點(diǎn)=

剪枝ABCD-搜索過(guò)程

剪枝法

設(shè)MAX節(jié)點(diǎn)的下限為，則其所有的MIN子節(jié)點(diǎn)中，其評(píng)估值的上限小于等于的節(jié)點(diǎn)，其以下部分的搜索都可以停止了，即對(duì)這部分節(jié)點(diǎn)進(jìn)行了剪枝。2023/10/20史忠植人工智能導(dǎo)論：搜索算法50

剪枝法設(shè)MIN節(jié)點(diǎn)的上限為，則其所有的MAX子節(jié)點(diǎn)中，其評(píng)估值的下限大于等于的節(jié)點(diǎn)，其以下部分的搜索都可以停止了，即對(duì)這部分節(jié)點(diǎn)進(jìn)行了剪枝。MAX節(jié)點(diǎn)

MIN