問題求解的基本原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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