版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
前面討論的各種搜索方法都沒有用到問題本身的特性信息,只是按照事先設(shè)定的線路進(jìn)行搜索,具有較大的盲目性。事實(shí)上,如果能夠利用搜索過程所得到的問題自身的一些特性信息來指導(dǎo)搜索過程,則對搜索將是十分有益的。這種利用問題自身的特性信息來引導(dǎo)搜索過程的搜索方法稱為啟發(fā)式搜索。由于啟發(fā)式搜索方法具有較強(qiáng)的針對性,因此,可以縮小搜索范圍,提高搜索效率。4.5狀態(tài)空間的啟發(fā)式搜索1前面討論的各種搜索方法都沒有用到問題本身的特1
啟發(fā)式搜索方法所依據(jù)的是問題自身的啟發(fā)性信息,而啟發(fā)性信息又是通過估價(jià)函數(shù)作用到搜索過程中的。
1.啟發(fā)性信息一.啟發(fā)性信息和估價(jià)函數(shù)
啟發(fā)性信息是指那種與具體問題求解過程有關(guān)的,并可指導(dǎo)搜索過程朝著最有希望方向前進(jìn)的控制信息。啟發(fā)性信息一般有以下三種:
①有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息;
②有效地幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成;
③能決定在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)哪些節(jié)點(diǎn)應(yīng)從搜索樹上被刪除。
一般來說,搜索過程所使用的啟發(fā)性信息的啟發(fā)能力越強(qiáng),擴(kuò)展的無用節(jié)點(diǎn)就越少。2啟發(fā)式搜索方法所依據(jù)的是問題自身的啟發(fā)性信息2
2.估價(jià)函數(shù)用來估計(jì)節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)。估價(jià)函數(shù)f(n)被定義為從初始節(jié)點(diǎn)S0出發(fā),經(jīng)過節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)Sg的所有路徑中最小路徑代價(jià)的估計(jì)值。它的一般形式為
f(n)=g(n)+h(n)
其中,g(n)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的實(shí)際代價(jià);h(n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)S0的最優(yōu)路徑的估計(jì)代價(jià)。對g(n)的值,可以按指向父節(jié)點(diǎn)的指針,從節(jié)點(diǎn)n反向跟蹤到初始節(jié)點(diǎn)S0,得到一條從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的最小代價(jià)路徑,然后把這條路徑上所有有向邊的代價(jià)相加,就得到g(n)的值。對h(n)的值,則需要根據(jù)問題自身的特性來確定,它體現(xiàn)的是問題自身的啟發(fā)性信息,因此也稱h(n)為啟發(fā)函數(shù)。ng(n)h(n)32.估價(jià)函數(shù)用來估計(jì)節(jié)點(diǎn)重要性的函數(shù)稱為估3例:八數(shù)碼難題。設(shè)問題的初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如前所述,且估價(jià)函數(shù)為:f(n)=d(n)+W(n)
其中,d(n)表示節(jié)點(diǎn)n在搜索樹中的深度;w(n)表示節(jié)點(diǎn)n中“不在位”的數(shù)碼個(gè)數(shù)。請計(jì)算初始狀態(tài)S0的估價(jià)函數(shù)值f(S0)。
解:在本例的估價(jià)函數(shù)中,取g(n)=d(n),h(n)=W(n)。它說明是用從S0到n的路徑上的單位代價(jià)表示實(shí)際代價(jià),用n中“不在位”的數(shù)碼個(gè)數(shù)作為啟發(fā)信息。一般來說,某節(jié)點(diǎn)中的“不在位”的數(shù)碼個(gè)數(shù)越多,說明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn)。
對初始節(jié)點(diǎn)S0,由于d(S0)=0,W(S0)=3,因此有
f(S0)=0+3=3
這個(gè)例子僅是為了說明估價(jià)函數(shù)的含義及估價(jià)函數(shù)值的計(jì)算。在問題搜索過程中,除了需要計(jì)算初始節(jié)點(diǎn)的估價(jià)函數(shù)之外,更多的是要計(jì)算新生成節(jié)點(diǎn)的估價(jià)函數(shù)值。
283147654例:八數(shù)碼難題。設(shè)問題的初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如前4二.A算法
在圖搜索算法中,如果能在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)對Open表中的節(jié)點(diǎn)進(jìn)行排序,則該搜索算法為A算法。由于估價(jià)函數(shù)中帶有問題自身的啟發(fā)性信息,因此,A算法也被稱為啟發(fā)式搜索算法。
對啟發(fā)式搜索算法,又可根據(jù)搜索過程中選擇擴(kuò)展節(jié)點(diǎn)的范圍,將其分為全局擇優(yōu)搜索算法和局部擇優(yōu)搜索算法。5二.A算法在圖搜索算法中,如果能在搜索的5每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí),總是從Open表的所有節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。其搜索過程可描述如下:
(1)把S0放入Open表中,f(s0)=g(So)+h(So);
(2)如果Open表為空,則問題無解,失敗退出;
(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表,記該節(jié)點(diǎn)為n;
(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是,則找到了問題的解,成功退出;
(5)若節(jié)點(diǎn)n不可擴(kuò)展,則轉(zhuǎn)第(2)步;
(6)擴(kuò)展節(jié)點(diǎn)n,生成其子節(jié)點(diǎn)ni(i=1,2,……),計(jì)算每一個(gè)子節(jié)點(diǎn)的估價(jià)值f(ni)(i=1,2,……),并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針,然后將這些子節(jié)點(diǎn)放入Open表中;
(7)根據(jù)各節(jié)點(diǎn)的估價(jià)函數(shù)值,對Open表中的全部節(jié)點(diǎn)按從小到大的順序重新進(jìn)行排序;
(8)轉(zhuǎn)第(2)步。
1.全局擇優(yōu)搜索6每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí),總是從Open表的所有節(jié)點(diǎn)中選擇6由于上述算法的第(7)步要對Open表中的全部節(jié)點(diǎn)按其估價(jià)函數(shù)值從小到大重新進(jìn)行排序,這樣在算法第(3)步取出的節(jié)點(diǎn)就一定是Open表的所有節(jié)點(diǎn)中估價(jià)函數(shù)值最小的一個(gè)節(jié)點(diǎn)。因此,它是一種全局擇優(yōu)的搜索方式。
對上述算法進(jìn)一步分析還可以發(fā)現(xiàn):如果取估價(jià)函數(shù)f(n)=g(n),則它將退化為代價(jià)樹的廣度優(yōu)先搜索;如果取估價(jià)函數(shù)f(n)=d(n),則它將退化為廣度優(yōu)先搜索??梢?,廣度優(yōu)先搜索和代價(jià)樹的廣度優(yōu)先搜索是全局擇優(yōu)搜索的兩個(gè)特例。7由于上述算法的第(7)步要對Open表中的全7例:八數(shù)碼難題。2834765S028314765238476528347652836475
8321476528371465
23847652384765
S9
4123847651238476512378465S5
5S66
S8
6
S7
4SgS10
4S11
6S1
4S2
4
S3
5S4
58例:八數(shù)碼難題。283S028328在局部擇優(yōu)搜索中,每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí),總是從剛生成的子節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。其搜索過程可描述如下:(1)把初始節(jié)點(diǎn)S0放入Open表中,f(S0)=g(S0)+h(S0);(2)如果Open表為空,則問題無解,失敗退出;
(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表,并記該節(jié)點(diǎn)為n;
(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是,則找到了問題的解,成功退出;
(5)若節(jié)點(diǎn)n不可擴(kuò)展,則轉(zhuǎn)第(2)步;
(6)擴(kuò)展節(jié)點(diǎn)n,生成其子節(jié)點(diǎn)ni(i=1,2,…),計(jì)算每一個(gè)子節(jié)點(diǎn)的估價(jià)值f(ni)(i=1,2,…),并按估價(jià)值從小到大的順序依次放入Open表的首部,并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針,然后轉(zhuǎn)第(2)步。
2.局部擇優(yōu)搜索(瞎子爬山法)9在局部擇優(yōu)搜索中,每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí),總是從9
由于這一算法的第(6)步僅是把剛生成的子節(jié)點(diǎn)按其估價(jià)函數(shù)值從小到大放入Open表的首都,這樣在算法第(3)步取出的節(jié)點(diǎn)僅是剛生成的子節(jié)點(diǎn)中估價(jià)函數(shù)值最小的一個(gè)節(jié)點(diǎn)。因此,它是一種局部擇優(yōu)的搜索方式。對這一算法進(jìn)一步分析也可以發(fā)現(xiàn):如果取估價(jià)函數(shù)f(n)=g(n),則它將退化為代價(jià)樹的深度優(yōu)先搜索;如果取估價(jià)函數(shù)f(n)=d(n),則它將退化為深度優(yōu)先搜索。可見,深度優(yōu)先搜索和代價(jià)樹的深度優(yōu)先搜索是局部擇優(yōu)搜索的兩個(gè)特例。10由于這一算法的第(6)步僅是把剛生成的子節(jié)點(diǎn)10三.A*算法前面討論的啟發(fā)式搜索算法,都沒有對估價(jià)函數(shù)f(n)作任何限制。實(shí)際上,估價(jià)函數(shù)對搜索過程是十分重要的,如果選擇不當(dāng),則有可能找不到問題的解,或者找到的不是問題的最優(yōu)解。為此,需要對估價(jià)函數(shù)進(jìn)行某些限制。A*算法就是對估價(jià)函數(shù)加上一些限制后得到的一種啟發(fā)式搜索算法。11三.A*算法前面討論的啟發(fā)式搜索算法,都沒11假設(shè)f*(n)為從初始節(jié)點(diǎn)S0出發(fā),約束經(jīng)過節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的最小代價(jià)值。估價(jià)函數(shù)f(n)是f*(n)的估計(jì)值。顯然,f*(n)應(yīng)由以下兩部分所組成:一部分是從初始節(jié)點(diǎn)到節(jié)點(diǎn)n的最小代價(jià),記為g*(n);另一部分是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最小代價(jià),記為h*(n),當(dāng)問題有多個(gè)目標(biāo)節(jié)點(diǎn)時(shí),應(yīng)取其中代價(jià)最小的一個(gè)。因此有
f*(n)=g*(n)+h*(n)
把估價(jià)函數(shù)f(n)與f*(n)相比,g(n)是對g*(n)的一個(gè)估計(jì),h(n)是對h*(n)的一個(gè)估計(jì)。在這兩個(gè)估計(jì)中,盡管g(n)的值容易計(jì)算,但它不一定就是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的真正最小代價(jià),很有可能從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的真正最小代價(jià)還沒有找到,故有g(shù)(n)≥g*(n)。
有了g*(n)和h*(n)的定義,如果對A算法(全局擇優(yōu)的啟發(fā)式搜索算法)中的g(n)和h(n)分別提出如下限制:
第一,g(n)是對g*(n)的估計(jì),且g(n)>0;
第二,h(n)是h*(n)的下界,即對任意節(jié)點(diǎn)n均有
h(n)≤h*(n)。
則稱得到的算法為A*算法。12假設(shè)f*(n)為從初始節(jié)點(diǎn)S0出發(fā),約束經(jīng)過12A*算法的有關(guān)特性。
1.A*算法的可納性
一般來說,對任意一個(gè)狀態(tài)空間圖,當(dāng)從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在時(shí),如果搜索算法能在有限步內(nèi)找到一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑,并在此路徑上結(jié)束,則稱該搜索算法是可采納的。A*算法是可采納的。(證明略)。
2.A*算法的最優(yōu)性
A*算法的搜索效率很大程度上取決于估價(jià)函數(shù)h(n)。一般來說,在滿足h(n)≤h*(n)的前提下,h(n)的值越大越好。h(n)的值越大,說明它攜帶的啟發(fā)性信息越多,A*算法搜索時(shí)擴(kuò)展的節(jié)點(diǎn)就越少,搜索效率就越高。A*算法的這一特性也稱為信息性。(證明略)13A*算法的有關(guān)特性。
1313A*算法應(yīng)用舉例
例:八數(shù)碼難題。問題的初始狀態(tài)和目標(biāo)狀態(tài)和前例相同。要求用A*算法解決該問題。
解:在上例中,我們?nèi)(n)=W(n)。盡管我們對h*(n)不能確切知道,但當(dāng)采用單位代價(jià)時(shí),通過對“不在位”數(shù)碼個(gè)數(shù)的估計(jì),可以得出至少要移動W(n)步才能到達(dá)目標(biāo),顯然有W(n)≤h*(n)。因此,前例中所定義的h(n)滿足A*算法的限制條件。
這里再取另外一種啟發(fā)函數(shù)h(n)=P(n),P(n)定義為每一個(gè)數(shù)碼與其目標(biāo)位置之間距離(不考慮夾在其間的數(shù)碼)的總和,同樣可以斷定至少要移動P(n)步才能到達(dá)目標(biāo),因此有P(n)≤h*(n),即滿足A*算法的限制條件。
23847655238476114A*算法應(yīng)用舉例
例:八數(shù)碼難題。問題的初始狀態(tài)和目標(biāo)狀1428314765h*=4,f=4S0231
8476528316475283
1476528314765g*=1
2318476523184765g*=21
23847651
2378465Sgg*=4h*=5,f=6h*=5,f=6h*=3,f=4h*=5,f=6h*=2,f=4h*=4,f=61
2384765g*=3h*=1,f=4h*=0,f=4h*=1,f=6八數(shù)碼難題h(n)=P(n)的搜索樹15283h*=4,f=4S0232832815例:設(shè)有如下結(jié)構(gòu)的移動將牌游戲B代表黑色牌,W代表白色牌;E代表該位置為空。玩法:當(dāng)一個(gè)牌移入相鄰的空位時(shí),費(fèi)用等于挑過的牌數(shù)加1。一個(gè)牌至多可跳過兩個(gè)牌進(jìn)入空位置,其費(fèi)用等于跳過的牌數(shù)加1。要求把所有的B都移到所有的W的右邊,設(shè)計(jì)h(x)。解:顯然W左邊的B越少越接近目標(biāo),因此可用W左邊B的個(gè)數(shù)作為h(x)h(x)=3*(每個(gè)W左邊B個(gè)數(shù)的總和)h(x)=3*(2+2+3)=21BBBWWWEBBBWWWE16例:設(shè)有如下結(jié)構(gòu)的移動將牌游戲BBBWWWEBBBWWWE116例:傳教士和野人問題。請用A*算法解決該問題。
解:用m表示左岸的傳道士人數(shù),c表示左岸的野人數(shù),b表示左岸的船數(shù),用三元組(m,c,b)表示問題的狀態(tài)。
對A*算法,首先需要確定估價(jià)函數(shù)。
設(shè)g(n)=d(n),h(n)=m+c-2b,
則有
f(n)=g(n)+h(n)=d(n)+m+c-2b
其中,d(n)為節(jié)點(diǎn)的深度。通過分析可知h(n)<h*(n),滿足A*算法的限制條件。
M-C問題的搜索過程如下頁圖所示。在該圖中,每個(gè)節(jié)點(diǎn)旁邊還標(biāo)出了該節(jié)點(diǎn)的h值和f值。17例:傳教士和野人問題。請用A*算法解決該問題。
解:用m表示17(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=4,f=4f(n)=d(n)+m+c-2bhh=5,f=6h=4,f=5h=4,f=5(3,2,1)h=3,f=5(2,1,0)(3,0,0)h=3,f=6h=3,f=6(2,2,1)(3,1,1)h=2,f=6h=2,f=6h=2,f=7h=2,f=7傳教士和野人問題的搜索圖(0,0,0)(0,3,1)h=1,f=7(0,1,0)h=1,f=8(0,2,1)h=0,f=8(0,2,0)(1,1,0)18(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=181919194.4與/或樹的盲目搜索204.4與/或樹的盲目搜索2020概念:直接可解的簡單問題稱為本原問題,本原問題對應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn),在與或圖(樹)中無子節(jié)點(diǎn)的節(jié)點(diǎn)稱為端節(jié)點(diǎn),一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)如果是“與”關(guān)系,則該節(jié)點(diǎn)便稱為與節(jié)點(diǎn),一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)如果是“或”關(guān)系,則該節(jié)點(diǎn)便稱為或節(jié)點(diǎn)。注意,終止節(jié)點(diǎn)一定是端節(jié)點(diǎn),但端節(jié)點(diǎn)不一定是終止節(jié)點(diǎn)。可解性判別(1)一個(gè)節(jié)點(diǎn)是可解,則節(jié)點(diǎn)須滿足下列條件之一:①終止節(jié)點(diǎn)是可解節(jié)點(diǎn);②一個(gè)與節(jié)點(diǎn)可解,當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全都可解;③一個(gè)或節(jié)點(diǎn)可解,只要其子節(jié)點(diǎn)至少有一個(gè)可解。(2)一個(gè)節(jié)點(diǎn)是不可解,則節(jié)點(diǎn)須滿足下列條件之一:①非終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn);②一個(gè)與節(jié)點(diǎn)不可解,只要其子節(jié)點(diǎn)至少有一個(gè)不可解;③一個(gè)或節(jié)點(diǎn)不可解,當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全都不可解。21概念:2121一.與/或樹的一般搜索與/或樹的搜索過程實(shí)際上是一個(gè)不斷尋找解樹的過程。其一般搜索過程如下:
(1)把原始問題作為初始節(jié)點(diǎn)S0,并把它作為當(dāng)前節(jié)點(diǎn);
(2)應(yīng)用分解或等價(jià)變換操作對當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展;
(3)為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針;
(4)選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn),反復(fù)執(zhí)行第(2)步和第(3)步,在此期間需要多次調(diào)用可解標(biāo)記過程或不可解標(biāo)記過程,直到初始節(jié)點(diǎn)被標(biāo)記為可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)為止。
上述搜索過程將形成一棵與/或樹,這種由搜索過程形成的與/或樹稱為搜索樹。當(dāng)搜索成功時(shí),經(jīng)可解標(biāo)記過程標(biāo)識的由初始節(jié)點(diǎn)及其下屬的可解節(jié)點(diǎn)構(gòu)成的子樹稱為解樹。用與/或樹法表示的問題求解過程與狀態(tài)空間法類似,也是通過搜索來實(shí)現(xiàn)對問題求解的。與/或樹的搜索策略也分為盲目搜索和啟發(fā)式搜索兩大類。22一.與/或樹的一般搜索與/或樹的搜索過程實(shí)22搜索過程中的可解標(biāo)記過程與不可解標(biāo)記過程都是自下而上進(jìn)行的,即由子節(jié)點(diǎn)的可解性確定父節(jié)點(diǎn)、祖父節(jié)點(diǎn)的可解性;由子節(jié)點(diǎn)的不可解性確定父節(jié)點(diǎn)、祖父節(jié)點(diǎn)的不可解性。在與/或樹中,除端節(jié)點(diǎn)和終止節(jié)點(diǎn)外,一個(gè)節(jié)點(diǎn)的可解性完全是由其子節(jié)點(diǎn)來決定的。對與節(jié)點(diǎn),只有其所有子節(jié)點(diǎn)都為可解時(shí)它才為可解,只要有一個(gè)子節(jié)點(diǎn)不可解它就是不可解的;對或節(jié)點(diǎn),只要有一個(gè)子節(jié)點(diǎn)可解它就是可解的,僅當(dāng)所有子節(jié)點(diǎn)都是不可解時(shí)它才為不可解。這種由可解子節(jié)點(diǎn)來確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)為可解節(jié)點(diǎn)的過程稱為可解標(biāo)記過程;由不可解子節(jié)點(diǎn)來確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)為不可解節(jié)點(diǎn)的過程稱為不可解標(biāo)記過程。
由于與/或樹搜索的目標(biāo)是尋找解樹,因此,如果搜索過程確定某個(gè)節(jié)點(diǎn)為可解節(jié)點(diǎn),則其不可解的后裔節(jié)點(diǎn)就可從搜索樹中刪去;同樣,如果搜索過程能確定某個(gè)節(jié)點(diǎn)為不可解節(jié)點(diǎn),則其后裔節(jié)點(diǎn)也可從搜索樹中刪去。23搜索過程中的可解標(biāo)記過程與不可解標(biāo)記過程都是自下而上進(jìn)行的,23與狀態(tài)空間的廣度優(yōu)先搜索類似,只是在搜索過程中需要多次調(diào)用可解標(biāo)記過程或不可解標(biāo)記過程,其搜索算法如下:
(1)把初始節(jié)點(diǎn)S0放人Open表中;
(2)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表,并記該節(jié)點(diǎn)為n;
(3)如果節(jié)點(diǎn)n可擴(kuò)展,則做下列工作:
①擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)放入Open表的尾部,并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針;
②考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。若有,則標(biāo)記這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn),并用可解標(biāo)記過程對其父節(jié)點(diǎn)及先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始解節(jié)點(diǎn)S0能夠被標(biāo)記為可解節(jié)點(diǎn),就得到了解樹,搜索成功,退出搜索過程;如果不能確定S0為可解節(jié)點(diǎn),則從Open表中刪去具有可解先輩的節(jié)點(diǎn);
③
轉(zhuǎn)第(2)步。二.與/或樹的廣度優(yōu)先搜索24與狀態(tài)空間的廣度優(yōu)先搜索類似,只是在搜索過程24(4)如果節(jié)點(diǎn)n不可擴(kuò)展,則做下列工作:
①
標(biāo)記節(jié)點(diǎn)n為不可解節(jié)點(diǎn);
②
應(yīng)用不可解標(biāo)記過程對節(jié)點(diǎn)n的先輩中不可解的節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始解節(jié)點(diǎn)S0也被標(biāo)記為不可解節(jié)點(diǎn),則搜索失敗,表明原始問題無解,退出搜索過程;如果不能確定S0為不可解節(jié)點(diǎn),則從Open表中刪去具有不可解先輩的節(jié)點(diǎn);
③轉(zhuǎn)第(2)步。25(4)如果節(jié)點(diǎn)n不可擴(kuò)展,則做下列工作:
25例:設(shè)有如下圖所示的與/或樹,節(jié)點(diǎn)按圖中所標(biāo)注的順序號進(jìn)行擴(kuò)展,其中標(biāo)有t1、t2、t3的節(jié)點(diǎn)是終止節(jié)點(diǎn),A、B、C為不可解的端節(jié)點(diǎn)。
與/或樹的廣度優(yōu)先搜索123A4t1t3CBt25搜索過程為:
(1)先擴(kuò)展1號節(jié)點(diǎn),生成2號節(jié)點(diǎn)和3號節(jié)點(diǎn),由于這兩個(gè)子節(jié)點(diǎn)都不是終止節(jié)點(diǎn),因此接著擴(kuò)展2號節(jié)點(diǎn)。(2)擴(kuò)展2號節(jié)點(diǎn),生成A節(jié)點(diǎn)和4號節(jié)點(diǎn)。由于這兩個(gè)子節(jié)點(diǎn)均不是終止節(jié)點(diǎn),因此接著擴(kuò)展3號節(jié)點(diǎn)。(3)擴(kuò)展3號節(jié)點(diǎn),生成t1節(jié)點(diǎn)和5號節(jié)點(diǎn)。由于t1為終止節(jié)點(diǎn),則標(biāo)記它為可解節(jié)點(diǎn),并應(yīng)用可解標(biāo)記過程,對其先輩中的可解節(jié)點(diǎn)進(jìn)行標(biāo)記,由于t1的父節(jié)點(diǎn)是一個(gè)與節(jié)點(diǎn),因此不能確定3號節(jié)點(diǎn)是否可解。(4)擴(kuò)展節(jié)點(diǎn)A,由于A是端節(jié)點(diǎn),調(diào)用不可解標(biāo)記過程,由于2號節(jié)點(diǎn)是或節(jié)點(diǎn),因此不能確定2號節(jié)點(diǎn)是不可解節(jié)點(diǎn)。(5)擴(kuò)展4號節(jié)點(diǎn),生成t2節(jié)點(diǎn)和B節(jié)點(diǎn)。由于t2為終止節(jié)點(diǎn),則標(biāo)記它為可解節(jié)點(diǎn),并應(yīng)用可解標(biāo)記過程,標(biāo)記4號節(jié)點(diǎn)為可解節(jié)點(diǎn),標(biāo)記2號節(jié)點(diǎn)為可解節(jié)點(diǎn),但不能標(biāo)記1號節(jié)點(diǎn)為可解節(jié)點(diǎn)。(6)擴(kuò)展5號節(jié)點(diǎn),生成t3節(jié)點(diǎn)和C節(jié)點(diǎn)。由于t3為終止節(jié)點(diǎn),標(biāo)記它為可解節(jié)點(diǎn),并應(yīng)用可解標(biāo)記過程,標(biāo)記5號節(jié)點(diǎn)為可解節(jié)點(diǎn),標(biāo)記3號節(jié)點(diǎn)為可解節(jié)點(diǎn)。標(biāo)記1號節(jié)點(diǎn)為可解節(jié)點(diǎn)。(7)搜索成功,得到由1、2、3、4、5號節(jié)點(diǎn)及t1、t2、t3節(jié)點(diǎn)構(gòu)成的解樹。該解樹如上圖中的粗線所示。26例:設(shè)有如下圖所示的與/或樹,節(jié)點(diǎn)按圖中所標(biāo)注的順序號26可以帶有深度限制dm,其搜索算法如下:
(1)把初始節(jié)點(diǎn)S0放入Open表中;
(2)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表,并記該節(jié)點(diǎn)為n;
(3)如果節(jié)點(diǎn)n的深度等于dm,則轉(zhuǎn)第(5)步的第①點(diǎn);
(4)如果節(jié)點(diǎn)n可擴(kuò)展,則做下列工作:
①
擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)放入Open表的首部,并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針;
②
考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。若有,則標(biāo)記這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn),并用可解標(biāo)記過程對其父節(jié)點(diǎn)及先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始節(jié)點(diǎn)S0能夠被標(biāo)記為可解節(jié)點(diǎn),就得到了解樹,搜索成功,退出搜索過程;如果不能確定S0為可解節(jié)點(diǎn),則從Open表中刪去具有可解先輩的節(jié)點(diǎn);
③
轉(zhuǎn)第(2)步。三.與/或樹的深度優(yōu)先搜索27可以帶有深度限制dm,其搜索算法如下:
(1)把初始27(5)如果節(jié)點(diǎn)n不可擴(kuò)展,則做下列工作:
①
標(biāo)記節(jié)點(diǎn)n為不可解節(jié)點(diǎn);
②應(yīng)用不可解標(biāo)記過程對節(jié)點(diǎn)n的先輩中不可解的節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始節(jié)點(diǎn)S0也被標(biāo)記為不可解節(jié)點(diǎn),則搜索失敗,表明原始問題無解,退出搜索過程;如果不能確定為不可解節(jié)點(diǎn),則從Open表中刪去具有不可解先輩的節(jié)點(diǎn);
③
轉(zhuǎn)第(2)步。
與/或樹的深度優(yōu)先搜索123A4t1t3CBt25例如,對上例所給出的與/或樹,若按有界深度優(yōu)先搜索,且給定dm=4,則其擴(kuò)展節(jié)點(diǎn)的順序?yàn)椋?/p>
1,3,5,2,4
其解樹與上例相同。28(5)如果節(jié)點(diǎn)n不可擴(kuò)展,則做下列工作:
28與/或樹的盲目搜索是按確定路線進(jìn)行的,當(dāng)要選擇一個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展時(shí),只是根據(jù)節(jié)點(diǎn)在與/或樹中所處的位置,而沒有考慮要付出的代價(jià),因而求得的解樹不一定是代價(jià)最小的解樹,即不一定是最優(yōu)解樹。因此,需要考慮與/或樹的啟發(fā)式搜索。在討論與/或樹的啟發(fā)式搜索過程之前,需要先討論幾個(gè)有關(guān)的概念。
一.解樹的代價(jià)與希望樹
與/或樹的啟發(fā)式搜索過程是一種利用搜索過程所得到的啟發(fā)性信息尋找最優(yōu)解樹的過程。對搜索的每一步,算法都試圖找到一個(gè)最有希望成為最優(yōu)解樹的子樹。最優(yōu)解樹是指代價(jià)最小的那棵解樹。4.5與/或樹的啟發(fā)式搜索29與/或樹的盲目搜索是按確定路線進(jìn)行的,當(dāng)要291.解樹的代價(jià)
在與/或樹的啟發(fā)式搜索過程中,解樹的代價(jià)可按如下規(guī)則計(jì)算:
(1)若n為終止節(jié)點(diǎn),則其代價(jià)h(n)=0。
(2)若n為或節(jié)點(diǎn),且子節(jié)點(diǎn)為n1,n2,…,nk,則n的代價(jià)為h(n)=min{c(n,ni)+h(ni)}(1≤i≤k)其中,c(n,ni)是節(jié)點(diǎn)n到其子節(jié)點(diǎn)ni的邊代價(jià)。
(3)若n為與節(jié)點(diǎn),且子節(jié)點(diǎn)為n1,n2,…,nk,則n的代價(jià)可用和代價(jià)法或最大代價(jià)法。
若用和代價(jià)法,則其計(jì)算公式為:h(n)=Σ((c(n,ni)+h(ni))i=1,2,……,k
若用最大代價(jià)法,則其計(jì)算公式為:
h(n)=max{c(n,ni)+h(ni)}(1≤i≤k)
(4)若n是端節(jié)點(diǎn),但又不是終止節(jié)點(diǎn),則n不可擴(kuò)展,其代價(jià)定義為h(n)=∞
(5)根節(jié)點(diǎn)的代價(jià)即為解樹的代價(jià)。301.解樹的代價(jià)
在與/或樹的啟發(fā)式搜索過程中30例:設(shè)右圖是一棵與/或樹,其中包括兩棵解樹,左邊的解樹由S0、A、t1、C及t3組成;右邊的解樹由S0、B、t2、D及t4組成。在此與/或樹中,t1、t2、t3、t4為終止節(jié)點(diǎn);E、F是端節(jié)點(diǎn);邊上的數(shù)字是該邊的代價(jià)。請計(jì)算解樹的代價(jià)。S0ABt1Ct3Et2Dt4F與/或樹的代價(jià)22463521解:先計(jì)算左邊的解樹
按和代價(jià):h(S0)=2+4+6+2=14
按最大代價(jià):h(S0)=8+2=10
再計(jì)算右邊的解樹
按和代價(jià):h(S0)=1+5+3+2=11
按最大代價(jià):h(S0)=6+2=8
在本例中,無論按和代價(jià)還是最大代價(jià),右邊的解樹都是最優(yōu)解樹。但在有些情況下,當(dāng)采用的代價(jià)法不同時(shí),找到的最優(yōu)解樹有可能不同。31例:設(shè)右圖是一棵與/或樹,其中包括兩棵解樹,左邊的解樹由S312.希望樹
為了找到最優(yōu)解樹,搜索過程的任何時(shí)刻都應(yīng)該選擇那些最有希望成為最優(yōu)解樹一部分的節(jié)點(diǎn)進(jìn)行擴(kuò)展。由于這些節(jié)點(diǎn)及其父節(jié)點(diǎn)所構(gòu)成的與/或樹最有可能成為最優(yōu)解樹的一部分,因此稱它為希望解樹,也簡稱為希望樹。需要注意,希望解樹是會隨搜索過程而不斷變化的。定義:希望解樹T
(1)初始節(jié)點(diǎn)S0在希望樹T中;
(2)如果n是具有子節(jié)點(diǎn)n1,n2,…,nk的或節(jié)點(diǎn),則n的某個(gè)子節(jié)點(diǎn)ni在希望樹T中的充分必要條件是
h(n)=min{c(n,ni)+h(ni)}1≤i≤k
(3)如果n是與節(jié)點(diǎn),則n的全部子節(jié)點(diǎn)都在希望樹T中。322.希望樹
為了找到最優(yōu)解樹,搜索過程的任何時(shí)刻都應(yīng)32
與/或樹的啟發(fā)式搜索需要不斷地選擇、修正希望樹,其搜索過程如下:
(1)把初始節(jié)點(diǎn)S0放入Open表中,計(jì)算h(S0);
(2)計(jì)算希望樹T;
(3)依次在Open表中取出T的端節(jié)點(diǎn)放入Closed表,記節(jié)點(diǎn)為n;
(4)如果節(jié)點(diǎn)n為終止節(jié)點(diǎn),則做下列工作:
①標(biāo)記節(jié)點(diǎn)n為可解節(jié)點(diǎn);
②在T上應(yīng)用可解標(biāo)記過程,對n的先輩節(jié)點(diǎn)中的所有可解節(jié)點(diǎn)進(jìn)行標(biāo)記;
③如果初始節(jié)點(diǎn)S0能夠被標(biāo)記為可解節(jié)點(diǎn),則T就是最優(yōu)解樹,成功退出;
④
否則,從Open表中刪去具有可解先輩的所有節(jié)點(diǎn);
⑤轉(zhuǎn)第(2)步。二.與/或樹的啟發(fā)式搜索過程33與/或樹的啟發(fā)式搜索需要不斷地選擇、修正希望樹,其搜33(5)如果節(jié)點(diǎn)n不是終止節(jié)點(diǎn),但可擴(kuò)展,則做下列工作:
①擴(kuò)展節(jié)點(diǎn)n,生成n的所有子節(jié)點(diǎn);
②把這些子節(jié)點(diǎn)都放入Open表中,并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)n的指針;
③計(jì)算這些子節(jié)點(diǎn)及其先輩節(jié)點(diǎn)的h值;
④
轉(zhuǎn)第(2)步。
(6)如果節(jié)點(diǎn)n不是終止節(jié)點(diǎn),且不可擴(kuò)展,則做下列工作:
①
標(biāo)記節(jié)點(diǎn)n為不可解節(jié)點(diǎn);
②
在T上應(yīng)用不可解標(biāo)記過程,對n的先輩節(jié)點(diǎn)中的所有不可解節(jié)點(diǎn)進(jìn)行標(biāo)記;
③
如果初始節(jié)點(diǎn)S0能夠被標(biāo)記為不可解節(jié)點(diǎn),則問題無解,失敗退出;
④否則,從Open表中刪去具有不可解先輩的所有節(jié)點(diǎn);
⑤轉(zhuǎn)第(2)步。34(5)如果節(jié)點(diǎn)n不是終止節(jié)點(diǎn),但可擴(kuò)展,則做下列工作:
34例,搜索過程每次擴(kuò)展節(jié)點(diǎn)時(shí)都同時(shí)擴(kuò)展兩層,且按一層或節(jié)點(diǎn)、一層與節(jié)點(diǎn)的間隔方式進(jìn)行擴(kuò)展。設(shè)初始節(jié)點(diǎn)為S0,對S0擴(kuò)展后得到的與/或樹如下圖所示。其中,端節(jié)點(diǎn)B、C、E、F下面的數(shù)字是用啟發(fā)函數(shù)估算出的h值,節(jié)點(diǎn)A、D旁邊的數(shù)字是按和代價(jià)法計(jì)算出來的節(jié)點(diǎn)代價(jià)。此時(shí),S0的右子樹是當(dāng)前的希望樹,下面對其端節(jié)點(diǎn)進(jìn)行擴(kuò)展。S0ADBCEF873332擴(kuò)展S0后的與/或樹835例,搜索過程每次擴(kuò)展節(jié)點(diǎn)時(shí)都同時(shí)擴(kuò)展兩層,且35擴(kuò)展節(jié)點(diǎn)E,由右子樹求出的h(S0)=12,而由左子樹求出的h(S0)=9。故當(dāng)前的希望樹應(yīng)改為左子樹。對B擴(kuò)展兩層。由于H和I是可解節(jié)點(diǎn),調(diào)用可解標(biāo)記過程,得節(jié)點(diǎn)G、B也為可解節(jié)點(diǎn),但不能標(biāo)記S0為可解節(jié)點(diǎn),須繼續(xù)擴(kuò)展。當(dāng)前的希望樹仍然是左子樹。對C擴(kuò)展。擴(kuò)展兩層后得到的與/或樹如圖3所示。S0ADBCEF8332
3222776119圖1擴(kuò)展E后的與/或樹S0ADBCEF8332
3222776119GKHILJ002226圖2擴(kuò)展B后的與/或樹S0DEFABC8332
3222776119IGKHLJ002226MNP005229圖3擴(kuò)展C后的與/或樹9由于N和P是可解節(jié)點(diǎn),調(diào)用可解標(biāo)記過程,得節(jié)點(diǎn)M、C、A也為可解節(jié)點(diǎn),進(jìn)而S0為可解節(jié)點(diǎn)。求出了代價(jià)最小的解樹,即最優(yōu)解樹,如圖中粗線所示。按和代價(jià)法,該最優(yōu)解樹的代價(jià)為9。36擴(kuò)展節(jié)點(diǎn)E,由右子樹求出的h(S0)=1236
博弈是一類富有智能行為的競爭活動,如下棋、打牌、戰(zhàn)爭等。博弈可分為雙人完備信息博弈和機(jī)遇性博弈。所謂雙人完備信息博弈,就是兩位選手對壘,輪流走步,每一方不僅知道對方已經(jīng)走過的棋步,而且還能估計(jì)出對方未來的走步。對弈的結(jié)果是一方贏,另一方輸;或者雙方和局。所謂機(jī)遇性博弈,是指存在不可預(yù)測性的博弈,例如擲幣等。對機(jī)遇性博弈,由于不具備完備信息,因此不作討論。假設(shè)博弈的一方為MAX,另一方為MIN。在博弈過程的每一步,可供MAX和MIN選擇的行動方案都可能有多種。從MAX方的觀點(diǎn)看,可供自己選擇的那些行動方案之間是“或”的關(guān)系,選擇哪個(gè)方案完全是由自己決定的;而對那些可供MIN選擇的行動方案之間則是“與”的關(guān)系,主動權(quán)掌握在MIN的手里,任何一個(gè)方案都有可能被MIN選中,MAX必須防止那種對自己最為不利的情況的發(fā)生。4.6博弈樹的啟發(fā)式搜索一.概述37博弈是一類富有智能行為的競爭活動,如下棋、打37若把雙人完備信息博弈過程用圖表示出來,就可得到一棵與/或樹,這種與/或樹被稱為博弈樹。在博弈樹中,那些下一步該MAX走步的節(jié)點(diǎn)稱為MAX節(jié)點(diǎn),而下一步該MIN走步的節(jié)點(diǎn)稱為MIN節(jié)點(diǎn)。博弈樹具有如下特點(diǎn):(l)博弈的初始狀態(tài)是初始節(jié)點(diǎn);(2)博弈樹中的“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)是逐層交替出現(xiàn)的;(3)整個(gè)博弈過程始終站在某一方的立場上,所有能使自己一方獲勝的終局都是本原問題,相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn);所有使對方獲勝的終局都是不可解節(jié)點(diǎn)。例如,站在MAX方,所有能使MAX方獲勝的節(jié)點(diǎn)都是可解節(jié)點(diǎn),所有能使MIN方獲勝的節(jié)點(diǎn)都是不可解節(jié)點(diǎn)。38若把雙人完備信息博弈過程用圖表示出來,就可得38對簡單的博弈問題,可以生成整個(gè)博弈樹,找到必勝的策略。但對于復(fù)雜的博弈,如國際象棋,大約有10120個(gè)節(jié)點(diǎn),要生成整個(gè)搜索樹是不可能的。一種可行的方法是用當(dāng)前正在考察的節(jié)點(diǎn)生成一棵部分博弈樹,由于該博弈樹的葉節(jié)點(diǎn)一般不是哪一方的獲勝節(jié)點(diǎn),因此,需利用估價(jià)函數(shù)f(n)對葉節(jié)點(diǎn)進(jìn)行靜態(tài)評估,對MAX有利的節(jié)點(diǎn)其估價(jià)函數(shù)取正值;那些對MIN有利的節(jié)點(diǎn),其估價(jià)函數(shù)取負(fù)值;那些使雙方均等的節(jié)點(diǎn),其估價(jià)函數(shù)取接近于0的值。二.極大極小過程為了計(jì)算非葉節(jié)點(diǎn)的值,必須從葉節(jié)點(diǎn)向上倒推。對于MAX節(jié)點(diǎn),由于MAX方總是選擇估值最大的走步,因此,MAX節(jié)點(diǎn)的倒推值應(yīng)該取其后繼節(jié)點(diǎn)估值的最大值。對于MIN節(jié)點(diǎn),由于MIN方總是選擇使估值最小的走步,因此MIN節(jié)點(diǎn)的倒推值應(yīng)取其后繼節(jié)點(diǎn)估值的最小值。這樣一步一步的計(jì)算倒推值,直至求出初始節(jié)點(diǎn)的倒推值為止。這一過程稱為極大極小過程。39對簡單的博弈問題,可以生成整個(gè)博弈樹,找到必39例:一字棋游戲。設(shè)有一個(gè)三行三列的棋盤,如下圖所示,兩個(gè)棋手輪流走步,每個(gè)棋手走步時(shí)往空格上擺一個(gè)自己的棋子,誰先使自己的棋子成三子一線為贏。設(shè)MAX方的棋子用×標(biāo)記,MIN方的棋子用
○標(biāo)記,并規(guī)定MAX方先走步。
解:為了對葉節(jié)點(diǎn)進(jìn)行靜態(tài)估值,規(guī)定估價(jià)函數(shù)e(P)如下:
若P是MAX的必勝局,則e(P)=+∞;
若P是MIN的必勝局,則e(P)=-∞;一字棋棋盤若P對MAX、MIN都是勝負(fù)未定局,則e(P)=e(+P)-e(-P)
其中,e(+P)表示棋局P上有可能使×成三子一線的數(shù)目;e(-P)表示棋局P上有可能使○成三子一線的數(shù)目。40例:一字棋游戲。設(shè)有一個(gè)三行三列的棋盤,如下圖所示,兩個(gè)棋40例如,對圖1所示的棋局有估價(jià)函數(shù)值e(P)=6-4=2圖1棋局1在搜索過程中,具有對稱性的棋局認(rèn)為是同一棋局。例如,圖2所示的棋局可以認(rèn)為是同一個(gè)棋局,這樣可以大大減少搜索空間。圖3給出了第一著走棋以后生成的博弈樹。圖中葉節(jié)點(diǎn)下面的數(shù)字是該節(jié)點(diǎn)的靜態(tài)估值,非葉節(jié)點(diǎn)旁邊的數(shù)字是計(jì)算出的倒推值。從圖中可以看出,對MAX來說S2是一著最好的走棋,它具有較大的倒推值。圖2對稱棋局的例子41例如,對圖1所示的棋局有估價(jià)函數(shù)值e(P)=6-4=2圖41
圖3一子棋的極大極小搜索S0S1S2S3S4S5-11-26-5=15-5=06-5=15-5=04-5=-15-6=-15-5=06-6=05-6=-14-6=-25-4=16-4=242
圖3一子棋的極大極小搜42極大極小值算法FunctionMAX-MIN-DECISION(state)returnsanaction inputs:state(currentstateingame) v←MAX-VALUE(state) returntheactioninSUCCESSORS(state)withvaluevFunctionMAX-VALUE(state)returnsautilityvalue ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←-∞ fora,sinSUCCESSORS(state)dov←MAX(v,MIN-VALUE(s)) returnv (a=action招數(shù))FunctionMIN-VALUE(state)returnsautilityvalue ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←+∞ fora,sinSUCCESSORS(state)dov←MIN(v,MAX-VALUE(s)) returnv43極大極小值算法FunctionMAX-MIN-DECISI43上述極大極小過程是先生成與/或樹,然后再計(jì)算各節(jié)點(diǎn)的估值,這種生成節(jié)點(diǎn)和計(jì)算估值相分離的搜索方式,需要生成規(guī)定深度內(nèi)的所有節(jié)點(diǎn),因此搜索效率較低。如果能邊生成節(jié)點(diǎn)邊對節(jié)點(diǎn)估值,從而可以剪去一些沒用的分枝,這種技術(shù)稱為α-β剪枝過程。三.α-β剪枝<=23S0DEFABC5332對于一個(gè)與節(jié)點(diǎn)來說,它取當(dāng)前子節(jié)點(diǎn)中的最小倒推值作為它倒推值的上界,稱該值為β值。對于一個(gè)或節(jié)點(diǎn)來說,它取當(dāng)前子節(jié)點(diǎn)中的最大倒推值作為它倒推值的下界,稱該值為α
值。44上述極大極小過程是先生成與/或樹,然后再計(jì)算44α-β剪枝的方法如下:
(1)MAX節(jié)點(diǎn)的α值為當(dāng)前子節(jié)點(diǎn)的最大倒推值;
(2)
MIN節(jié)點(diǎn)的β值為當(dāng)前子節(jié)點(diǎn)的最小倒推值;
(3)
α-β剪枝的規(guī)則如下:
①
任何MAX節(jié)點(diǎn)n的α值大于或等于它先輩節(jié)點(diǎn)的β值,則n以下的分枝可停止搜索,并令節(jié)點(diǎn)n的倒推值為α。這種剪枝稱為β剪枝。
②
任何MIN節(jié)點(diǎn)n的β值小于或等于它先輩節(jié)點(diǎn)的α值,則n以下的分枝可停止搜索,并令節(jié)點(diǎn)n的倒推值為β。這種剪枝稱為α剪枝。
三.α-β剪枝≥αmin≤βmax≥α45α-β剪枝的方法如下:
(1)MAX節(jié)點(diǎn)的α值45S0ABCDFGHEIJKLMNPQRS4861580-64≥4≤1≤4=45≥5=4≥4≥0=0≤-6=0≤0=4*****α-β剪枝的例子T446S0ABCDFGHEIJKLMNPQRS4861580-6446S00-330031653-322-3-254-3089-347S00-330031653-322-3-254-3089-347S00-330031653-322-3-254-3089-3******跳棋程序的學(xué)習(xí)策略48S00-330031653-322-3-254-3089-348-剪枝算法在極大極小值算法基礎(chǔ)上增加了剪枝功能,即在返回值基礎(chǔ)上增加了判斷FunctionALPHA-BETA-SEARCH(state)returnsanaction inputs:state(currentstateingame) v←MAX-VALUE(state,-∞,+∞) returntheactioninSUCCESSORS(state)withvaluev49-剪枝算法在極大極小值算法基礎(chǔ)上增加了剪枝功能,即在返回49-剪枝算法FunctionMAX-VALUE(state,,)returnsautilityvalue inputs:state ,thevalueofthebestalternativeforMAXalongthepathtostate ,thevalueofthebestalternativeforMINalongthepathtostate ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←-∞ fora,sinSUCCESSORS(state)do v←MAX(v,MIN-VALUE(s,,)) ifv≥thenreturnv
←MAX(,v) returnv50-剪枝算法FunctionMAX-VALUE(stat50-剪枝算法FunctionMIN-VALUE(state,,)returnsautilityvalue inputs:state ,thevalueofthebestalternativeforMAXalongthepathtostate thevalueofthebestalternativeforMINalongthepathtostate ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←+∞ fora,sinSUCCESSORS(state)do v←MIN(v,MAX-VALUE(s,
,)) ifv≤thenreturnv
←MIN(,v) returnv51-剪枝算法FunctionMIN-VALUE(stat51產(chǎn)生式系統(tǒng)與圖搜索分析產(chǎn)生式正向推理算法,可以看出,它們只能用于解決邏輯推理性問題。若要求解規(guī)劃性問題則還需要:(1)記錄動態(tài)數(shù)據(jù)庫狀態(tài)變化的歷史,這就需要增設(shè)一個(gè)CLOSED表。(2)若要回溯,則還需保存與每個(gè)動態(tài)數(shù)據(jù)庫狀態(tài)對應(yīng)的可用規(guī)則集。因?yàn)閯討B(tài)數(shù)據(jù)庫狀態(tài)與可用規(guī)則集實(shí)際是一一對應(yīng)的。(3)要進(jìn)行樹式搜索,還需設(shè)置一個(gè)OPEN表,以進(jìn)行新生動態(tài)數(shù)據(jù)庫的狀態(tài)保存和當(dāng)前動態(tài)數(shù)據(jù)庫狀態(tài)的切換。(4)還要考慮一條規(guī)則是否只允許執(zhí)行一次。若是,則要對已執(zhí)行了的規(guī)則進(jìn)行標(biāo)記。成功退出失敗退出把初始數(shù)據(jù)放入綜合數(shù)據(jù)庫綜合數(shù)據(jù)庫中有解嗎?形成可用知識集可用知識集空?按照沖突消解策略從該知識集中選出一條知識進(jìn)行推理推出的是新事實(shí)?將該新事實(shí)加入到綜合數(shù)據(jù)庫中把用戶補(bǔ)充的新事實(shí)加入到綜合數(shù)據(jù)庫中用戶可以補(bǔ)充新事實(shí)嗎?知識庫中有可用知識嗎?YYYYYNNNNN52產(chǎn)生式系統(tǒng)與圖搜索分析產(chǎn)生式正向推理算法,52可以看出,二者實(shí)際是一回事。圖搜索技術(shù)描述了問題求解的方法,產(chǎn)生式系統(tǒng)則給出了實(shí)施這種方法的一種計(jì)算機(jī)程序系統(tǒng)的結(jié)構(gòu)模式。這樣,問題求解、圖搜索和產(chǎn)生式系統(tǒng)三者的關(guān)系是:問題求解是目的,圖搜索是方法,產(chǎn)生式系統(tǒng)是形式。53可以看出,二者實(shí)際是一回事。圖搜索技術(shù)描述了問題求解53前面討論的各種搜索方法都沒有用到問題本身的特性信息,只是按照事先設(shè)定的線路進(jìn)行搜索,具有較大的盲目性。事實(shí)上,如果能夠利用搜索過程所得到的問題自身的一些特性信息來指導(dǎo)搜索過程,則對搜索將是十分有益的。這種利用問題自身的特性信息來引導(dǎo)搜索過程的搜索方法稱為啟發(fā)式搜索。由于啟發(fā)式搜索方法具有較強(qiáng)的針對性,因此,可以縮小搜索范圍,提高搜索效率。4.5狀態(tài)空間的啟發(fā)式搜索54前面討論的各種搜索方法都沒有用到問題本身的特54
啟發(fā)式搜索方法所依據(jù)的是問題自身的啟發(fā)性信息,而啟發(fā)性信息又是通過估價(jià)函數(shù)作用到搜索過程中的。
1.啟發(fā)性信息一.啟發(fā)性信息和估價(jià)函數(shù)
啟發(fā)性信息是指那種與具體問題求解過程有關(guān)的,并可指導(dǎo)搜索過程朝著最有希望方向前進(jìn)的控制信息。啟發(fā)性信息一般有以下三種:
①有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息;
②有效地幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成;
③能決定在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)哪些節(jié)點(diǎn)應(yīng)從搜索樹上被刪除。
一般來說,搜索過程所使用的啟發(fā)性信息的啟發(fā)能力越強(qiáng),擴(kuò)展的無用節(jié)點(diǎn)就越少。55啟發(fā)式搜索方法所依據(jù)的是問題自身的啟發(fā)性信息55
2.估價(jià)函數(shù)用來估計(jì)節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)。估價(jià)函數(shù)f(n)被定義為從初始節(jié)點(diǎn)S0出發(fā),經(jīng)過節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)Sg的所有路徑中最小路徑代價(jià)的估計(jì)值。它的一般形式為
f(n)=g(n)+h(n)
其中,g(n)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的實(shí)際代價(jià);h(n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)S0的最優(yōu)路徑的估計(jì)代價(jià)。對g(n)的值,可以按指向父節(jié)點(diǎn)的指針,從節(jié)點(diǎn)n反向跟蹤到初始節(jié)點(diǎn)S0,得到一條從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的最小代價(jià)路徑,然后把這條路徑上所有有向邊的代價(jià)相加,就得到g(n)的值。對h(n)的值,則需要根據(jù)問題自身的特性來確定,它體現(xiàn)的是問題自身的啟發(fā)性信息,因此也稱h(n)為啟發(fā)函數(shù)。ng(n)h(n)562.估價(jià)函數(shù)用來估計(jì)節(jié)點(diǎn)重要性的函數(shù)稱為估56例:八數(shù)碼難題。設(shè)問題的初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如前所述,且估價(jià)函數(shù)為:f(n)=d(n)+W(n)
其中,d(n)表示節(jié)點(diǎn)n在搜索樹中的深度;w(n)表示節(jié)點(diǎn)n中“不在位”的數(shù)碼個(gè)數(shù)。請計(jì)算初始狀態(tài)S0的估價(jià)函數(shù)值f(S0)。
解:在本例的估價(jià)函數(shù)中,取g(n)=d(n),h(n)=W(n)。它說明是用從S0到n的路徑上的單位代價(jià)表示實(shí)際代價(jià),用n中“不在位”的數(shù)碼個(gè)數(shù)作為啟發(fā)信息。一般來說,某節(jié)點(diǎn)中的“不在位”的數(shù)碼個(gè)數(shù)越多,說明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn)。
對初始節(jié)點(diǎn)S0,由于d(S0)=0,W(S0)=3,因此有
f(S0)=0+3=3
這個(gè)例子僅是為了說明估價(jià)函數(shù)的含義及估價(jià)函數(shù)值的計(jì)算。在問題搜索過程中,除了需要計(jì)算初始節(jié)點(diǎn)的估價(jià)函數(shù)之外,更多的是要計(jì)算新生成節(jié)點(diǎn)的估價(jià)函數(shù)值。
2831476557例:八數(shù)碼難題。設(shè)問題的初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如前57二.A算法
在圖搜索算法中,如果能在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)對Open表中的節(jié)點(diǎn)進(jìn)行排序,則該搜索算法為A算法。由于估價(jià)函數(shù)中帶有問題自身的啟發(fā)性信息,因此,A算法也被稱為啟發(fā)式搜索算法。
對啟發(fā)式搜索算法,又可根據(jù)搜索過程中選擇擴(kuò)展節(jié)點(diǎn)的范圍,將其分為全局擇優(yōu)搜索算法和局部擇優(yōu)搜索算法。58二.A算法在圖搜索算法中,如果能在搜索的58每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí),總是從Open表的所有節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。其搜索過程可描述如下:
(1)把S0放入Open表中,f(s0)=g(So)+h(So);
(2)如果Open表為空,則問題無解,失敗退出;
(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表,記該節(jié)點(diǎn)為n;
(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是,則找到了問題的解,成功退出;
(5)若節(jié)點(diǎn)n不可擴(kuò)展,則轉(zhuǎn)第(2)步;
(6)擴(kuò)展節(jié)點(diǎn)n,生成其子節(jié)點(diǎn)ni(i=1,2,……),計(jì)算每一個(gè)子節(jié)點(diǎn)的估價(jià)值f(ni)(i=1,2,……),并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針,然后將這些子節(jié)點(diǎn)放入Open表中;
(7)根據(jù)各節(jié)點(diǎn)的估價(jià)函數(shù)值,對Open表中的全部節(jié)點(diǎn)按從小到大的順序重新進(jìn)行排序;
(8)轉(zhuǎn)第(2)步。
1.全局擇優(yōu)搜索59每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí),總是從Open表的所有節(jié)點(diǎn)中選擇59由于上述算法的第(7)步要對Open表中的全部節(jié)點(diǎn)按其估價(jià)函數(shù)值從小到大重新進(jìn)行排序,這樣在算法第(3)步取出的節(jié)點(diǎn)就一定是Open表的所有節(jié)點(diǎn)中估價(jià)函數(shù)值最小的一個(gè)節(jié)點(diǎn)。因此,它是一種全局擇優(yōu)的搜索方式。
對上述算法進(jìn)一步分析還可以發(fā)現(xiàn):如果取估價(jià)函數(shù)f(n)=g(n),則它將退化為代價(jià)樹的廣度優(yōu)先搜索;如果取估價(jià)函數(shù)f(n)=d(n),則它將退化為廣度優(yōu)先搜索??梢姡瑥V度優(yōu)先搜索和代價(jià)樹的廣度優(yōu)先搜索是全局擇優(yōu)搜索的兩個(gè)特例。60由于上述算法的第(7)步要對Open表中的全60例:八數(shù)碼難題。2834765S028314765238476528347652836475
8321476528371465
23847652384765
S9
4123847651238476512378465S5
5S66
S8
6
S7
4SgS10
4S11
6S1
4S2
4
S3
5S4
561例:八數(shù)碼難題。283S0283261在局部擇優(yōu)搜索中,每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí),總是從剛生成的子節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。其搜索過程可描述如下:(1)把初始節(jié)點(diǎn)S0放入Open表中,f(S0)=g(S0)+h(S0);(2)如果Open表為空,則問題無解,失敗退出;
(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表,并記該節(jié)點(diǎn)為n;
(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是,則找到了問題的解,成功退出;
(5)若節(jié)點(diǎn)n不可擴(kuò)展,則轉(zhuǎn)第(2)步;
(6)擴(kuò)展節(jié)點(diǎn)n,生成其子節(jié)點(diǎn)ni(i=1,2,…),計(jì)算每一個(gè)子節(jié)點(diǎn)的估價(jià)值f(ni)(i=1,2,…),并按估價(jià)值從小到大的順序依次放入Open表的首部,并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針,然后轉(zhuǎn)第(2)步。
2.局部擇優(yōu)搜索(瞎子爬山法)62在局部擇優(yōu)搜索中,每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí),總是從62
由于這一算法的第(6)步僅是把剛生成的子節(jié)點(diǎn)按其估價(jià)函數(shù)值從小到大放入Open表的首都,這樣在算法第(3)步取出的節(jié)點(diǎn)僅是剛生成的子節(jié)點(diǎn)中估價(jià)函數(shù)值最小的一個(gè)節(jié)點(diǎn)。因此,它是一種局部擇優(yōu)的搜索方式。對這一算法進(jìn)一步分析也可以發(fā)現(xiàn):如果取估價(jià)函數(shù)f(n)=g(n),則它將退化為代價(jià)樹的深度優(yōu)先搜索;如果取估價(jià)函數(shù)f(n)=d(n),則它將退化為深度優(yōu)先搜索??梢姡疃葍?yōu)先搜索和代價(jià)樹的深度優(yōu)先搜索是局部擇優(yōu)搜索的兩個(gè)特例。63由于這一算法的第(6)步僅是把剛生成的子節(jié)點(diǎn)63三.A*算法前面討論的啟發(fā)式搜索算法,都沒有對估價(jià)函數(shù)f(n)作任何限制。實(shí)際上,估價(jià)函數(shù)對搜索過程是十分重要的,如果選擇不當(dāng),則有可能找不到問題的解,或者找到的不是問題的最優(yōu)解。為此,需要對估價(jià)函數(shù)進(jìn)行某些限制。A*算法就是對估價(jià)函數(shù)加上一些限制后得到的一種啟發(fā)式搜索算法。64三.A*算法前面討論的啟發(fā)式搜索算法,都沒64假設(shè)f*(n)為從初始節(jié)點(diǎn)S0出發(fā),約束經(jīng)過節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的最小代價(jià)值。估價(jià)函數(shù)f(n)是f*(n)的估計(jì)值。顯然,f*(n)應(yīng)由以下兩部分所組成:一部分是從初始節(jié)點(diǎn)到節(jié)點(diǎn)n的最小代價(jià),記為g*(n);另一部分是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最小代價(jià),記為h*(n),當(dāng)問題有多個(gè)目標(biāo)節(jié)點(diǎn)時(shí),應(yīng)取其中代價(jià)最小的一個(gè)。因此有
f*(n)=g*(n)+h*(n)
把估價(jià)函數(shù)f(n)與f*(n)相比,g(n)是對g*(n)的一個(gè)估計(jì),h(n)是對h*(n)的一個(gè)估計(jì)。在這兩個(gè)估計(jì)中,盡管g(n)的值容易計(jì)算,但它不一定就是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的真正最小代價(jià),很有可能從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的真正最小代價(jià)還沒有找到,故有g(shù)(n)≥g*(n)。
有了g*(n)和h*(n)的定義,如果對A算法(全局擇優(yōu)的啟發(fā)式搜索算法)中的g(n)和h(n)分別提出如下限制:
第一,g(n)是對g*(n)的估計(jì),且g(n)>0;
第二,h(n)是h*(n)的下界,即對任意節(jié)點(diǎn)n均有
h(n)≤h*(n)。
則稱得到的算法為A*算法。65假設(shè)f*(n)為從初始節(jié)點(diǎn)S0出發(fā),約束經(jīng)過65A*算法的有關(guān)特性。
1.A*算法的可納性
一般來說,對任意一個(gè)狀態(tài)空間圖,當(dāng)從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在時(shí),如果搜索算法能在有限步內(nèi)找到一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑,并在此路徑上結(jié)束,則稱該搜索算法是可采納的。A*算法是可采納的。(證明略)。
2.A*算法的最優(yōu)性
A*算法的搜索效率很大程度上取決于估價(jià)函數(shù)h(n)。一般來說,在滿足h(n)≤h*(n)的前提下,h(n)的值越大越好。h(n)的值越大,說明它攜帶的啟發(fā)性信息越多,A*算法搜索時(shí)擴(kuò)展的節(jié)點(diǎn)就越少,搜索效率就越高。A*算法的這一特性也稱為信息性。(證明略)66A*算法的有關(guān)特性。
1366A*算法應(yīng)用舉例
例:八數(shù)碼難題。問題的初始狀態(tài)和目標(biāo)狀態(tài)和前例相同。要求用A*算法解決該問題。
解:在上例中,我們?nèi)(n)=W(n)。盡管我們對h*(n)不能確切知道,但當(dāng)采用單位代價(jià)時(shí),通過對“不在位”數(shù)碼個(gè)數(shù)的估計(jì),可以得出至少要移動W(n)步才能到達(dá)目標(biāo),顯然有W(n)≤h*(n)。因此,前例中所定義的h(n)滿足A*算法的限制條件。
這里再取另外一種啟發(fā)函數(shù)h(n)=P(n),P(n)定義為每一個(gè)數(shù)碼與其目標(biāo)位置之間距離(不考慮夾在其間的數(shù)碼)的總和,同樣可以斷定至少要移動P(n)步才能到達(dá)目標(biāo),因此有P(n)≤h*(n),即滿足A*算法的限制條件。
23847655238476167A*算法應(yīng)用舉例
例:八數(shù)碼難題。問題的初始狀態(tài)和目標(biāo)狀6728314765h*=4,f=4S0231
8476528316475283
1476528314765g*=1
2318476523184765g*=21
23847651
2378465Sgg*=4h*=5,f=6h*=5,f=6h*=3,f=4h*=5,f=6h*=2,f=4h*=4,f=61
2384765g*=3h*=1,f=4h*=0,f=4h*=1,f=6八數(shù)碼難題h(n)=P(n)的搜索樹68283h*=4,f=4S0232832868例:設(shè)有如下結(jié)構(gòu)的移動將牌游戲B代表黑色牌,W代表白色牌;E代表該位置為空。玩法:當(dāng)一個(gè)牌移入相鄰的空位時(shí),費(fèi)用等于挑過的牌數(shù)加1。一個(gè)牌至多可跳過兩個(gè)牌進(jìn)入空位置,其費(fèi)用等于跳過的牌數(shù)加1。要求把所有的B都移到所有的W的右邊,設(shè)計(jì)h(x)。解:顯然W左邊的B越少越接近目標(biāo),因此可用W左邊B的個(gè)數(shù)作為h(x)h(x)=3*(每個(gè)W左邊B個(gè)數(shù)的總和)h(x)=3*(2+2+3)=21BBBWWWEBBBWWWE69例:設(shè)有如下結(jié)構(gòu)的移動將牌游戲BBBWWWEBBBWWWE169例:傳教士和野人問題。請用A*算法解決該問題。
解:用m表示左岸的傳道士人數(shù),c表示左岸的野人數(shù),b表示左岸的船數(shù),用三元組(m,c,b)表示問題的狀態(tài)。
對A*算法,首先需要確定估價(jià)函數(shù)。
設(shè)g(n)=d(n),h(n)=m+c-2b,
則有
f(n)=g(n)+h(n)=d(n)+m+c-2b
其中,d(n)為節(jié)點(diǎn)的深度。通過分析可知h(n)<h*(n),滿足A*算法的限制條件。
M-C問題的搜索過程如下頁圖所示。在該圖中,每個(gè)節(jié)點(diǎn)旁邊還標(biāo)出了該節(jié)點(diǎn)的h值和f值。70例:傳教士和野人問題。請用A*算法解決該問題。
解:用m表示70(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=4,f=4f(n)=d(n)+m+c-2bhh=5,f=6h=4,f=5h=4,f=5(3,2,1)h=3,f=5(2,1,0)(3,0,0)h=3,f=6h=3,f=6(2,2,1)(3,1,1)h=2,f=6h=2,f=6h=2,f=7h=2,f=7傳教士和野人問題的搜索圖(0,0,0)(0,3,1)h=1,f=7(0,1,0)h=1,f=8(0,2,1)h=0,f=8(0,2,0)(1,1,0)71(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=717219724.4與/或樹的盲目搜索734.4與/或樹的盲目搜索2073概念:直接可解的簡單問題稱為本原問題,本原問題對應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn),在與或圖(樹)中無子節(jié)點(diǎn)的節(jié)點(diǎn)稱為端節(jié)點(diǎn),一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)如果是“與”關(guān)系,則該節(jié)點(diǎn)便稱為與節(jié)點(diǎn),一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)如果是“或”關(guān)系,則該節(jié)點(diǎn)便稱為或節(jié)點(diǎn)。注意,終止節(jié)點(diǎn)一定是端節(jié)點(diǎn),但端節(jié)點(diǎn)不一定是終止節(jié)點(diǎn)??山庑耘袆e(1)一個(gè)節(jié)點(diǎn)是可解,則節(jié)點(diǎn)須滿足下列條件之一:①終止節(jié)點(diǎn)是可解節(jié)點(diǎn);②一個(gè)與節(jié)點(diǎn)可解,當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全都可解;③一個(gè)或節(jié)點(diǎn)可解,只要其子節(jié)點(diǎn)至少有一個(gè)可解。(2)一個(gè)節(jié)點(diǎn)是不可解,則節(jié)點(diǎn)須滿足下列條件之一:①非終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn);②一個(gè)與節(jié)點(diǎn)不可解,只要其子節(jié)點(diǎn)至少有一個(gè)不可解;③一個(gè)或節(jié)點(diǎn)不可解,當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全都不可解。74概念:2174一.與/或樹的一般搜索與/或樹的搜索過程實(shí)際上是一個(gè)不斷尋找解樹的過程。其一般搜索過程如下:
(1)把原始問題作為初始節(jié)點(diǎn)S0,并把它作為當(dāng)前節(jié)點(diǎn);
(2)應(yīng)用分解或等價(jià)變換操作對當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展;
(3)為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針;
(4)選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn),反復(fù)執(zhí)行第(2)步和第(3)步,在此期間需要多次調(diào)用可解標(biāo)記過程或不可解標(biāo)記過程,直到初始節(jié)點(diǎn)被標(biāo)記為可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)為止。
上述搜索過程將形成一棵與/或樹,這種由搜索過程形成的與/或樹稱為搜索樹。當(dāng)搜索成功時(shí),經(jīng)可解標(biāo)記過程標(biāo)識的由初始節(jié)點(diǎn)及其下屬的可解節(jié)點(diǎn)構(gòu)成的子樹稱為解樹。用與/或樹法表示的問題求解過程與狀態(tài)空間法類似,也是通過搜索來實(shí)現(xiàn)對問題求解的。與/或樹的搜索策略也分為盲目搜索和啟發(fā)式搜索兩大類。75一.與/或樹的一般搜索與/或樹的搜索過程實(shí)75搜索過程中的可解標(biāo)記過程與不可解標(biāo)記過程都是自下而上進(jìn)行的,即由子節(jié)點(diǎn)的可解性確定父節(jié)點(diǎn)、祖父節(jié)點(diǎn)的可解性;由子節(jié)點(diǎn)的不可解性確定父節(jié)點(diǎn)、祖父節(jié)點(diǎn)的不可解性。在與/或樹中,除端節(jié)點(diǎn)和終止節(jié)點(diǎn)外,一個(gè)節(jié)點(diǎn)的可解性完全是由其子節(jié)點(diǎn)來決定的。對與節(jié)點(diǎn),只有其所有子節(jié)點(diǎn)都為可解時(shí)它才為可解,只要有一個(gè)子節(jié)點(diǎn)不可解它就是不可解的;對或節(jié)點(diǎn),只要有一個(gè)子節(jié)點(diǎn)可解它就是可解的,僅當(dāng)所有子節(jié)點(diǎn)都是不可解時(shí)它才為不可解。這種由可解子節(jié)點(diǎn)來確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)為可解節(jié)點(diǎn)的過程稱為可解標(biāo)記過程;由不可解子節(jié)點(diǎn)來確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)為不可解節(jié)點(diǎn)的過程稱為不可解標(biāo)記過程。
由于與/或樹搜索的目標(biāo)是尋找解樹,因此,如果搜索過程確定某個(gè)節(jié)點(diǎn)為可解節(jié)點(diǎn),則其不可解的后裔節(jié)點(diǎn)就可從搜索樹中刪去;同樣,如果搜索過程能確定某個(gè)節(jié)點(diǎn)為不可解節(jié)點(diǎn),則其后裔節(jié)點(diǎn)也可從搜索樹中刪去。76搜索過程中的可解標(biāo)記過程與不可解標(biāo)記過程都是自下而上進(jìn)行的,76與狀態(tài)空間的廣度優(yōu)先搜索類似,只是在搜索過程中需要多次調(diào)用可解標(biāo)記過程或不可解標(biāo)記過程,其搜索算法如下:
(1)把初始節(jié)點(diǎn)S0放人Open表中;
(2)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表,并記該節(jié)點(diǎn)為n;
(3)如果節(jié)點(diǎn)n可擴(kuò)展,則做下列工作:
①擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)放入Open表的尾部,并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針;
②考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。若有,則標(biāo)記這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn),并用可解標(biāo)記過程對其父節(jié)點(diǎn)及先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始解節(jié)點(diǎn)S0能夠被標(biāo)記為可解節(jié)點(diǎn),就得到了解樹,搜索成功,退出搜索過程;如果不能確定S0為可解節(jié)點(diǎn),則從Open表中刪去具有可解先輩的節(jié)點(diǎn);
③
轉(zhuǎn)第(2)步。二.與/或樹的廣度優(yōu)先搜索77與狀態(tài)空間的廣度優(yōu)先搜索類似,只是在搜索過程77(4)如果節(jié)點(diǎn)n不可擴(kuò)展,則做下列工作:
①
標(biāo)記節(jié)點(diǎn)n為不可解節(jié)點(diǎn);
②
應(yīng)用不可解標(biāo)記過程對節(jié)點(diǎn)n的先輩中不可解的節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始解節(jié)點(diǎn)S0也被標(biāo)記為不可解節(jié)點(diǎn),則搜索失敗,表明原始問題無解,退出搜索過程;如果不能確定S0為不可解節(jié)點(diǎn),則從Open表中刪去具有不可解先輩的節(jié)點(diǎn);
③轉(zhuǎn)第(2)步。78(4)如果節(jié)點(diǎn)n不可擴(kuò)展,則做下列工作:
78例:設(shè)有如下圖所示的與/或樹,節(jié)點(diǎn)按圖中所標(biāo)注的順序號進(jìn)行擴(kuò)展,其中標(biāo)有t1、t2、t3的節(jié)點(diǎn)是終止節(jié)點(diǎn),A、B、C為不可解的端節(jié)點(diǎn)。
與/或樹的廣度優(yōu)先搜索123A4t1t3CBt25搜索過程為:
(1)先擴(kuò)展1號節(jié)點(diǎn),生成2號節(jié)點(diǎn)和3號節(jié)點(diǎn),由于這兩個(gè)子節(jié)點(diǎn)都不是終止節(jié)點(diǎn),因此接著擴(kuò)展2號節(jié)點(diǎn)。(2)擴(kuò)展2號節(jié)點(diǎn),生成A節(jié)點(diǎn)和4號節(jié)點(diǎn)。由于這兩個(gè)子節(jié)點(diǎn)均不是終止節(jié)點(diǎn),因此接著擴(kuò)展3號節(jié)點(diǎn)。(3)擴(kuò)展3
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024-2030年中國風(fēng)險(xiǎn)投資行業(yè)競爭狀況與發(fā)展模式分析報(bào)告
- 2024-2030年中國風(fēng)電葉片環(huán)氧樹脂行業(yè)發(fā)展方向及應(yīng)用潛力預(yù)測研究報(bào)告
- 2024-2030年中國預(yù)粉碎機(jī)行業(yè)市場發(fā)展趨勢與前景展望戰(zhàn)略研究報(bào)告
- 2024-2030年中國靜壓滅菌器市場現(xiàn)狀調(diào)研及銷售投資運(yùn)作模式分析研究報(bào)告
- 2024-2030年中國防霧霾口罩行業(yè)市場運(yùn)行分析及投資價(jià)值評估報(bào)告
- 2024-2030年中國防腐漆行業(yè)發(fā)展分析及競爭策略與趨勢預(yù)測研究報(bào)告
- 2024-2030年中國防溺水系統(tǒng)行業(yè)發(fā)展形勢及投資動態(tài)預(yù)測報(bào)告
- 2024年中國涂塑吊花籃市場調(diào)查研究報(bào)告
- 保密協(xié)議商業(yè)合同的翻譯與解讀
- 在建住宅樓購買合同
- 如何提高小學(xué)語文課堂教學(xué)效率小學(xué)語文教師教學(xué)經(jīng)驗(yàn)交流PPT圖文課件
- 《人因工程學(xué)課程設(shè)計(jì)》教學(xué)大綱
- 教科版五上第二單元《地球表面的變化》教學(xué)課件
- 人教版五年級數(shù)學(xué)上冊第三單元-解決問題例10課件
- 五年級上冊英語素材-基礎(chǔ)梳理資料 川教版
- 分布式光伏電站外來人員安全責(zé)任書
- 血常規(guī)化驗(yàn)單的解讀ppt參考課件
- 對數(shù)的概念(公開課)公開課一等獎(jiǎng)省優(yōu)質(zhì)課大賽獲獎(jiǎng)?wù)n件
- 大班科學(xué)活動磁鐵的秘密
- 畢業(yè)設(shè)計(jì)-汽車車速傳感器檢測系統(tǒng)設(shè)計(jì)
- 浙教版小學(xué)三年級上冊數(shù)學(xué)期末整理復(fù)習(xí)假期練習(xí)題單
評論
0/150
提交評論