問題求解的基本原理

問題求解的基本原理第1頁，共79頁，2023年，2月20日，星期三2.1概述人工智能解決問題的過程可以抽象為一個問題的求解過程。問題求解就是通過在某個可能的解空間內(nèi)搜索，在有限的步長內(nèi)尋找到一個能解決某類問題的解。第2頁，共79頁，2023年，2月20日，星期三什么是搜索1、搜索引起：人工智能所要解決的問題大部分是結(jié)構(gòu)不良或非結(jié)構(gòu)化的問題，對這樣的問題一般不存在成熟的求解算法可供利用，而只能是利用已有的知識一步步地摸索著前進(jìn)。在此過程中，存在著如何尋找可用知識的問題，即如何確定推理路線，使其付出的代價盡可能的少，而問題又能得到較好的解決。2、搜索：根據(jù)問題的實際情況不斷尋找可利用的知識，從而構(gòu)造一條代價較少的推理路線，使問題得到圓滿解決的過程稱為搜索。第3頁，共79頁，2023年，2月20日，星期三求解問題的步驟

目標(biāo)的表示搜索（工作過程的動作表示）執(zhí)行（執(zhí)行動作）問題的形式化的定義（問題的表示）初始狀態(tài)集合：所處的環(huán)境。操作符集合：把一個問題從一個狀態(tài)變換為另一個狀態(tài)的動作集合。目標(biāo)測試函數(shù)：確定一個狀態(tài)是否是目標(biāo)。路徑費(fèi)用函數(shù)例子：書33的8數(shù)碼游戲第4頁，共79頁，2023年，2月20日，星期三搜索分類：分為盲目搜索和啟發(fā)式搜索。A、盲目搜索：是按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中獲得的中間信息不用來改進(jìn)控制策略。由于搜索總是按預(yù)先規(guī)定的路線進(jìn)行，沒有考慮到問題本身的特性，所以這種搜索具有盲目性，效率不高，不便于復(fù)雜問題的求解。B、啟發(fā)式搜索：是在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過程并找到最優(yōu)解。（顯然，啟發(fā)式搜索優(yōu)于盲目搜索。但由于啟發(fā)式搜索需要具有與問題本身特性有關(guān)的信息，而這并非對每一類問題都可方便地抽取出來，因此盲目搜索仍不失為一種應(yīng)用較多的搜索策略。）第5頁，共79頁，2023年，2月20日，星期三問題求解的性能完備性：是否能找到解最優(yōu)性：找到最優(yōu)解時間復(fù)雜度：找到一個解花費(fèi)時間空間復(fù)雜度：需多少存儲空間第6頁，共79頁，2023年，2月20日，星期三1、狀態(tài)空間表示法狀態(tài)空間表示法是人工智能中最基本的形式化方法，也是討論問題求解技術(shù)的基礎(chǔ)。狀態(tài)空間表示法是用“狀態(tài)”和“算符”來表示問題的一種方法。2.2盲目搜索策略第7頁，共79頁，2023年，2月20日，星期三1、狀態(tài)：狀態(tài)是描述問題求解過程中任一時刻狀況的數(shù)據(jù)結(jié)構(gòu)，一般用一組變量的有序組合表示：SK=（SK0,SK1，…）當(dāng)給每一個分量以確定的值時，就得到了一個具體的狀態(tài)。2、算符：算符引起狀態(tài)中某些分量發(fā)生變化，從而使問題由一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作稱為算符。當(dāng)?shù)竭_(dá)目標(biāo)狀態(tài)時，由初始狀態(tài)到目標(biāo)狀態(tài)所用算符的序列就是問題的一個解。第8頁，共79頁，2023年，2月20日，星期三3、狀態(tài)空間：由問題的全部狀態(tài)及一切可用算符所構(gòu)成的集合稱為問題的狀態(tài)空間。狀態(tài)空間是一個四元組：（S，O，S0，G），其中S為狀態(tài)集合，O為算符集合，S0為初始狀態(tài)集合，G為目標(biāo)狀態(tài)集合。4、狀態(tài)空間的圖示形式稱為狀態(tài)空間圖。其中，節(jié)點表示狀態(tài)；有向邊（?。┍硎舅惴?。第9頁，共79頁，2023年，2月20日，星期三例1

