【文章內(nèi)容簡介】 再將所有笫一層節(jié)點逐一擴展，得到第二層節(jié)點。并逐一檢查第二層節(jié)點中是否包含有 Sg，如此依次按照先生成、先檢查、先擴展的原則進行下去，直到發(fā)現(xiàn) Sg為止 2023/5/15 73寬度優(yōu)先實例2 31 8 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 5125 6 731 2 3 8 47 6 5 目標82 3 41 8 7 6 5491011 12 13 14 1516 172023/5/15 74寬度優(yōu)先搜索 ?如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做 寬度優(yōu)先搜索。?這種搜索是逐層進行的，在對下一層的任意節(jié)點進行搜索之前，必須搜索完本層的所有節(jié)點。?“先產(chǎn)生的節(jié)點先擴展 ”2023/5/15 75 (1)把初始節(jié)點 S0，放入 OPEN表。 (2)如果 OPEN表為空。則問題無解，失敗并退出。 (3)把 OPEN表中的第一個節(jié)點取出放入 CLOSE表中，并按順序冠以編號 n； (4)考察節(jié)點 n是否為目標節(jié)點。若是，則求得了問題的解，成功并退出。 (5)若節(jié)點 n不可擴展，則轉(zhuǎn)第 (2)步； (6)擴展節(jié)點 n，將其子節(jié)點放到 OPEN表的 尾部 ，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第 (2)步。采用隊列結(jié)構(gòu)，寬度優(yōu)先算法可以表示如下：2023/5/15 76 例 通過挪動積木塊，希望從初始狀態(tài)達到一個目的狀態(tài)，即三塊積木堆疊在一起。積木 A在頂部，積木 B在頂中間，積木 C在底部。請畫出按照寬度優(yōu)先搜索策略所產(chǎn)生的搜索樹。 這個問題的唯一操作算子為 MOVE(X,Y)，即積木 X搬到 Y（積木或桌面）上面。如 “ 挪動積木 A到桌面上表示為 MOVE(A,Table)。該操作算子可運用的先決條件是：（ 1）被挪動積木的頂部必須為空。（ 2）如 Y是積木（不是桌面），則積木 Y的頂部也必須為空。（ 3）同一狀態(tài)下，運用操作算子的次數(shù)不得多于一次。2023/5/15 77積木問題的寬度優(yōu)先搜索樹 2023/5/15 78寬度優(yōu)先搜索的性質(zhì)o 當問題有解時， 一定 能找到解 (完備性 )o 當問題為單位代價時，且問題有解時， 一定能找到最優(yōu)解（最優(yōu)性）o 方法與問題無關(guān)，具有通用性o 效率較低o 屬于圖搜索方法2023/5/15 79o 寬度優(yōu)先搜索 是一種盲目搜索，時間和空間復(fù)雜度都比較高，當目標節(jié)點距離初始節(jié)點較遠時會產(chǎn)生許多無用的節(jié)點，搜索效率低。o 寬度優(yōu)先搜索中，時間需求是一個很大的問題，特別是當搜索的深度比較大時，尤為嚴重，但是空間需求是比執(zhí)行時間更嚴重的問題。 寬度優(yōu)先搜索優(yōu)點：目標節(jié)點如果存在，用寬度優(yōu)先搜索算法總可以找到該目標節(jié)點，而且 是最?。醋疃搪窂剑┑墓?jié)點。寬度優(yōu)先搜索的優(yōu)點和缺點2023/5/15 80深度優(yōu)先深度優(yōu)先o 深度優(yōu)先 ——擴展當前節(jié)點后生成的子節(jié)點總是 置于 OPEN表的前端 ，即 OPEN表 作為 棧 ， 后進先出 ，使 搜索優(yōu)先向縱深方向發(fā)展 。o 過程：從初始節(jié)點 S0開始，按生成規(guī)則生成下一級各子節(jié)點，檢查是否出現(xiàn)目標節(jié)點 Sg；若未出現(xiàn)，則按 “ 最晚生成的子節(jié)點優(yōu)先擴展 ” 的原則，再用生成規(guī)則生成再下一級的子節(jié)點，再檢查是否出現(xiàn) Sg；若仍未出現(xiàn)，則再擴展最晚生成的子節(jié)點。如此下去，沿著最晚生成的子節(jié)點分枝，逐級 “ 縱向 ” 深入搜索。 2023/5/15 81深度優(yōu)先實例2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 61234 689 1113141618191 2 3 8 47 6 5目標5 71012151720212023/5/15 82深度優(yōu)先搜索o 在深度優(yōu)先搜索中，首先擴展最新產(chǎn)生的 (最深的 )節(jié)點，深度 相等的節(jié)點可以任意排列。o “ 最晚產(chǎn)生的節(jié)點最先擴展 ”? 起始節(jié)點深度為 0 ? 任何其他節(jié)點的深度等于其父輩節(jié)點深度加上 1 :dn=dn1+12023/5/15 83深度優(yōu)先搜索?很明顯這樣做， 不一定 找到最佳解，而且由于深度的限制，可能找不到解，然而，若不加深度限制，可能沿著一條路線無限制地擴展下去，這當然是不允許的。?為保證找到解，應(yīng)選擇適當?shù)?深度界限 ，或者采取不斷加大深度界限的辦法，反復(fù)搜索，直到找到解。這種改進的方法叫做迭代加深搜索 。2023/5/15 84(1)把初始節(jié)點 S0放入 OPEN表； (2)如果 OPEN表為空，則問題無解，失敗并退出。 (3)把 OPEN表中的第一個節(jié)點取出放入 CLOSE表中，并按順序冠以編號 n； (4)考察節(jié)點 n是否為目標節(jié)點。若是，則求得了問題的解，成功并退出。 (5)若節(jié)點 n不可擴展，則轉(zhuǎn)第 (2)步； (6)擴展節(jié)點 n，將其子節(jié)點放到 OPEN表的 首部 ，并為其配置指向父節(jié)點的指針，然后轉(zhuǎn)第 (2)步?；跅崿F(xiàn)的深度優(yōu)先搜索算法： 2023/5/15 85 例 卒子穿陣問題 : 要求一卒子從頂部通過圖所示的列陣到達底部。要求卒子行進中不可進入到代表敵兵駐守的區(qū)域內(nèi)（標注 1），并不準后退。 假定限制值為 5。請畫出按照深度優(yōu)先搜索策略所產(chǎn)生的搜索樹 2023/5/15 86卒子穿陣的深度優(yōu)先搜索樹 2023/5/15 87深度優(yōu)先搜索的性質(zhì)深度優(yōu)先搜索的性質(zhì)o 一般不能保證找到最優(yōu)解o 當深度限制不合理時， 可能找不到解 ，可以將算法改為 可變深度限制o 最壞情況時，搜索空間等同于窮舉o 是一個通用的與問題無關(guān)的方法2023/5/15 88o 深度優(yōu)先搜索 的 優(yōu)點 是 比寬度優(yōu)先搜索算法需要較少的空間 ，該算法只需要保存搜索樹的一部分，它由 當前正在搜索的路徑和該路徑上還沒有完全展開的節(jié)點標志所組成 。o 深度優(yōu)先搜索的存儲器要求是深度約束的線性函數(shù)。 深度優(yōu)先搜索的優(yōu)點深度優(yōu)先搜索的優(yōu)點2023/5/15 89深度優(yōu)先搜索的缺點深度優(yōu)先搜索的缺點 既不是完備的，也不是最優(yōu)的。 主要問題是可能 搜索到了錯誤的路徑上 。很多問題可能具有很深甚至是無限的搜索樹，如果不幸選擇了一個錯誤的路徑，則深度優(yōu)先搜索會一直搜索下去，而不會回到正確的路徑上。這樣一來對于這些問題，深度優(yōu)先搜索要么陷入無限的循環(huán)而不能給出一個答案，要么最后找到一個答案，但路徑很長而且不是最優(yōu)的答案。2023/5/15 90比較 o 適用場合 ?深度優(yōu)先 —— 當一個問題有多個解答或多條解答路徑，且只須找到其中一個時； 往往應(yīng)對搜索深度加以限制 。 ?寬度優(yōu)先 —— 確保搜索到 最短的解答路徑 。o 共同優(yōu)缺點： ?可直接應(yīng)用一般圖搜索算法實現(xiàn)，不需要設(shè)計特別的節(jié)點排序方法，從而簡單易行，適合于許多復(fù)雜度不高的問題求解任務(wù)。 ?節(jié)點排序的盲目性，由于不采用領(lǐng)域?qū)ｉT知識去指導排序，往往會在白白搜索了大量無關(guān)的狀態(tài)節(jié)點后才碰到解答，所以也稱為 盲目搜索 。 2023/5/15 91有界深度搜索和迭代加深搜索 有界深度優(yōu)先搜索 過程總體上按深度優(yōu)先算法方法進行，但對搜索深度需要給出一個深度限制 dm，當深度達到了 dm的時候，如果還沒有找到解答，就停止對該分支的搜索，換到另外一個分支進行搜索。2023/5/15 92(1)把初始節(jié)點 S0放入 OPEN表中，置 S0的深度 d(S0)=0。 (2)如果 OPEN表為空，則問題無解，失敗并退出。 (3)把 OPEN表中的第一個節(jié)點取出放入 CLOSE表中。并按順序冠以編號 n。(4)考察節(jié)點 n是否為目標節(jié)點。若是，則求得了問題的解，成功并退出。 (5)如果節(jié)點 n的深度 d(n)= dm，則轉(zhuǎn)第 (2)步 。 (6)如果節(jié)點 n不可擴展，則轉(zhuǎn)第 (2)步。 (7)擴展節(jié)點 n。將其子節(jié)點放入 OPEN表的 首部 ，并為其配置指向父節(jié)點的指針。然后轉(zhuǎn)第 (2)步。 有界深度搜索算法2023/5/15 93策略說明 : o （ 1） 深度限制 dm很重要 。 當問題有解，且解的路徑長度小于或等于 dm時，則搜索過程一定能夠找到解，但是和深度優(yōu)先搜索一樣這并不能保證最先找到的是最優(yōu)解。o 但是當 dm取得太小，解的路徑長度大于 dm時，則搜索過程中就找不到解，即這時搜索過程甚至是不完備的。2023/5/15 94（ 2） 深度限制 dm不能太大 。當 dm太大時，搜索過程會產(chǎn)生過多的無用節(jié)點，既浪費了計算機資源，又降低了搜索效率。（ 3）有界深度搜索的主要問題是 深度限制值 dm的選取 。 2023/5/15 95改進方法 ： （迭代加深搜索） 先任意給定一個較小的數(shù)作為 dm，然后按有界深度算法搜索，若在此深度限制內(nèi)找到了解，則算法結(jié)束；如在此限制內(nèi)沒有找到問題的解，則增大深度限制dm，繼續(xù)搜索。2023/5/15 96o 迭代加深搜索 ，試圖嘗試所有可能的深度限制：n 首先深度為 0，n 然后深度為 1，n 然后為 2，等等。o 如果初始深度為 0，則該算法只生成根節(jié)點，并檢測它。o 如果根節(jié)點不是目標，則深度加 1，通過典型的深度優(yōu)先算法，生成深度為 1的樹。o 當深度限制為 m時，樹的深度為 m。 2023/5/15 97o 迭代加深搜索看起來會很浪費，因為很多節(jié)點都可能擴展多次。o 然而對于很多問題， 這種多次的擴展負擔實際上很小 ，直覺上可以想象，如果一棵樹的分支系數(shù)很大，幾乎所有的節(jié)點都在最底層上，則對于上面各層節(jié)點擴展多次對整個系統(tǒng)來說影響不是很大。 2023/5/15 98 Procedure IterativedeepeningBegin(1)設(shè)置當前深度限制 =1。 (2)把初始節(jié)點壓入棧 ,并設(shè)置棧頂指針 。 (3)While棧不空并且深度在給定的深度限制之內(nèi) do Begin 彈出棧頂元素； If棧頂元素 =goal,返回并結(jié)束 。 Else以任意的順序把棧頂元素的子女壓入棧中 。 End End whild (4)深度限制加 1,并返回 2。End.迭代加深搜索算法2023/5/15 99總結(jié)o 寬度優(yōu)先搜索、深度優(yōu)先搜索和迭代加深搜索都可以用于生成和測試算法。o 寬度優(yōu)先搜索 需要指數(shù)數(shù)量的空間，深度優(yōu)