人工智能第五章 問題求解基本原理

1、2.2 盲目搜索策略解解1 1：A A、B B都搬到都搬到3 3上：上：A(1,2) B(1,3) A(2,3) 解解2 2：A A、B B都搬到都搬到2 2上：上：A(1,3)B(1,2)A(3,2)例如，把問題例如，把問題P分解為三個(gè)子問題分解為三個(gè)子問題P1，P2，P3，可用圖表示。如圖：可用圖表示。如圖：P1，P2，P3是問題是問題P的三個(gè)的三個(gè)子問題，只有當(dāng)這三個(gè)子問題都可解時(shí)，問題子問題，只有當(dāng)這三個(gè)子問題都可解時(shí)，問題P才才可解，稱可解，稱P1，P2，P3之間存在之間存在“與與”關(guān)系關(guān)系；稱節(jié)；稱節(jié)點(diǎn)點(diǎn)P為為“與與”節(jié)點(diǎn)節(jié)點(diǎn)；由；由P，P1，P2，P3所構(gòu)成的圖所構(gòu)成的圖稱為稱為

2、“與與”樹樹。在圖中，為了標(biāo)明某個(gè)節(jié)點(diǎn)是。在圖中，為了標(biāo)明某個(gè)節(jié)點(diǎn)是“與與”節(jié)點(diǎn)，通常節(jié)點(diǎn)，通常用一條弧把各條邊連接起來用一條弧把各條邊連接起來。例如，問題例如，問題P P被等價(jià)變換為新問題被等價(jià)變換為新問題P1P1，P2P2，P3P3。如。如左圖所示。其中，新問題左圖所示。其中，新問題P1P1，P2P2，P3P3中只要有一個(gè)中只要有一個(gè)可解，則原問題就可解，稱可解，則原問題就可解，稱P1,P2P1,P2，P3P3之間存在之間存在“或或”關(guān)系關(guān)系；節(jié)點(diǎn)；節(jié)點(diǎn)P P稱為稱為“或或”節(jié)點(diǎn)節(jié)點(diǎn)；由；由P P，P1P1，P2P2，P3P3所構(gòu)成的圖是一個(gè)所構(gòu)成的圖是一個(gè)“或或”樹樹。上述兩種方法也可。

3、上述兩種方法也可結(jié)合起來使用，此時(shí)的圖稱為結(jié)合起來使用，此時(shí)的圖稱為“與或與或”樹。其中樹。其中既有既有“與與”節(jié)點(diǎn)，也有節(jié)點(diǎn)，也有“或或”節(jié)點(diǎn)。如右圖所示。節(jié)點(diǎn)。如右圖所示。3 3、基本概念：、基本概念：A A、本原問題本原問題：不能再分解或變換，而且直接可解的子問題稱：不能再分解或變換，而且直接可解的子問題稱為本原問題。為本原問題。B B、端節(jié)點(diǎ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)；本原問題所對(duì)應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn)。顯然，終為端節(jié)點(diǎn)；本原問題所對(duì)應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn)。顯然，終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)不一定是終止節(jié)點(diǎn)。止節(jié)點(diǎn)一