二階梵塔問題。設(shè)有1、2、3三根鋼針，在1號鋼針上穿有A、B兩個金片，A小于B，A位于B的上面。要求把這兩個金片全部移到另一根鋼針上，而且規(guī)定每次只能移動一片，任何時刻都不能使B位于A的上面。第10頁，共79頁，2023年，2月20日，星期三第11頁，共79頁，2023年，2月20日，星期三第12頁，共79頁，2023年，2月20日，星期三解1：A、B都搬到3上：A(1,2)B(1,3)A(2,3)第13頁，共79頁，2023年，2月20日，星期三解2：A、B都搬到2上：A(1,3)B(1,2)A(3,2)第14頁，共79頁，2023年，2月20日，星期三6、狀態(tài)空間方法求解問題特點：（a）用狀態(tài)空間方法表示問題時，首先必須定義狀態(tài)的描述形式，通過使用這種描述形式可把問題的一切狀態(tài)都表示出來。其次，還要定義一組算符，通過使用算符可把問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。（b）問題的求解過程是一個不斷把算符作用于狀態(tài)的過程。5、狀態(tài)空間圖搜索求解步驟（書37）第15頁，共79頁，2023年，2月20日，星期三（c）算符的一次使用，就使問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)?？赡苡卸鄠€算符序列都可使問題從初始狀態(tài)變到目標(biāo)狀態(tài)，這就得到了多個解。（d）對任何一個狀態(tài)，可使用的算符可能不止一個，這樣由一個狀態(tài)所生成的后繼狀態(tài)就可能有多個。當(dāng)對這些后繼狀態(tài)使用算符生成更進(jìn)一步的狀態(tài)時，首先應(yīng)對哪一個狀態(tài)進(jìn)行操作呢？這取決于搜索策略，不同搜索策略的操作順序是不相同的，這正是本章要討論的問題。第16頁，共79頁，2023年，2月20日，星期三2、與／或樹表示法（與／或樹是用于表示問題及其求解過程的又一種形式化方法，通常用于表示比較復(fù)雜問題的求解）。對于一個復(fù)雜問題，直接求解往往比較困難。此時，可通過下述方法進(jìn)行簡化：1、分解：把一個復(fù)雜問題分解為若干個較為簡單的子問題，每個子問題又可繼續(xù)分解為若干個更為簡單的子問題，重復(fù)此過程，直到不需要再分解或者不能再分解為止。然后對每個子問題分別進(jìn)行求解，最后把各子問題的解復(fù)合起來就得到了原問題的解。問題的這一分解過程可用一個圖表示出來。第17頁，共79頁，2023年，2月20日，星期三例如，把問題P分解為三個子問題P1，P2，P3，可用圖表示。如圖：P1，P2，P3是問題P的三個子問題，只有當(dāng)這三個子問題都可解時，問題P才可解，稱P1，P2，P3之間存在“與”關(guān)系；稱節(jié)點P為“與”節(jié)點；由P，P1，P2，P3所構(gòu)成的圖稱為“與”樹。在圖中，為了標(biāo)明某個節(jié)點是“與”節(jié)點，通常用一條弧把各條邊連接起來。第18頁，共79頁，2023年，2月20日，星期三2、等價變換：對于一個復(fù)雜問題，除了可用“分解”方法進(jìn)行求解外，還可利用同構(gòu)或同態(tài)的等價變換，把它變換為若干個較容易求解的新問題。若新問題中有一個可求解，則就得到了原問題的解。問題的等價變換過程，也可用一個圖表示出來，稱為“或”樹。第19頁，共79頁，2023年，2月20日，星期三例如，問題P被等價變換為新問題P1，P2，P3。如左圖所示。其中，新問題P1，P2，P3中只要有一個可解，則原問題就可解，稱P1,P2，P3之間存在“或”關(guān)系；節(jié)點P稱為“或”節(jié)點；由P，P1，P2，P3所構(gòu)成的圖是一個“或”樹。上述兩種方法也可結(jié)合起來使用，此時的圖稱為“與／或”樹。其中既有“與”節(jié)點，也有“或”節(jié)點。如右圖所示。第20頁，共79頁，2023年，2月20日，星期三3、基本概念：A、本原問題：不能再分解或變換，而且直接可解的子問題稱為本原問題。B、端節(jié)點與終止節(jié)點：在與／或樹中，沒有子節(jié)點的節(jié)點稱為端節(jié)點；本原問題所對應(yīng)的節(jié)點稱為終止節(jié)點。顯然，終止節(jié)點一定是端節(jié)點，但端節(jié)點不一定是終止節(jié)點。C、可解節(jié)點：在與／或樹中，滿足下列條件之一者，稱為可解節(jié)點：(1）它是一個終止節(jié)點。(2）它是一個“或”節(jié)點，且其子節(jié)點中至少有一個是可解節(jié)點。(3）它是一個“與”節(jié)點，且其子節(jié)點全部是可解節(jié)點。第21頁，共79頁，2023年，2月20日，星期三D、不可解節(jié)點：關(guān)于可解節(jié)點的三個條件全部不滿足的節(jié)點稱為不可解節(jié)點。E、解樹：由可解節(jié)點所構(gòu)成，并且由這些可解節(jié)點可推出初始節(jié)點（原始問題）為可解節(jié)點的子樹稱為解樹。在解樹中一定包含初始節(jié)點。第22頁，共79頁，2023年，2月20日，星期三例如，圖(a)的解樹如圖(b)所示。在圖中，節(jié)點p為原始問題節(jié)點，用t標(biāo)出的節(jié)點是終止節(jié)點。根據(jù)可解節(jié)點的定義，很容易推出原始問題p是可解的。第23頁，共79頁，2023年，2月20日，星期三第24頁，共79頁，2023年，2月20日，星期三第25頁，共79頁，2023年，2月20日，星期三第26頁，共79頁，2023年，2月20日，星期三第27頁，共79頁，2023年，2月20日，星期三第28頁，共79頁，2023年，2月20日，星期三S(3,3,1)S(3,3,3)第29頁，共79頁，2023年，2月20日，星期三2.3狀態(tài)空間的搜索策略第30頁，共79頁，2023年，2月20日，星期三一、狀態(tài)空間的一般搜索過程

一個復(fù)雜問題的狀態(tài)空間一般都是十分寵大的。若把它們都存儲到計算機(jī)中去，需占用巨大的存儲空間。另一方面，對一個確定的具體問題來說，與解題有關(guān)的狀態(tài)空間往往只是整個狀態(tài)空間的一部分，因此只要能生成并存儲這部分狀態(tài)空間就可求得問題的解。對一個具體問題，如何生成它所需要的部分狀態(tài)空間從而實現(xiàn)對問題的求解呢？第31頁，共79頁，2023年，2月20日，星期三1、基本思想：A、把問題的初始狀態(tài)（即初始節(jié)點）作為當(dāng)前狀態(tài)；B、選擇適用的算符對其進(jìn)行操作，生成一組子狀態(tài)（或稱后繼狀態(tài)、后繼節(jié)點、子節(jié)點）；C、然后檢查目標(biāo)狀態(tài)是否在其中出現(xiàn)。若出現(xiàn)，則搜索成功，找到了問題的解；若不出現(xiàn)，則按某種搜索策略從已生成的狀態(tài)中再選一個狀態(tài)作為當(dāng)前狀態(tài)；D、重復(fù)B、C，直到目標(biāo)狀態(tài)出現(xiàn)或者不再有可供操作的狀態(tài)及算符時為止。第32頁，共79頁，2023年，2月20日，星期三2、狀態(tài)空間的一般搜索過程：OPEN表：用于存放剛生成的節(jié)點。對于不同的搜索策略，節(jié)點在OPEN表中的排列順序是不同的。CLOSED表：用于存放將要擴(kuò)展或者已擴(kuò)展的節(jié)點。所謂對一個節(jié)點進(jìn)行“擴(kuò)展”是指：用合適的算符對該節(jié)點進(jìn)行操作，生成一組子節(jié)點。第33頁，共79頁，2023年，2月20日，星期三第34頁，共79頁，2023年，2月20日，星期三搜索的一般過程如下：①把初始節(jié)點S0放入OPEN表，并建立目前只包含S0的圖，記為G。②檢查OPEN表是否為空，若為空則問題無解，退出。③把OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為節(jié)點n。④考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。⑤擴(kuò)展節(jié)點n，生成一組子節(jié)點。把其中不是節(jié)點n先輩的那些子節(jié)點記作集合M，并把這些子節(jié)點作為節(jié)點n的子節(jié)點加入G中。第35頁，共79頁，2023年，2月20日，星期三⑥針對M中子節(jié)點的不同情況，分別進(jìn)行如下處理：A、對于那些未曾在G中出現(xiàn)過的M成員設(shè)置一個指向父節(jié)點（即節(jié)點n）的指針，并把它們放入OPEN表。B、對于那些先前已在G中出現(xiàn)過的M成員，確定是否需要修改它指向父節(jié)點的指針。C、對于那些先前已在G中出現(xiàn)并且已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點指向父節(jié)點的指針。⑦按某種搜索策略對OPEN表中的節(jié)點進(jìn)行排序。⑧轉(zhuǎn)第（2）步。第36頁，共79頁，2023年，2月20日，星期三第37頁，共79頁，2023年，2月20日，星期三例1：實心黑點代表已擴(kuò)展了的節(jié)點，它們位于CLOSED表上；空心圓圈代表未擴(kuò)展的節(jié)點，它們位于OPEN表上；有向邊旁的箭頭是指向父節(jié)點的指針。每邊代價為1。第38頁，共79頁，2023年，2月20日，星期三擴(kuò)展節(jié)點1：假設(shè)現(xiàn)在要擴(kuò)展節(jié)點1，并且只生成單一的后繼節(jié)點2。但是目前節(jié)點2已有父節(jié)點3，即節(jié)點2在先前擴(kuò)節(jié)點3時已被生成了，現(xiàn)在又作為節(jié)點1的后繼節(jié)點被再次生成。此時，為確定哪一個節(jié)點作為節(jié)點2的父節(jié)點，需要計算路徑代價。從S0經(jīng)節(jié)點1到節(jié)點2的代價為2，而從S0經(jīng)節(jié)點3到節(jié)點2的代價為4，顯然經(jīng)節(jié)點1到節(jié)點2的代價較小，因此應(yīng)修改節(jié)點2指向父節(jié)點的指針，讓它指向節(jié)點1，即把節(jié)點1作為節(jié)點2的父節(jié)點，不再以節(jié)點3作為它的父節(jié)點。第39頁，共79頁，2023年，2月20日，星期三另外，節(jié)點4既是節(jié)點2的后繼節(jié)點又是節(jié)點6的后繼節(jié)點，當(dāng)節(jié)點2以節(jié)點3為父節(jié)點時，由于從S0經(jīng)節(jié)點2到節(jié)點4的代價大于從S0經(jīng)節(jié)點6到節(jié)點4的代價，所以節(jié)點4以節(jié)點6為父節(jié)點。但是，經(jīng)擴(kuò)展節(jié)點1之后，從S0經(jīng)節(jié)點2到節(jié)點4的代價為3，而從S0經(jīng)節(jié)點6到節(jié)點4的代價為4，所以節(jié)點4不能再以節(jié)點6為父節(jié)點，而需要改為以節(jié)點2為父節(jié)點。第40頁，共79頁，2023年，2月20日，星期三第41頁，共79頁，2023年，2月20日，星期三第42頁，共79頁，2023年，2月20日，星期三二、廣度優(yōu)先搜索——寬度優(yōu)先搜索1、基本思想：

從初始節(jié)點S0開始，逐層地對節(jié)點進(jìn)行擴(kuò)展并考察它是否為目標(biāo)節(jié)點，在第n層的節(jié)點沒有全部擴(kuò)展并考察之前，不對第n+1層的節(jié)點進(jìn)行擴(kuò)展。OPEN表中的節(jié)點總是按進(jìn)入的先后順序排列，先進(jìn)入的節(jié)點排在前面，后進(jìn)入的排在后面。第43頁，共79頁，2023年，2月20日，星期三2、搜索過程：①把初始節(jié)點S0放入OPEN表。②如果OPEN表為空，則問題無解，退出。③把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表。④考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。⑤若節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第②步。⑥擴(kuò)展節(jié)點n，將其子節(jié)點(不含先輩節(jié)點)放入OPEN表的尾部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第②步。第44頁，共79頁，2023年，2月20日，星期三例：重排九宮問題。在3×3的方格棋盤上放置分別標(biāo)有數(shù)字1,2,3,4,5,6,7,8的八張牌，初始狀態(tài)為S0，目標(biāo)狀態(tài)為Sg，如圖所示?？墒褂玫乃惴校嚎崭褡笠?，空格上移，空格右移，空格下移。即，它們只允許把位于空格左，上，右，下邊的牌移入空格。要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑。第45頁，共79頁，2023年，2月20日，星期三由圖3可以看出，解的路徑是S0——3——8——16——26。第46頁，共79頁，2023年，2月20日，星期三

廣度優(yōu)先搜索的優(yōu)劣：①缺點：盲目性較大，當(dāng)目標(biāo)節(jié)點距離初始節(jié)點較遠(yuǎn)時將會產(chǎn)生許多無用節(jié)點，搜索效率低。②優(yōu)點：只要問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。第47頁，共79頁，2023年，2月20日，星期三三、深度優(yōu)先搜索：1、基本思想：

從初始節(jié)點S0開始擴(kuò)展，若沒有得到目標(biāo)節(jié)點，則選擇最后產(chǎn)生的子節(jié)點進(jìn)行擴(kuò)展，若還是不能到達(dá)目標(biāo)節(jié)點，則再對剛才最后產(chǎn)生的子節(jié)點進(jìn)行擴(kuò)展，一直如此向下搜索。當(dāng)?shù)竭_(dá)某個子節(jié)點，且該子節(jié)點既不是目標(biāo)節(jié)點又不能繼續(xù)擴(kuò)展時，才選擇其兄弟節(jié)點進(jìn)行考察。第48頁，共79頁，2023年，2月20日，星期三2、其搜索過程如下：

①把初始節(jié)點S0放入OPEN表。②如果OPEN表為空，則問題無解，退出。③把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表。④考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。⑤若節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第②步。⑥擴(kuò)展節(jié)點n，將其子節(jié)點放入到OPEN表的首部，并為其配置指向父節(jié)點的指針，然后轉(zhuǎn)第②步。

該過程與廣度優(yōu)先搜索的唯一區(qū)別是：廣度優(yōu)先搜索是將節(jié)點n的子節(jié)點放入到OPEN表的尾部，而深度優(yōu)先搜索是把節(jié)點n的子節(jié)點放入到OPEN表的首部。第49頁，共79頁，2023年，2月20日，星期三例3：重排九宮問題進(jìn)行深度優(yōu)先搜索。（圖中只是搜索樹的一部分，尚未到達(dá)目標(biāo)節(jié)點，仍可繼續(xù)往下搜索。）第50頁，共79頁，2023年，2月20日，星期三深度優(yōu)先搜索的特點：

在深度優(yōu)先搜索中，搜索一旦進(jìn)入某個分支，就將沿著該分支一直向下搜索。如果目標(biāo)節(jié)點恰好在此分支上，則可較快地得到解。但是，如果目標(biāo)節(jié)點不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的，即使問題有解，它也不一定能求得解。另外，用深度優(yōu)先搜索求得的解，不一定是路徑最短的解。

第51頁，共79頁，2023年，2月20日，星期三四、有界深度優(yōu)先搜索：1、提出：為了解決深度優(yōu)先搜索不完備的問題，避免搜索過程陷入無窮分支的死循環(huán)，提出了有界深度優(yōu)先搜索方法。2、基本思想：對深度優(yōu)先搜索引入搜索深度的界限（設(shè)為dm)，當(dāng)搜索深度達(dá)到了深度界限，而尚未出現(xiàn)目標(biāo)節(jié)點時，就換一個分支進(jìn)行搜索。第52頁，共79頁，2023年，2月20日，星期三3、搜索過程：①把初始節(jié)點S0放入OPEN表中，置S0的深度d（S0)=0。②如果OPEN表為空，則問題無解，退出。③把OPEN表中的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表。④考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。⑤如果節(jié)點n的深度d（節(jié)點n）=dm，則轉(zhuǎn)第②步。⑥若節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第②步。⑦擴(kuò)展節(jié)點n，將其子節(jié)點放入OPEN表的首部，并為其配置指向父節(jié)點的指針。然后轉(zhuǎn)第②步。第53頁，共79頁，2023年，2月20日，星期三關(guān)于dm的討論：①如果問題有解，且其路徑長度<=dm，則上述搜索過程一定能求得解。但是，若解的路徑長度＞dm，則上述搜索過程就得不到解。②當(dāng)dm太大時，搜索時將產(chǎn)生許多無用的子節(jié)點，既浪費(fèi)了計算機(jī)的存儲空間與時間，又降低了搜索效率。③dm的選擇：先任意給定一個較小的數(shù)作為dm，然后進(jìn)行上述的有界深度優(yōu)先搜索，當(dāng)搜索達(dá)到了指定的深度界限dm仍未發(fā)現(xiàn)目標(biāo)節(jié)點，并且CLOSED表中仍有待擴(kuò)展節(jié)點時，就將這些節(jié)點送回OPEN表，同時增大深度界限dm，繼續(xù)向下搜索。如此不斷地增大dm，只要問題有解，就一定可以找到它。但此時找到的解不一定是最優(yōu)解。第54頁，共79頁，2023年，2月20日，星期三④為找到最優(yōu)解，可增設(shè)一個表（R)，每找到一個目標(biāo)節(jié)點后，就把它放入到R的前面，并令dm等于該目標(biāo)節(jié)點所對應(yīng)的路徑長度，然后繼續(xù)搜索。由于后求得的解的路徑長度不會超過先求得的解的路徑長度，所以最后求得的解一定是最優(yōu)解。第55頁，共79頁，2023年，2月20日，星期三例4：設(shè)深度界度dm=4，用有界深度優(yōu)先搜索方法求解重排九宮問題。）解的路徑是S0—20—25—26—28。第56頁，共79頁，2023年，2月20日，星期三五、代價樹的廣度優(yōu)先搜索

