問(wèn)題求解的基本原理

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

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

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

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

從初始節(jié)點(diǎn)S0開(kāi)始，逐層地對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察它是否為目標(biāo)節(jié)點(diǎn)，在第n層的節(jié)點(diǎn)沒(méi)有全部擴(kuò)展并考察之前，不對(duì)第n+1層的節(jié)點(diǎn)進(jìn)行擴(kuò)展。OPEN表中的節(jié)點(diǎn)總是按進(jìn)入的先后順序排列，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面。第43頁(yè)，共79頁(yè)，2023年，2月20日，星期三2、搜索過(guò)程：①把初始節(jié)點(diǎn)S0放入OPEN表。②如果OPEN表為空，則問(wèn)題無(wú)解，退出。③把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSED表。④考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)題的解，退出。⑤若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第②步。⑥擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)(不含先輩節(jié)點(diǎn))放入OPEN表的尾部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第②步。第44頁(yè)，共79頁(yè)，2023年，2月20日，星期三例：重排九宮問(wèn)題。在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頁(yè)，共79頁(yè)，2023年，2月20日，星期三由圖3可以看出，解的路徑是S0——3——8——16——26。第46頁(yè)，共79頁(yè)，2023年，2月20日，星期三

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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