4、定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)不一定是終止節(jié)點(diǎn)。C C、可解節(jié)點(diǎn)可解節(jié)點(diǎn)：在與或樹中，滿足下列條件之一者，稱為可：在與或樹中，滿足下列條件之一者，稱為可解節(jié)點(diǎn)：解節(jié)點(diǎn)：(1(1）它是一個(gè)終止節(jié)點(diǎn)。）它是一個(gè)終止節(jié)點(diǎn)。(2(2）它是一個(gè)）它是一個(gè)“或或”節(jié)點(diǎn)，節(jié)點(diǎn)，且其子節(jié)點(diǎn)中至少有一個(gè)是可解節(jié)點(diǎn)。且其子節(jié)點(diǎn)中至少有一個(gè)是可解節(jié)點(diǎn)。(3(3）它是一個(gè)）它是一個(gè)“與與”節(jié)點(diǎn)，且其子節(jié)點(diǎn)全部是可解節(jié)點(diǎn)。節(jié)點(diǎn)，且其子節(jié)點(diǎn)全部是可解節(jié)點(diǎn)。D D、不可解節(jié)點(diǎn)不可解節(jié)點(diǎn)：關(guān)于可解節(jié)點(diǎn)的三個(gè)條件全部不滿足：關(guān)于可解節(jié)點(diǎn)的三個(gè)條件全部不滿足的節(jié)點(diǎn)稱為不可解節(jié)點(diǎn)。的節(jié)點(diǎn)稱為不可解節(jié)點(diǎn)。E E、解樹解樹：由可解節(jié)點(diǎn)所構(gòu)成，并

5、且由這些可解節(jié)點(diǎn)可：由可解節(jié)點(diǎn)所構(gòu)成，并且由這些可解節(jié)點(diǎn)可推出初始節(jié)點(diǎn)（原始問題）為可解節(jié)點(diǎn)的子樹稱為解樹。推出初始節(jié)點(diǎn)（原始問題）為可解節(jié)點(diǎn)的子樹稱為解樹。在解樹中一定包含初始節(jié)點(diǎn)。在解樹中一定包含初始節(jié)點(diǎn)。例如，圖例如，圖(a)(a)的解樹如圖的解樹如圖(b)(b)所示。所示。在圖中，節(jié)點(diǎn)在圖中，節(jié)點(diǎn)p p為原始問題節(jié)點(diǎn)，用為原始問題節(jié)點(diǎn)，用t t標(biāo)出的節(jié)點(diǎn)是終止節(jié)點(diǎn)。標(biāo)出的節(jié)點(diǎn)是終止節(jié)點(diǎn)。根據(jù)可解節(jié)點(diǎn)的定義，很容易推出原始問題根據(jù)可解節(jié)點(diǎn)的定義，很容易推出原始問題p p是可解的。是可解的。S(3,3,1) S(3,3,3)2.3 狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略例例1：實(shí)心黑點(diǎn)代表已

6、擴(kuò)展了的節(jié)點(diǎn)，它們位于：實(shí)心黑點(diǎn)代表已擴(kuò)展了的節(jié)點(diǎn)，它們位于CLOSED表上；空心圓圈代表未擴(kuò)展的節(jié)點(diǎn)，它們表上；空心圓圈代表未擴(kuò)展的節(jié)點(diǎn)，它們位于位于 OPEN 表上；有向邊旁的箭頭是指向父節(jié)點(diǎn)表上；有向邊旁的箭頭是指向父節(jié)點(diǎn)的指針。每邊代價(jià)為的指針。每邊代價(jià)為1。例：重排九宮問題。在例：重排九宮問題。在3 33 3的方格棋盤上放置分的方格棋盤上放置分別標(biāo)有數(shù)字別標(biāo)有數(shù)字1,2,3,4,5,6,7,81,2,3,4,5,6,7,8的八張牌，初始狀的八張牌，初始狀態(tài)為態(tài)為S0S0，目標(biāo)狀態(tài)為，目標(biāo)狀態(tài)為SgSg，如圖所示?？墒褂玫模鐖D所示?？墒褂玫乃惴校嚎崭褡笠?，空格上移，空格右移，空算符

7、有：空格左移，空格上移，空格右移，空格下移。即，它們只允許把位于空格左，上，格下移。即，它們只允許把位于空格左，上，右，下邊的牌移入空格。要求尋找從初始狀態(tài)右，下邊的牌移入空格。要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑。到目標(biāo)狀態(tài)的路徑。例例3 3：重排九宮問題進(jìn)行深度：重排九宮問題進(jìn)行深度優(yōu)先搜索。優(yōu)先搜索。（圖中只是搜索樹的一部分，（圖中只是搜索樹的一部分，尚未到達(dá)目標(biāo)節(jié)點(diǎn)，仍可繼尚未到達(dá)目標(biāo)節(jié)點(diǎn)，仍可繼續(xù)往下搜索。）續(xù)往下搜索。）為找到最優(yōu)解，可增設(shè)一個(gè)表（R)，每找到一個(gè)目標(biāo)節(jié)點(diǎn)后，就把它放入到R的前面，并令dm等于該目標(biāo)節(jié)點(diǎn)所對(duì)應(yīng)的路徑長(zhǎng)度，然后繼續(xù)搜索。由于后求得的解的路徑長(zhǎng)度不會(huì)超過先

8、求得的解的路徑長(zhǎng)度，所以最后求得的解一定是最優(yōu)解。S0S1S2S3S4S5舉例：假設(shè)S3和S5是目標(biāo)節(jié)點(diǎn) 找到S3 Dm=3， R表：S3 繼續(xù)搜索 找到S5 Dm=2， R表：S5 S3 最后解為S5。例例4 4：設(shè)深度界度：設(shè)深度界度dm=4dm=4，用有界深度優(yōu)先，用有界深度優(yōu)先搜索方法求解重排九宮問題。）搜索方法求解重排九宮問題。）例例1 1：如圖：如圖1 1為五城市間的交通路線圖，為五城市間的交通路線圖，A A城城市是出發(fā)地，市是出發(fā)地，E E城市是目的地，兩城市間的城市是目的地，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示。求從交通費(fèi)用（代價(jià)）如圖中數(shù)字所示。求從A A到到E E的最小

9、費(fèi)用交通路線。的最小費(fèi)用交通路線。例例: :設(shè)有如圖所示的與或樹。其中標(biāo)設(shè)有如圖所示的與或樹。其中標(biāo)有有t1t1，t2t2，t3t3，t4t4的節(jié)點(diǎn)均為終止節(jié)的節(jié)點(diǎn)均為終止節(jié)點(diǎn)，點(diǎn)，A A和和B B為不可解的端節(jié)點(diǎn)。為不可解的端節(jié)點(diǎn)。例例1 1：其中標(biāo)有：其中標(biāo)有t1t1，t2t2，t3t3，t4t4的節(jié)點(diǎn)均為終止節(jié)點(diǎn)，的節(jié)點(diǎn)均為終止節(jié)點(diǎn)，A A和和B B為不可解的端節(jié)點(diǎn)。規(guī)定深度為為不可解的端節(jié)點(diǎn)。規(guī)定深度為4 4，對(duì)下述與，對(duì)下述與/ /或樹進(jìn)行有界搜索為：或樹進(jìn)行有界搜索為：(l(l）首先擴(kuò)展）首先擴(kuò)展1 1號(hào)節(jié)點(diǎn)，此時(shí)號(hào)節(jié)點(diǎn)，此時(shí)OPENOPEN（3,23,2）。）。(2(2）擴(kuò)展）擴(kuò)

10、展3 3號(hào)節(jié)點(diǎn)后，得到號(hào)節(jié)點(diǎn)后，得到5 5號(hào)節(jié)點(diǎn)和號(hào)節(jié)點(diǎn)和B B節(jié)點(diǎn)。此時(shí)節(jié)點(diǎn)。此時(shí)OPENOPEN（B,5,2B,5,2）。）。(3)(3)擴(kuò)展擴(kuò)展B B，B B為不可解節(jié)點(diǎn)，用不可解標(biāo)識(shí)過程標(biāo)識(shí)為不可解節(jié)點(diǎn)，用不可解標(biāo)識(shí)過程標(biāo)識(shí)它的先輩節(jié)點(diǎn)。不能確定任何先輩為不可解。它的先輩節(jié)點(diǎn)。不能確定任何先輩為不可解。(4(4）擴(kuò)展）擴(kuò)展5 5號(hào)節(jié)點(diǎn)得到號(hào)節(jié)點(diǎn)得到t4t4節(jié)點(diǎn)與節(jié)點(diǎn)與t3t3節(jié)點(diǎn)，此時(shí)節(jié)點(diǎn)，此時(shí)OPENOPEN（t4,t3,2t4,t3,2）。）。t4t4節(jié)點(diǎn)與節(jié)點(diǎn)與t3t3節(jié)點(diǎn)可解，標(biāo)識(shí)節(jié)點(diǎn)可解，標(biāo)識(shí)5 5可解，可解，3 3可解，可解，1 1不確定。將不確定。將3 3的后輩都刪去。的后輩都刪去。(5(5）擴(kuò)展）擴(kuò)展2 2號(hào)節(jié)點(diǎn)，號(hào)節(jié)點(diǎn)，OPENOPEN（t1,4t1,4）, t1, t1可解，可解，2 2不確定。不確定。(6(6）擴(kuò)展）擴(kuò)展4 4號(hào)節(jié)點(diǎn)，號(hào)節(jié)點(diǎn)，OP