代價樹：邊上標(biāo)有代價（或費(fèi)用）的樹稱為代價樹。代價樹中，用c（x1，x2）表示從父節(jié)點x1到子節(jié)點x2的代價。用g（x）表示從初始節(jié)點S0到節(jié)點x的代價。代價計算公式：g（x2)=g（x1)+c（x1，x2)第57頁，共79頁，2023年，2月20日，星期三1、代價樹廣度優(yōu)先搜索的基本思想：

每次從OPEN表中選擇節(jié)點往CLOSED表傳送時，總是選擇其代價為最小的節(jié)點。（也就是說，OPEN表中的節(jié)點在任一時刻都是按其代價從小至大排序的，代價小的節(jié)點排在前面，代價大的節(jié)點排在后面，而不管節(jié)點在代價樹中處于什么位置上。）第58頁，共79頁，2023年，2月20日，星期三

2、代價樹廣度優(yōu)先搜索的搜索過程：(1）把初始節(jié)點S0放入OPEN表，令g(S0)=0。(2）如果OPEN表為空，則問題無解，退出。(3）把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表。(4）考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。(5）若節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第（2）步。(6）擴(kuò)展節(jié)點n，將其子節(jié)點放入OPEN表中，且為其配置指向父節(jié)點的指針；計算各子節(jié)點的代價，并按各節(jié)點的代價對OPEN表中的全部節(jié)點進(jìn)行排序（按從小到大的順序），然后轉(zhuǎn)第（2）步。如果問題有解，該搜索過程一定能求得，并且求出的是最優(yōu)解。第59頁，共79頁，2023年，2月20日，星期三例1：如圖1為五城市間的交通路線圖，A城市是出發(fā)地，E城市是目的地，兩城市間的交通費(fèi)用（代價）如圖中數(shù)字所示。求從A到E的最小費(fèi)用交通路線。第60頁，共79頁，2023年，2月20日，星期三為了應(yīng)用代價樹的廣度優(yōu)先搜索方法求解此問題，需先將交通圖轉(zhuǎn)換為代價樹，如圖2所示。轉(zhuǎn)換的方法是：①從起始節(jié)點A開始，把與它直接相鄰的節(jié)點作為它的子節(jié)點。對其它節(jié)點也做相同的處理。②若一個節(jié)點已作為某節(jié)點的直系先輩節(jié)點時，就不能再作為這個節(jié)點的子節(jié)點。③圖中的節(jié)點除起始節(jié)點A外，其它節(jié)點都可能要在代價樹中出現(xiàn)多次，為區(qū)分它的多次出現(xiàn)，分別用下標(biāo)1,2，…標(biāo)出，其實它們都是圖中的同一節(jié)點。例如El,E2,E3,E4都是圖中的節(jié)點E。對此代價樹進(jìn)行代價樹的廣度優(yōu)先搜索，可得到最優(yōu)解為A一Cl一Dl一E2代價為8。由此可知從A城市到E城市的最小費(fèi)用路線為A一C一D一E。第61頁，共79頁，2023年，2月20日，星期三八、代價樹的深度優(yōu)先搜索1、基本思想：

代價樹的深度優(yōu)先搜索是從剛擴(kuò)展出的子節(jié)點中選一個代價最小的節(jié)點送入CLOSED表進(jìn)行考察。（而在代價樹的廣度優(yōu)先搜索中，每次都是從OPEN表的全體節(jié)點中選擇一個代價最小的節(jié)點送入CLOSED表進(jìn)行考察。）

第62頁，共79頁，2023年，2月20日，星期三2、代價樹深度優(yōu)先搜索的過程：(1）把初始節(jié)點S0放入OPEN表中。(2）如果OPEN表為空，則問題無解，退出。(3）把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表。(4）考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。(5）若節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第(2)步。(6）擴(kuò)展節(jié)點n，將其子節(jié)點按邊代價從小到大的順序放到OPEN表的首部，并為各子節(jié)點配置指向父節(jié)點的指針，然后轉(zhuǎn)第(2)步。第63頁，共79頁，2023年，2月20日，星期三例如，在上圖所示的代價樹中，首先對A進(jìn)行擴(kuò)展，得到Cl及Bl，由于Cl的代價小于Bl的代價，所以首先把Cl送入CLOSED表進(jìn)行考察。此時代價樹的廣度優(yōu)先搜索與代價樹的深度優(yōu)先搜索是一致的。但往下繼續(xù)進(jìn)行時，兩者就不一樣了。對Cl進(jìn)行擴(kuò)展得到Dl，Dl的代價為5。此時OPEN表中有Bl與Dl,Bl的代價為4。若按代價樹的廣度優(yōu)先搜索方法進(jìn)行搜索，應(yīng)選Bl送入CLOSED表，但按代價樹的深度優(yōu)先搜索方法，則應(yīng)選Dl送入CLOSED表。Dl擴(kuò)展后，再選E2，到達(dá)了目標(biāo)節(jié)點。所以，按代價樹的深度優(yōu)先搜索方法，得到的解是A一Cl一Dl一E2代價為8。第64頁，共79頁，2023年，2月20日，星期三5.3與／或樹的搜索策略第65頁，共79頁，2023年，2月20日，星期三一、與／或樹的一般搜索過程：1、概念對于一個“與”節(jié)點，只有當(dāng)其子節(jié)點全部為可解節(jié)點時，它才為可解節(jié)點，只要子節(jié)點中有一個為不可解節(jié)點，它就是不可解節(jié)點。對與一個“或”節(jié)點，只要子節(jié)點中有一個是可解節(jié)點，它就是可解節(jié)點，只有當(dāng)全部子節(jié)點都是不可解節(jié)點時，它才是不可解節(jié)點?？山鈽?biāo)示過程：由可解子節(jié)點來確定父節(jié)點、祖父節(jié)點等為可解節(jié)點的過程稱為可解標(biāo)示過程。不可解標(biāo)示過程：由不可解子節(jié)點來確定其父節(jié)點、祖父節(jié)點等為不可解節(jié)點的過程稱為不可解標(biāo)示過程。第66頁，共79頁，2023年，2月20日，星期三2、與／或樹的一般搜索過程：(a）把原始問題作為初始節(jié)點S0，并把它作為當(dāng)前節(jié)點。(b）應(yīng)用分解或等價變換算符對當(dāng)前節(jié)點進(jìn)行擴(kuò)展。(c）為每個子節(jié)點設(shè)置指向父節(jié)點的指針。(d）選擇合適的子節(jié)點作為當(dāng)前節(jié)點，反復(fù)執(zhí)行第（b）步和第（c）步，在此期間要多次調(diào)用可解標(biāo)示過程和不可解標(biāo)示過程，直到初始節(jié)點被標(biāo)示為可解節(jié)點或不可解節(jié)點為止?？山馀c不可解標(biāo)示過程都是由下而上進(jìn)行的。第67頁，共79頁，2023年，2月20日，星期三由這個搜索過程所形成的節(jié)點和指針結(jié)構(gòu)稱為搜索樹。與／或樹搜索的目標(biāo)是尋找解樹，從而求得原始問題的解。如果在搜索的某一時刻，通過可解標(biāo)示過程可確定初始節(jié)點是可解的，則由此初始節(jié)點及其下屬的可解節(jié)點就構(gòu)成了解樹。如果已確定某個節(jié)點為可解節(jié)點，則其不可解的后裔節(jié)點就不再有用，可從搜索樹中刪去；同樣，如果已確定某個節(jié)點是不可解節(jié)點，則其全部后裔節(jié)點都不再有用，可從搜索樹中刪去，但當(dāng)前這個不可解節(jié)點還不能刪去，因為在判斷其先輩節(jié)點的可解性時還要用到它。第68頁，共79頁，2023年，2月20日，星期三二、與／或樹的廣度優(yōu)先搜索：

搜索過程如下：(1）把初始節(jié)點S0放入OPEN表。(2）把OPEN表中的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表。(3）如果節(jié)點n可擴(kuò)展，則做下列工作。①擴(kuò)展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每個子節(jié)點配置指向父節(jié)點的指針，以備標(biāo)示過程使用。

第69頁，共79頁，2023年，2月20日，星期三②考察這些子節(jié)點中有否終止節(jié)點。若有，則標(biāo)示這些終止節(jié)點為可解節(jié)點，并將它們也放入CLOSED表，然后應(yīng)用可解標(biāo)示過程對其父節(jié)點、祖父節(jié)點等先輩節(jié)點中的可解節(jié)點進(jìn)行標(biāo)示。如果初始節(jié)點S0也被標(biāo)示為可解節(jié)點，就得到了解樹，搜索成功，退出搜索過程；如果不能確定S0為可解節(jié)點，則從OPEN表中刪去具有可解先輩的節(jié)點。(因為其先輩節(jié)點已可解，故已無再考察節(jié)點的必要)③轉(zhuǎn)第（2）步。第70頁，共79頁，2023年，2月20日，星期三(4）如果節(jié)點n不可擴(kuò)展，則做下列工作：①標(biāo)示節(jié)點n為不可解節(jié)點。②應(yīng)用不可解標(biāo)示過程對節(jié)點n的先輩節(jié)點中不可解的節(jié)點進(jìn)行標(biāo)示。如果初始節(jié)點S0也被標(biāo)示為不可解節(jié)點，則搜索失敗，表明原始問題無解，退出搜索過程；如果不能確定S0為不可解節(jié)點，則從OPEN表中刪去具有不可解先輩的節(jié)點。(因為其先輩節(jié)點已不可解，故已無再考察這些節(jié)點的必要)③轉(zhuǎn)第(2)步。第71頁，共79頁，2023年，2月20日，星期三例:設(shè)有如圖所示的與／或樹。其中標(biāo)有t1，t2，t3，t4的節(jié)點均為終止節(jié)點，A和B為不可解的端節(jié)點。第72頁，共79頁，2023年，2月20日，星期三搜索過程為：

(l）首先擴(kuò)展1號節(jié)點，得到2號節(jié)點和3號節(jié)點，由于這兩個子節(jié)點均不是終止節(jié)點，所以接著擴(kuò)展2號節(jié)點。此時OPEN表中只剩下3號節(jié)點。

(2）擴(kuò)展2號節(jié)點后，得到4號節(jié)點和t1節(jié)點。此時OPEN表中的節(jié)點有：3號節(jié)點、4號節(jié)點及t1節(jié)點。由于t1是終止節(jié)點，則標(biāo)示它為可解節(jié)點，并應(yīng)用可解標(biāo)示過程，對其先輩節(jié)點中的可解節(jié)點進(jìn)行標(biāo)示。在此例中，t1的父節(jié)點是一個“與”節(jié)點，因此僅由t1可解尚不能確定2號節(jié)點是否為可解節(jié)點。將t1放入closed表中，繼續(xù)搜索，下一步擴(kuò)展的是3號節(jié)點。第73頁，共79頁，2023年，2月20日，星期三(3）擴(kuò)展3號節(jié)點得到5號節(jié)點與B節(jié)點，兩者均不是終止節(jié)點，所以接著擴(kuò)展4號節(jié)點。(4）擴(kuò)展4號節(jié)點后得到節(jié)點A和t2。由于t2是終止節(jié)點，所以標(biāo)示它為可解節(jié)點，放入closed中，并應(yīng)用可解標(biāo)示過程標(biāo)示出4號節(jié)點、2號節(jié)點均為可解節(jié)點，但1號節(jié)點目前還不能確定它是否為可解節(jié)點。刪除