第三章搜索策略

2023/1/191第3章搜索策略問題求解系統(tǒng)劃分為兩大類知識貧乏系統(tǒng)

依靠搜索技術(shù)解決問題知識貧乏、缺乏針對性效率低知識豐富系統(tǒng)

依靠推理技術(shù)解決問題基于豐富知識的推理技術(shù)，直截了當(dāng)效率高2023/1/192第3章搜索策略兩大類搜索技術(shù):1、一般圖搜索、啟發(fā)式搜索2、基于問題歸約的與或圖搜索兩種典型的推理技術(shù):1、基于歸結(jié)的演繹推理歸結(jié)反演2、基于規(guī)則的演繹推理正向演繹推理逆向演繹推理2023/1/1933.1引言

對于給定的問題，智能系統(tǒng)的行為一般是找到能夠達到所希望目標(biāo)的動作序列，并使其所付出的代價最小、性能最好?；诮o定的問題，問題求解的第一步是目標(biāo)的表示。搜索就是找到智能系統(tǒng)的動作序列的過程。2023/1/194搜索算法的輸入是給定的問題，輸出是表示為動作序列的方案。一旦有了方案，就可以執(zhí)行該方案所給出的動作了。（執(zhí)行階段）因此，求解問題包括：目標(biāo)表示搜索執(zhí)行2023/1/195（1）初始狀態(tài)集合：定義了初始的環(huán)境。（2）操作符集合：把一個問題從一個狀態(tài)變換為另一個狀態(tài)的動作集合。（3）目標(biāo)檢測函數(shù)：用來確定一個狀態(tài)是不是目標(biāo)。（4）路徑費用函數(shù)：對每條路徑賦予一定費用的函數(shù)。其中，初始狀態(tài)集合和操作符集合定義了問題的搜索空間。一般給定問題就是確定該問題的一些基本信息，一個問題由4部分組成:2023/1/196和通常的搜索空間不同，人工智能中大多數(shù)問題的狀態(tài)空間在問題求解之前不是全部知道的。

在人工智能中，搜索問題一般包括兩個重要的問題：搜索什么搜索什么通常指的就是目標(biāo)。在哪里搜索在哪里搜索就是“搜索空間”。搜索空間通常是指一系列狀態(tài)的匯集，因此稱為狀態(tài)空間。2023/1/197所以，人工智能中的搜索可以分成兩個階段：狀態(tài)空間的生成階段在該狀態(tài)空間中對所求問題狀態(tài)的搜索搜索可以根據(jù)是否使用啟發(fā)式信息分為盲目搜索啟發(fā)式搜索2023/1/198盲目搜索只是可以區(qū)分出哪個是目標(biāo)狀態(tài)。一般是按預(yù)定的搜索策略進行搜索。沒有考慮到問題本身的特性，這種搜索具有很大的盲目性，效率不高，不便于復(fù)雜問題的求解。

啟發(fā)式搜索是在搜索過程中加入了與問題有關(guān)的啟發(fā)式信息，用于指導(dǎo)搜索朝著最有希望的方向前進，加速問題的求解并找到最優(yōu)解。

2023/1/199根據(jù)問題的表示方式分為狀態(tài)空間搜索與或圖搜索狀態(tài)空間搜索是用狀態(tài)空間法來求解問題所進行的搜索與/或圖搜索是指用問題規(guī)約方法來求解問題時所進行的搜索。2023/1/1910考慮一個問題的狀態(tài)空間為一棵樹的形式。寬度優(yōu)先搜索深度優(yōu)先搜索如果根節(jié)點首先擴展，然后是擴展根節(jié)點生成的所有節(jié)點，然后是這些節(jié)點的后繼，如此反復(fù)下去。在樹的最深一層的節(jié)點中擴展一個節(jié)點。只有當(dāng)搜索遇到一個死亡節(jié)點（非目標(biāo)節(jié)點并且是無法擴展的節(jié)點）的時候，才返回上一層選擇其他的節(jié)點搜索。2023/1/111無論是寬度度優(yōu)先搜索索還是深度度優(yōu)先搜索索，遍歷節(jié)節(jié)點的順序序一般都是是固定的，，即一旦搜搜索空間給給定，節(jié)點點遍歷的順順序就固定定了。這種種類型的遍遍歷稱為“確定性”的，也就是是盲目搜索。對于啟發(fā)式式搜索，在在計算每個個節(jié)點的參參數(shù)之前無法確定先先選擇哪個個節(jié)點擴展展，這種搜索索一般也稱2023/1/112完備性：如果存在一個個解答，該策策略是否保證證能夠找到？時間復(fù)雜性：需要多長時間可以找到解答？空間復(fù)雜性：執(zhí)行搜索需要多少存儲空間？最優(yōu)性：如果存在不同的幾個解答，該策略是否可以發(fā)現(xiàn)最高質(zhì)量的解答？搜索策略評價價標(biāo)準(zhǔn):2023/1/113有許多智力力問題(如梵塔問題題、旅行商商問題、八八皇后問題題、農(nóng)夫過過河問題等等)和實際問題題（如路徑徑規(guī)劃、機機器人行動動規(guī)劃等））都可以歸歸結(jié)為狀態(tài)空間搜搜索。用狀態(tài)空間搜搜索來求解問題題的系統(tǒng)均均定義一個個狀態(tài)空間，并通過適適當(dāng)?shù)乃阉魉惴ㄔ?.2基于狀態(tài)空空間圖的搜搜索技術(shù)2023/1/114狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示(1)狀態(tài)空間的的表示狀態(tài)空間記記為SP，可表示為為二元組：：SP=(S,O)S——問題求解（（即搜索））過程中所所有可能到達的合法狀態(tài)構(gòu)成的集合合；O——操作算子的集合，操作算子的的執(zhí)行會導(dǎo)導(dǎo)致問題狀狀態(tài)的變遷遷；狀態(tài)——用于記載問問題求解（（即搜索））過程中某一時刻問問題現(xiàn)狀的的快照；抽象為矢量量形式Q=[q0,q1,…,qn]T每個元素qi稱為狀態(tài)分量給定每個個狀態(tài)分量量qi的值就得得到一個個具體的的狀態(tài)Qk=[q0k,q1k,…,qnk]T2023/1/115狀態(tài)表示狀態(tài)態(tài)的變遷遷操作算子子問題的狀狀態(tài)空間間是一個表表示該問問題的全全部可能能狀態(tài)及及其變遷遷的有向圖。節(jié)點狀態(tài)有向弧狀態(tài)的變變遷弧上的標(biāo)標(biāo)簽導(dǎo)致狀態(tài)態(tài)變遷的的操作算子子用狀態(tài)空間間搜索來求解2023/1/116例1：走迷宮是人們熟悉悉的一種游游戲。狀態(tài)空間搜搜索2023/1/117格子、入口口和出口——節(jié)點——狀態(tài)通道——有向弧——操作算子迷宮可以由由一個有向圖表示2023/1/118例2:在一個3×3的方格棋盤盤上放置著著1,2,3,4,5,6,7,8八個數(shù)碼，，每個數(shù)碼碼占一格，，且有一個個空格。這這些數(shù)碼可可在棋盤上上移動，其其移動規(guī)則則是：與空空格相鄰的的數(shù)碼方可可移入空格格?，F(xiàn)在的問題是：對于指指定的56741382初始棋局56748321目標(biāo)棋局移動數(shù)碼2023/1/119231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123847652023/1/1202023/1/121狀態(tài)空間搜索索——1.狀態(tài)空間及其其搜索的表示示(2)狀態(tài)空間表示示的經(jīng)典例子子“傳教士和和野人問題””問題的描述：N個傳教士帶領(lǐng)領(lǐng)N個野人劃船過過河；3個安全約束條條件：1)船上人數(shù)不得得超過載重限限量，設(shè)為K個人；2)任何時刻（包包括兩岸、船船上）野人數(shù)數(shù)目不得超過過傳教士；3)允許在河的某某一岸或者在在船上只有野野人而沒有傳傳教士；22狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示(2)狀態(tài)空間表表示的經(jīng)典典例子“傳傳教士和野野人問題””特例：N=3，K=2狀態(tài)分量m——傳教士在左左岸的實際際人數(shù)狀態(tài)分量c——野人在左岸岸的實際人人數(shù)狀態(tài)分量b——指示船是否否在左岸(1、0)3個安全約束束條件m≧c(左岸安全)且N-m≧≧N-c(右岸安全);m=0且0≤c≤≤N(左岸沒有傳傳道士，右右岸一定安安全);N-m=0且0≤N-c≤N(右岸沒有傳傳道士，左左岸一定安安全);2023/1/123設(shè)初始狀態(tài)下傳教士、、野人和船船都在左岸岸，目標(biāo)狀態(tài)下這三者均均在右岸，，問題狀態(tài)以（m,c,b）表示。問題的求解解任務(wù)可描描述為：(3,3,1)→(0,0,0)該簡單問題題可能到達的合法狀態(tài)：可能狀態(tài)總數(shù)：4×4×2=32根據(jù)條件得得出合法狀態(tài)：20m≧c且N-m≧≧N-c(左岸安全且且右岸安全全)m=1,c=1；m=2,c=2m=0且0≤c≤≤N(左岸沒有傳傳道士)m=0,c=0,1,2,3N-m=0且0≤N-c≤N(右岸沒有傳傳道士)m=3,c=0,1,2,3不可能到達達的合法狀狀態(tài)：(0,0,1),(0,3,0),(3,0,1),(3,3,0)可能到達的合法狀態(tài)共16個2023/1/124狀態(tài)空間搜索索——1.狀態(tài)空間及其其搜索的表示示(2)狀態(tài)空間表示示的經(jīng)典例子子“傳教士和和野人問題””定義2類操作算子：L(x,y)——指示從左岸到右岸的劃船操作R(x,y)——指示從右岸到左岸的劃船操作x+y≤≤K=2(船的載重限制制)；x和y取值的可能組組合只有5個10，20，11，01，02(允許在船上只只有野人而沒沒有傳教士)共有10個操作算子2023/1/125渡河問題的狀狀態(tài)空間有向向圖2023/1/126狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示由此例可以以看出用狀態(tài)空間間方法表示示問題時，，首先必須須定義狀態(tài)的的描述形式式，通過使用用這種描述述形式可把把問題的一切狀態(tài)都都表示出來來。另外，還還要定義一組操操作，通過使用用這些操作作可把問題題由一種狀態(tài)態(tài)轉(zhuǎn)變?yōu)榱砹硪环N狀態(tài)態(tài)。問題的求解解過程是一一個不斷把操作作作用于狀狀態(tài)的過程程。如果在使使用某個操操作后得到到的新狀態(tài)態(tài)是目標(biāo)狀狀態(tài)，就得得到了問題題的一個解解。這個解解是從初始狀態(tài)到到目標(biāo)狀態(tài)態(tài)所用操作作構(gòu)成的序序列。2023/1/127狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示由此例可以以看出要使問題由由一種狀態(tài)態(tài)轉(zhuǎn)變到另另一種狀態(tài)態(tài)時，就必必須使用一一次操作。。這樣，在在從初始狀狀態(tài)轉(zhuǎn)變到到目標(biāo)狀態(tài)態(tài)時，就可可能存在多多個操作序序列(即得到多個解解)。那么，其中中使用操作最少少或較少的解解才為最優(yōu)解解(因為只有在使使用操作時所所付出的代價價為最小的解解才是最優(yōu)解解)。對其中的某一一個狀態(tài)，可可能存在多個個操作．使該該狀態(tài)變到幾幾個不同的后后繼狀態(tài)．那那么到底用哪哪個操作進行行搜索呢?這就有賴于搜索策略了．不同的搜索策策略有不同的的順序，這就是本章章后面要討論論的問題。2023/1/128課堂練練習(xí)有一農(nóng)農(nóng)夫帶帶一只只狐貍貍、一一只小小羊和和一籃籃菜過過河（（從左左岸到到右岸岸）。。假設(shè)設(shè)船太太小，，農(nóng)夫夫每次次只能能帶一一樣?xùn)|東西過過河；；考慮慮到安安全，，無農(nóng)農(nóng)夫看看管時時，狐狐貍和和小羊羊不能能在一一起，，小羊羊和那那籃菜菜也不不能在在一起起。請請為該該問題題的解解決設(shè)設(shè)計狀狀態(tài)空空間，，并畫畫出狀狀態(tài)空空間圖圖。2023/1/129解析以變量量m、f、s、v分別指指示農(nóng)農(nóng)夫、、狐貍貍、小小羊、、菜,且每個個變量量只可可取值值1(表示在在左岸岸)或0(表示在在右岸岸)。問題題狀態(tài)態(tài)可以以四元元組(m、f、s、v)描述,設(shè)初始始狀態(tài)態(tài)下均均在左左岸,目標(biāo)狀狀態(tài)下下都到到達右右岸。。從而而,問題求求解任任務(wù)可可描述述為(1,1,1,1)->(0,0,0,0)由于問問題簡簡單,狀態(tài)空空間中中可能能的狀狀態(tài)總總數(shù)為為2×2×2×2=16,由于要要遵從從安全全限制制,合法的的狀態(tài)態(tài)只有有(除初、、目狀狀態(tài)外外):1110，1101，1011，1010，0101，0001，0010，0100；不不合法法狀態(tài)態(tài)有:0111,1000,1100,0011,0110,1001設(shè)計二二類操操作算算子:Lx、Rx,x為m、f、s、v時分別別指示示農(nóng)夫夫獨自自,帶狐貍貍,帶小羊羊,帶菜過過河；；狀態(tài)態(tài)空間間圖如如下所所示.由于Lx和Rx是互逆逆操作作,故而解解答路路徑可可有無無數(shù)條條,但最近近的只只有二二條;都是7個操作作步.思考：：為什什么不不把船船的狀狀態(tài)放放到狀狀態(tài)空空間中中去？？2023/1/130解析:四元組組(m、f、s、v)2023/1/131狀態(tài)空間搜索索——1.狀態(tài)空間及其其搜索的表示示(3)狀態(tài)空間的搜搜索狀態(tài)空間的搜搜索記為SE，可表示為五五元組：SE=(S,O,E,I,G)；E——搜索引擎；I——問題的初始狀狀態(tài)，I∈S；G——問題的目標(biāo)狀狀態(tài)集合，GS。搜索引擎E——可以設(shè)計為實現(xiàn)任何搜索索算法的控制系統(tǒng)。?；舅枷搿ㄟ^搜索引擎擎E尋找一個操作算子的調(diào)調(diào)用序列，使問題從初初始狀態(tài)I變遷到目標(biāo)狀狀態(tài)G之一。解答路徑——初-目變遷過程中中的狀態(tài)序列或相應(yīng)的操作算子調(diào)用用序列。2023/1/132狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示或圖（一般般圖）一個狀態(tài)可以有多個可供供選擇的操作算子子；操作算子間間的選擇是是一種“或”的關(guān)系;這樣的有向向圖稱為或圖。2023/1/133狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示(3)狀態(tài)空間的的搜索或圖（一般般圖）一個狀態(tài)可可以有多個個可供選擇擇的操作算算子；操作算子間間的選擇是是一種“或”的關(guān)關(guān)系系，，這樣樣的的有有向向圖圖稱稱為為或圖圖。。狀態(tài)態(tài)空空間間一般般都都表表示示為為或圖圖（（一一般般圖圖））搜索索圖圖———在搜索索解解答答路路徑徑的過過程程中中畫畫出出搜搜索索時時涉涉及及到到的的節(jié)節(jié)點點和和弧弧線線，，構(gòu)構(gòu)成成所所謂謂的的搜索索圖圖。狀態(tài)態(tài)空空間間搜搜索索一般般圖圖搜搜索索2023/1/134狀態(tài)空空間搜搜索——1.狀態(tài)空空間及及其搜搜索的的表示示(3)狀態(tài)空空間的的搜索索狀態(tài)空空間、搜索圖圖和解答路路徑之間的的關(guān)系系S0Sg2023/1/135狀態(tài)空間搜索索——1.狀態(tài)空間及其其搜索的表示示(4)一般圖搜索例例子——八數(shù)碼游戲求解的問題：：給定初始布局局(即初始狀態(tài))和目標(biāo)布局(即目標(biāo)狀態(tài))，如何移動數(shù)碼碼才能從初始始布局到達目目標(biāo)布局？解答就是一個合法法的棋牌走步序列列。初始布局目標(biāo)布局移動數(shù)碼2023/1/136狀態(tài)態(tài)空空間間搜搜索索———1.狀態(tài)態(tài)空空間間及及其其搜搜索索的的表表示示(4)一般般圖圖搜搜索索例例子子———八數(shù)數(shù)碼碼游游戲戲用一一般般圖圖搜搜索索方方法法解解決決該該問問題題的的步步驟驟：：1、為為問題題狀狀態(tài)態(tài)的表表示示建建立立數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)2、制制定定操作作算算子子集合合3、設(shè)設(shè)計計搜索索引引擎擎第一一步步：：為為問問題題狀狀態(tài)態(tài)的的表表示示建建立立數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)3××3的一一個個矩矩陣陣S矩陣陣元元素素Sij∈∈{0,1,2,3,4,5,6,7,8},其中1≤i,j≤3數(shù)字0表示空格數(shù)字1-8表示相應(yīng)的的棋牌八數(shù)碼問題題就可表示示為：2023/1/137狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示初始布局目標(biāo)布局移動數(shù)碼(4)一般圖搜索索例子——八數(shù)碼游戲戲2023/1/138狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示(4)一般圖搜索索例子——八數(shù)碼游戲戲第二步：制制定操作算算子集直觀方法——為每個棋牌牌制定一套套可能的走走步：左、、上、右、、下四種移移動。需要32個操作算子子簡易方法——僅為空格制制定這4種走步。僅需4個操作算子子第三步：設(shè)設(shè)計搜索引引擎問題狀態(tài)空空間的大小小與問題題涉涉及及的的元元素素個數(shù)數(shù)是是程程指數(shù)數(shù)級級爆爆炸炸式式增增長長（即即，，組合合爆爆炸炸問問題題）如，，棋棋盤盤布布局局（（問問題題狀狀態(tài)態(tài)））總總共共有有9!=362880個研究究焦焦點點是解決決組組合合爆爆炸炸問問題題，通過過壓壓縮縮搜搜索索空空間間，提高高搜搜索索效效率率。2023/1/139狀態(tài)態(tài)空空間間搜搜索索———1.狀態(tài)態(tài)空空間間及及其其搜搜索索的的表表示示狀態(tài)態(tài)空空間間、搜索索圖圖和解答答路路徑徑之間間的的關(guān)關(guān)系系S0Sg2023/1/140狀態(tài)空間間搜索——2.一般圖搜搜索策略略（1）搜索術(shù)術(shù)語1、節(jié)點深深度根節(jié)點指示初始狀態(tài)態(tài)，令其深深度為0；搜索圖中中的其他他節(jié)點的的深度dn就可以遞遞歸地定定義為其其父節(jié)點深深度dn-1加1：dn=dn-1+1。根節(jié)點深深度=0第n-1層節(jié)點dn-1第n層節(jié)點dn=dn-1+1搜索圖2023/1/141狀態(tài)空間間搜索——2.一般圖搜搜索策略略（1）搜索術(shù)術(shù)語2、節(jié)點擴擴展應(yīng)用操作算子子將上一狀態(tài)態(tài)（節(jié)點ni）變遷到到下一狀態(tài)態(tài)（節(jié)點nj）節(jié)點ni稱為被擴展節(jié)節(jié)點（父節(jié)點點）節(jié)點nj稱為ni的子節(jié)點節(jié)點ni節(jié)點nj2023/1/142（1）搜索術(shù)術(shù)語3、路徑節(jié)點ni到nj的路徑是是由相鄰鄰節(jié)點間間的弧線構(gòu)成成的折線線要求路徑徑是無環(huán)環(huán)的4、路徑代代價——相鄰節(jié)點點ni和ni+1間的路徑代價價記為C(ni,ni+1)通常令任意相鄰鄰節(jié)點間間的路徑徑代價相相同，并以路路徑長度度1指示。即C(ni,ni+1)=1。狀態(tài)空間間搜索——2.一般圖搜搜索策略略節(jié)點ni節(jié)點ni+1節(jié)點nj2023/1/143狀態(tài)態(tài)空空間間搜搜索索———2.一般般圖圖搜搜索索策策略略（1）搜搜索索術(shù)術(shù)語語4、路路徑徑代代價價目標(biāo)標(biāo)狀狀態(tài)態(tài)節(jié)節(jié)點點ng節(jié)點點ni節(jié)點點nkC(nk,ng)C(ni,nk)C(ni,ng)2023/1/144狀態(tài)空空間搜搜索——2.一般圖圖搜索索策略略（2）一般般圖搜搜索算算法符號說說明：：s-初始狀狀態(tài)節(jié)節(jié)點G-搜索圖圖OPEN-存放待擴展展節(jié)點點的表CLOSE-存放已被擴擴展的的節(jié)點點的表MOVE-FIRST(OPEN)-取OPEN表首的的節(jié)點點作為當(dāng)前要要被擴擴展的的節(jié)點點n，同時時將節(jié)點點n移至CLOSE表一般圖圖搜索索算法法劃分分為二二個階階段：：1、初始始化2、搜索索循環(huán)環(huán)2023/1/145狀態(tài)空空間搜搜索——2.一般圖圖搜索索策略略（2）一般般圖搜搜索算算法算法劃劃分為為二個個階段段：1、初始始化建立只包含含初始始狀態(tài)態(tài)節(jié)點點s的搜索索圖G:={s}OPEN:={s}CLOSE:={}2、搜索索循環(huán)環(huán)MOVE-FIRST(OPEN)-取出OPEN表首的的節(jié)點點n作為擴擴展的的節(jié)點點，同同時將將其移移到close表擴展出出n的子節(jié)節(jié)點,插入搜索圖圖G和OPEN表適當(dāng)?shù)牡臉?biāo)記記和修修改指指針排序OPEN表通過循循環(huán)地地執(zhí)行行該算算法，，搜索圖圖G會因不不斷有有新節(jié)節(jié)點加加入而而逐步步長大大，直直到搜搜索到到目標(biāo)標(biāo)節(jié)點點。2023/1/146以下面的八數(shù)數(shù)碼為例，看看一般圖的搜搜索算法初始布局目標(biāo)布局移動數(shù)碼狀態(tài)空間搜索索——2.一般圖搜索策策略2023/1/1472023/1/1482023/1/1492023/1/1502023/1/1512023/1/1522023/1/1532023/1/1542023/1/1552023/1/1562023/1/1572023/1/1582023/1/1592023/1/1602023/1/1612023/1/1622023/1/1632023/1/1642023/1/1652023/1/166狀態(tài)態(tài)空空間間搜搜索索———2.一般般圖圖搜搜索索策策略略（2）一一般般圖圖搜搜索索算算法法———搜索索過過程程中中的的指指針針修修改改節(jié)點點n擴展展后后的子子節(jié)節(jié)點點分分為為3類：(i)全新新節(jié)節(jié)點點(ii)已出出現(xiàn)現(xiàn)在在OPEN表中的的節(jié)節(jié)點點(iii)已出現(xiàn)的CLOSE表中的節(jié)點指針標(biāo)記和和修改的方方法：(i)類節(jié)點：加加入OPEN表，建立從從子節(jié)點到到父節(jié)點n的指針(ii)類節(jié)點、(iii)類節(jié)點比較經(jīng)由老父節(jié)點、新父節(jié)點n到達初始狀態(tài)節(jié)節(jié)點的路徑代價經(jīng)由新父節(jié)節(jié)點n的代價比較較小，則將將原子節(jié)點點指向老父父節(jié)點的指指針，修改改為指向新新父節(jié)點n(iii)類節(jié)點還得得從CLOSE表中移出，，重新加入入OPEN表。2023/1/167狀態(tài)空間搜搜索——2.一般圖搜索索策略Sn4ninjn1n2n3n31n32節(jié)點ni是當(dāng)前擴展展的節(jié)點；；擴展出4個后續(xù)節(jié)點點；n1、n2是新節(jié)點，只需建立指指向父節(jié)點點的指針，，并加入OPEN表；2023/1/168狀態(tài)空間搜索索——2.一般圖搜索策策略Sn4ninjn1n2n3n31n32n4已經(jīng)存在于OPEN表，并且已有有父節(jié)點njn4經(jīng)nj的路徑代價大大取消n4指向nj的指針改為建立n4指向新父節(jié)點點ni的指針n3已經(jīng)存在于CLOSE表，并且已有有父節(jié)點nj需要做和n4同樣的比較和和指針修改工工作。并且要要重新加入open表。2023/1/169狀態(tài)空空間搜搜索——2.一般圖圖搜索索策略略（2）一般般圖搜搜索算算法OPEN表中節(jié)節(jié)點簡簡單的的排序序方式式：深度優(yōu)優(yōu)先——擴展當(dāng)當(dāng)前節(jié)節(jié)點后后生成成的子子節(jié)點點總是是置于OPEN表的前前端，即OPEN表作為棧，后進先先出，使搜索優(yōu)優(yōu)先向向縱深深方向向發(fā)展展。2023/1/170深度優(yōu)先實例例231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123468911131416181912384765目標(biāo)571012151720212023/1/171深度度優(yōu)優(yōu)先先搜搜索索在深深度度優(yōu)優(yōu)先先搜搜索索中中，，首首先先擴擴展展最最新新產(chǎn)產(chǎn)生生的的(最深深的的)節(jié)點點，，深深度度相相等等的的節(jié)節(jié)點點可可以以任任意意排排列列。?！白钔懋a(chǎn)產(chǎn)生的的節(jié)點點最先先擴展展”起始節(jié)節(jié)點深深度為為0任何其其他節(jié)節(jié)點的的深度度等于于其父父輩節(jié)節(jié)點深深度加加上1:dn=dn-1+12023/1/172深度優(yōu)優(yōu)先搜搜索很明顯顯這樣樣做，，不一定定找到最最佳解解，而而且由由于深深度的的限制制，可可能找找不到到解，，然而而，若若不加加深度度限制制，可可能沿沿著一一條路路線無無限制制地擴擴展下下去，，這當(dāng)當(dāng)然是是不允允許的的。為保證證找到到解，，應(yīng)選選擇適適當(dāng)?shù)牡纳疃冉缃缦?，或者者采取取不斷斷加大大深度度界限限的辦辦法，，反復(fù)復(fù)搜索索，直直到找找到解解。這這種改改進的的方法法叫做做迭代加加深搜搜索。2023/1/173ProcedureDepthFirstSearchBegin把初始始節(jié)點點壓入入棧，，并設(shè)設(shè)置棧棧頂指指針；；While棧不空空doBegin彈出棧棧頂元元素；；If棧頂元元素=goal，成功功返回回并結(jié)結(jié)束；；Else以任意意次序序把棧棧頂元元素的的子女女壓入入棧中中；EndWhileEnd基于棧棧實現(xiàn)現(xiàn)的深深度優(yōu)優(yōu)先搜搜索算算法：：2023/1/174初始節(jié)點點放到棧棧中，棧棧指針指指向棧的的最上邊邊的元素素。為了對該該節(jié)點進進行檢測測，需要要從棧中中彈出該該節(jié)點，，如果是是目標(biāo)，，該算法法結(jié)束，，否則把把其子節(jié)節(jié)點以任任何順序序壓入棧棧中。該該過程直直到棧變變成為空空。遍歷一棵樹的的過程（（下圖））。2023/1/175深度優(yōu)先搜索索的性質(zhì)一般不能保證證找到最優(yōu)解解當(dāng)深度限制不不合理時，可能找不到解解，可以將算法法改為可變深度限制制最壞情況時，，搜索空間等等同于窮舉是一個通用的的與問題無關(guān)關(guān)的方法2023/1/176深度優(yōu)先搜搜索的優(yōu)點是比寬度優(yōu)優(yōu)先搜索算算法需要較較少的空間間，該算法法只需要保保存搜索樹樹的一部分分，它由當(dāng)當(dāng)前正在搜搜索的路徑徑和該路徑徑上還沒有有完全展開開的節(jié)點標(biāo)標(biāo)志所組成成。深度優(yōu)先搜搜索的存儲儲器要求是是深度約束束的線性函函數(shù)。深度優(yōu)先搜搜索的優(yōu)點點2023/1/177深度度優(yōu)優(yōu)先先搜搜索索的的缺缺點點既不不是是完完備備的的，，也也不不是是最最優(yōu)優(yōu)的的。。主要要問問題題是是可可能能搜搜索索到到了了錯錯誤誤的的路路徑徑上上。。很很多多問問題題可可能能具具有有很很深深甚甚至至是是無無限限的的搜搜索索樹樹，，如如果果不不幸幸選選擇擇了了一一個個錯錯誤誤的的路路徑徑，，則則深深度度優(yōu)優(yōu)先先搜搜索索會會一一直直搜搜索索下下去去，，而而不不會會回回到到正正確確的的路路徑徑上上。。這這樣樣一一來來對對于于這這些些問問題題，，深深度度優(yōu)優(yōu)先先搜搜索索要要么么陷陷入入無無限限的的循循環(huán)環(huán)而而不不能能給給出出一一個個答答案案，，要要么么最最后后找找到到一一個個答答案案，，但但路路徑徑很很長長而而且且不不是是最最優(yōu)優(yōu)的的答答案案。。2023/1/178狀態(tài)空間搜索索——2.一般圖搜索策策略（2）一般圖搜索索算法OPEN表中節(jié)點簡單單的排序方式式：深度優(yōu)先——擴展當(dāng)前節(jié)點點后生成的子子節(jié)點總是置于OPEN表的前端，即OPEN表作為棧，后進先出，使搜索優(yōu)先向縱縱深方向發(fā)展展。寬度優(yōu)先——擴展當(dāng)前節(jié)點點后生成的子子節(jié)點總是置于OPEN表的后端，即OPEN表作為隊列，先進先出，使搜索優(yōu)先向橫橫向方向發(fā)展展。2023/1/179寬度優(yōu)先實例例23184765283147652318476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)8234187654910111213141516172023/1/180寬度優(yōu)優(yōu)先搜搜索如果搜搜索是是以接接近起起始節(jié)節(jié)點的的程度度依次次擴展展節(jié)點點的，，那么么這種種搜索索就叫叫做寬度優(yōu)優(yōu)先搜搜索。。這種搜搜索是是逐層層進行行的，，在對對下一一層的的任意意節(jié)點點進行行搜索索之前前，必必須搜搜索完完本層層的所所有節(jié)節(jié)點。。“先產(chǎn)產(chǎn)生的的節(jié)點點先擴擴展””2023/1/181ProcedureBreadth-first-searchBegin把初始始節(jié)點點放入入隊列列；Repeat取得隊隊列最最前面面的元元素為為current;Ifcurrent=goal成功返返回并并結(jié)束束；ElsedoBegin如果current有子女女，則則current的子女女以任意意次序序添加加到隊隊列的的尾部部；EndUntil隊列為為空End采用隊隊列結(jié)結(jié)構(gòu)，，寬度度優(yōu)先先算法法可以以表示示如下下：2023/1/182寬度優(yōu)先搜搜索算法原原理：如果當(dāng)前的的節(jié)點不是是目標(biāo)節(jié)點點，則把當(dāng)當(dāng)點節(jié)點的的子孫以任任意順序增增加到隊列列的后面，，并把隊列列的前端元元素定義為為current。如果目標(biāo)發(fā)發(fā)現(xiàn)，則算算法終止。。2023/1/183寬度優(yōu)先搜搜索的性質(zhì)質(zhì)當(dāng)問題有解解時，一定能找到解當(dāng)問題為單單位代價時時，且問題題有解時，，一定能找到到最優(yōu)解方法與問題題無關(guān)，具具有通用性性效率較低屬于圖搜索索方法2023/1/184寬度優(yōu)先先搜索是一種盲盲目搜索索，時間間和空間間復(fù)雜度度都比較較高，當(dāng)當(dāng)目標(biāo)節(jié)節(jié)點距離離初始節(jié)節(jié)點較遠遠時會產(chǎn)產(chǎn)生許多多無用的的節(jié)點，，搜索效效率低。。寬度優(yōu)先先搜索中中，時間間需求是是一個很很大的問問題，特特別是當(dāng)當(dāng)搜索的的深度比比較大時時，尤為為嚴(yán)重，，但是空空間需求求是比執(zhí)執(zhí)行時間間更嚴(yán)重重的問題題。寬度優(yōu)先先搜索優(yōu)優(yōu)點：目標(biāo)節(jié)點點如果存存在，用用寬度優(yōu)優(yōu)先搜索索算法總總可以找找到該目目標(biāo)節(jié)點點，而且且是最小?。醋钭疃搪窂綇剑┑墓?jié)節(jié)點。寬度優(yōu)先先搜索的的優(yōu)點和和缺點2023/1/185總結(jié)適用場場合深度優(yōu)優(yōu)先——當(dāng)一個個問題題有多多個解解答或或多條條解答答路徑徑，且且只須須找到到其中中一個個時；；往往往應(yīng)對對搜索索深度度加以以限制制。寬度優(yōu)優(yōu)先——確保搜搜索到到最短短的解解答路路徑。。共同優(yōu)優(yōu)缺點點：可直接接應(yīng)用用一般般圖搜搜索算算法實實現(xiàn)，，不需需要設(shè)設(shè)計特特別的的節(jié)點點排序序方法法，從從而簡簡單易易行，，適合合于許許多復(fù)復(fù)雜度度不高高的問問題求求解任任務(wù)。。節(jié)點排排序的的盲目目性，，由于于不采采用領(lǐng)領(lǐng)域?qū)ｉT知知識去去指導(dǎo)導(dǎo)排序序，往往往會會在白白白搜搜索了了大量量無關(guān)關(guān)的狀狀態(tài)節(jié)節(jié)點后后才碰碰到解解答，，所以以也稱稱為盲目搜搜索。2023/1/186有界深度搜搜索和迭代代加深搜索索有界深度優(yōu)優(yōu)先搜索過程總體上上按深度優(yōu)優(yōu)先算法方方法進行，，但對搜索索深度需要要給出一個個深度限制制dm，當(dāng)深度達達到了dm的時候，如如果還沒有有找到解答答，就停止止對該分支支的搜索，，換到另外外一個分支支進行搜索索。2023/1/187策略說明:（1）深度限制dm很重要。當(dāng)問題有解，，且解的路徑徑長度小于或或等于dm時，則搜索過過程一定能夠夠找到解，但但是和深度優(yōu)優(yōu)先搜索一樣樣這并不能保保證最先找到到的是最優(yōu)解解。但是當(dāng)dm取得太小，解解的路徑長度度大于dm時，則搜索過過程中就找不不到解，即這這時搜索過程程甚至是不完完備的。2023/1/188（2）深度限限制dm不能太太大。當(dāng)dm太大時時，搜搜索過過程會會產(chǎn)生生過多多的無無用節(jié)節(jié)點，，既浪浪費了了計算算機資資源，，又降降低了了搜索索效率率。（3）有界界深度度搜索索的主主要問問題是是深度限限制值值dm的選取取。2023/1/189改進方法法：（迭迭代加深深搜索））先任意給給定一個個較小的的數(shù)作為為dm，然后按按有界深深度算法法搜索，，若在此此深度限限制內(nèi)找找到了解解，則算算法結(jié)束束；如在在此限制制內(nèi)沒有有找到問問題的解解，則增增大深度度限制dm，繼續(xù)搜搜索。2023/1/190迭代加深搜索索，試圖嘗試所所有可能的深深度限制：首先深度為0，然后深度為1，然后為2，等等。如果初始深度度為0，則該算法只只生成根節(jié)點點，并檢測它它。如果根節(jié)點不不是目標(biāo)，則則深度加1，通過典型的的深度優(yōu)先算算法，生成深深度為1的樹。當(dāng)深度限制為為m時，樹的深度度為m。2023/1/191迭代加深搜索索看起來會很很浪費，因為為很多節(jié)點都都可能擴展多多次。然而對于很多多問題，這種種多次的擴展展負擔(dān)實際上上很小，直覺覺上可以想象象，如果一棵棵樹的分支系系數(shù)很大，幾幾乎所有的節(jié)節(jié)點都在最底底層上，則對對于上面各層層節(jié)點擴展多多次對整個系系統(tǒng)來說影響響不是很大。。2023/1/192搜索最優(yōu)策略略的比較表注：b是分支系數(shù)，，d是解答的深度度，m是搜索樹的最最大深度，l是深度限制。。2023/1/193寬度優(yōu)先搜索索、深度優(yōu)先先搜索和迭代代加深搜索都都可以用于生生成和測試算算法。寬度度優(yōu)優(yōu)先先搜搜索索需要要指指數(shù)數(shù)數(shù)數(shù)量量的的空空間間，，深深度度優(yōu)優(yōu)先先搜搜索索的的空空間間復(fù)復(fù)雜雜度度和和最最大大搜搜索索深深度度呈呈線線性性關(guān)關(guān)系系。。2023/1/194迭代加深深搜索對一棵深深度受控控的樹采采用深度度優(yōu)先的的搜索。。它結(jié)合合了寬度度優(yōu)先和和深度優(yōu)優(yōu)先搜索索的優(yōu)點點。和寬度優(yōu)優(yōu)先搜索索一樣，，它是最最優(yōu)的，，也是完完備的。。但對空空間要求求和深度度優(yōu)先搜搜索一樣樣是適中中的。2023/1/195一般圖搜搜索算法法常用的簡簡單方式式：深度優(yōu)先先寬度優(yōu)先先【缺點：節(jié)節(jié)點排序序的盲目目性】在白白搜索了大大量無關(guān)關(guān)的狀態(tài)態(tài)節(jié)點后才碰到到解答，，效率低提高一般圖搜搜索效率的關(guān)鍵優(yōu)化OPEN表中節(jié)點點的排序序方式盲目搜索索3.4啟發(fā)式搜搜索★2023/1/196125634最理想情情況：每次排序序后OPEN表表首元素素n總在解答答路徑上上2023/1/197啟發(fā)式搜索索啟發(fā)式知識識指導(dǎo)OPEN表排序的一般圖搜索索：全局排序——對OPEN表中的所有節(jié)點排排序，使最有希望的節(jié)點排在在表首。A算法，A*算法（掌握握！）局部排序——僅對新擴展出來的的子節(jié)點排排序，使這些新節(jié)點中最有希望者能優(yōu)先取取出考察和和擴展；爬山法（了了解，對深度優(yōu)先法法的改進）；2023/1/198啟發(fā)式搜索索——1.A算法（掌握）【基本思想】設(shè)計體現(xiàn)啟啟發(fā)式知識識的評價函數(shù)f(n)；指導(dǎo)一般圖搜索索中OPEN表待擴展節(jié)節(jié)點的排序序：【評價函數(shù)f(n)=g(n)+h(n)（掌握）】n-搜索圖G中的節(jié)點；f(n)-G中從初始狀狀態(tài)節(jié)點s，經(jīng)由節(jié)點點n到達目標(biāo)節(jié)節(jié)點ng，估計的最小路徑代代價；g(n)-G中從s到n，目前實際的路徑代價價；h(n)-從n到ng，估計的最小路徑徑代價；2023/1/199啟發(fā)式搜索索——1.A算法（掌握）Snng目標(biāo)狀態(tài)節(jié)節(jié)點ng初始狀態(tài)節(jié)節(jié)點S節(jié)點n搜索圖Gh(n):n-ng的估計最小小路徑代價價g(n):s-n的實際路徑徑代價f(n):s-n-ng的估計最小路徑代代價2023/1/1100啟發(fā)發(fā)式式搜搜索索———1.A算法法（（掌握握）【評價價函函數(shù)數(shù)f(n)=g(n)+h(n)（掌掌握握））】n-搜索索圖圖G中的節(jié)節(jié)點點；f(n)-G中從從s經(jīng)n到ng，估計計的最小小路路徑徑代代價價；g(n)-G中從從s到n，目前實實際的路徑徑代價價；h(n)-從n到ng，估計的最小路路徑代代價；h(n)值-依賴于于啟發(fā)式式知識識加以計計算；；h(n)稱為啟發(fā)式式函數(shù)數(shù)（掌握意意義?。。?。如何用用評價價函數(shù)數(shù)來實實現(xiàn)A算法?（掌握?。。?023/1/1101啟發(fā)式式搜索索——1.A算法（（掌握）A算法的設(shè)計計與一般圖圖搜索索相同，，劃分分為二二個階階段：：1、初始始化建立只只包含含初始始狀態(tài)態(tài)節(jié)點點s的搜索索圖G:={s}OPEN:={s}CLOSE:={}2、搜索索循環(huán)環(huán)MOVE-FIRST(OPEN)-取出OPEN表首的節(jié)點點n⑥擴展出出n的子節(jié)節(jié)點,插入搜搜索圖圖G和OPEN表⑦適當(dāng)?shù)牡臉?biāo)記記和修修改指指針（（子節(jié)點點父節(jié)節(jié)點）⑧排序OPEN表（評價函函數(shù)f(n)的值排排序））通過循循環(huán)地地執(zhí)行行該算算法，，搜索索圖會會因不不斷有有新節(jié)節(jié)點加加入而而逐步步長大大，直直到搜搜索到到目標(biāo)標(biāo)節(jié)點點。2023/1/1102啟發(fā)式搜搜索——1.A算法（掌握）算法A的設(shè)計與與一般圖圖搜索類類似，劃劃分為二二個階段段：1、初始化化2、搜索循循環(huán)MOVE-FIRST(OPEN)-取出OPEN表首的節(jié)節(jié)點n⑥擴展出n的子節(jié)點點,插入搜索索圖G和OPEN表對每個子子節(jié)點ni,計算f(n,ni)=g(n,ni)+h(ni)⑦適當(dāng)?shù)臉?biāo)標(biāo)記和修修改指針針（子節(jié)點父節(jié)點點）⑧排序OPEN表（評價函函數(shù)f(n)的值排序序）2023/1/1103啟發(fā)式搜搜索——1.A算法（掌握）⑥擴展出n的子節(jié)點點,插入搜索索圖G和OPEN表對每個子子節(jié)點ni,計算f(n,ni)=g(n,ni)+h(ni)⑦適當(dāng)?shù)臉?biāo)標(biāo)記和修修改指針針（子節(jié)點父節(jié)點點）(i)全新節(jié)點點：f(ni)=f(n,ni)(ii)已出現(xiàn)在在OPEN表中的節(jié)點點(iii)已出現(xiàn)的的CLOSE表中的節(jié)點點IFf(ni)>f(n,ni)THEN修改指針針指向新父結(jié)點nf(ni)=f(n,ni)⑧排序OPEN表（f(n)值從小到到大排序序）2023/1/11042.若OPEN表是空表表，則失失敗退出出；算法A3.選擇擇OPEN表上上的的第第一一個個節(jié)節(jié)點點，，把把它它從從OPEN表移移出出并并放放進進CLOSE表中中，，稱稱此此節(jié)節(jié)點點為為節(jié)節(jié)點點n；1.建立立一一個個只包包含含起起始始節(jié)節(jié)點點S的搜搜索索圖圖G,把S放到到一一個個叫叫OPEN的未未擴擴展展節(jié)節(jié)點點表表中中；；建建立立一一個個叫叫做做CLOSE的已已擴擴展展節(jié)節(jié)點點表表，，其其初初始始為為空空表表；；5.擴展展節(jié)節(jié)點點n，同同時時生生成成不不是是n的祖祖先先的的那那些些子子節(jié)節(jié)點點的的集集合合M,把M的這這些些成成員員作作為為n的后后繼繼節(jié)節(jié)點點添添入入圖圖G中；；對于于M中每每個個子子節(jié)節(jié)點點ni,計算算f(n,ni)=g(n,ni)+h(ni);4.若n為一一目目標(biāo)標(biāo)節(jié)節(jié)點點，，則則有有解解成成功功退退出出，，此此解解是是追追蹤蹤圖圖G中沿沿著著指指針針從從n到S這條條路路徑徑而而得得到到的的；；2023/1/11056.對那那些些未未曾曾在在G中出出現(xiàn)現(xiàn)過過的的M成員員（（全全新新節(jié)節(jié)點點））設(shè)設(shè)置置一一個個通通向向n的指指針針。。把把M的這這些些成成員員加加進進OPEN表。。對對已已經(jīng)經(jīng)在在OPEN表上上的的每每一一個個M成員員，，比較較子子節(jié)節(jié)點點ni經(jīng)由由新新、、老老父父節(jié)節(jié)點點的的評評價價函函數(shù)數(shù)值值f(n,ni)、f(ni);若f(n,ni)<f(ni)點,則令f(ni)=f(n,ni),并移動動子節(jié)節(jié)點指指向老老父節(jié)節(jié)點的的指針針，改改為指指向新新父節(jié)節(jié)點。。對已已在在CLOSE表上上的的每每個個M成員員，，作作與與第第2類同同樣樣的的處處理理，，并并把把這這些些子子結(jié)結(jié)點點從從CLOSE表移出，，重新加加入OPEN表。7.按f(n)排序OPEN表中的節(jié)節(jié)點，f(n)值最小者者排在首首位，重排OPEN表；8.轉(zhuǎn)2。此過程生生成一個個明確的的圖G(搜索圖））和一個個G的子集T(搜索樹））。2023/1/1106啟發(fā)式搜搜索——1.A算法（掌握）A算法實例例——八數(shù)碼游游戲1)設(shè)計評價價函數(shù)f(n)f(n)=d(n)+w(n),其中d(n)-節(jié)點n在搜索圖圖中的節(jié)點深度度，對g(n)的度量；w(n)-代表啟發(fā)發(fā)式函數(shù)數(shù)h(n),其值是節(jié)節(jié)點n與目標(biāo)狀狀態(tài)節(jié)點點ng相比較，，不考慮慮空格，，錯位的棋棋牌個數(shù)數(shù)；初始布局目標(biāo)布局移動數(shù)碼2023/1/1107啟發(fā)式搜搜索——1.A算法（掌握）啟發(fā)式算算法A實例——八數(shù)碼游游戲1)設(shè)計評價價函數(shù)f(n)f(n)計算實例例初始布局局s目標(biāo)布局局ngw(s):錯位的棋棋牌個數(shù)數(shù)d(s):當(dāng)前節(jié)點點深度f(s)h(n):n-ng的最小路路徑代價價g(n):s-n的最小路路徑代價價f(n):s-n-ng的最小路路徑代價價注：W(S)不考慮空空格2023/1/1108狀態(tài)空間搜索索——2.一般圖搜索策策略（1）搜索術(shù)語1、節(jié)點深度根節(jié)點指示初始狀態(tài)，令其深度為為0；搜索圖中的其其他節(jié)點的深度dn就可以遞歸地地定義為其父節(jié)點深度dn-1加1：dn=dn-1+1。根節(jié)點深度=0第n-1層節(jié)點dn-1第n層節(jié)點dn=dn-1+1搜索圖G2023/1/1109啟發(fā)式搜索——1.A算法（掌握）啟發(fā)式算法A實例——八數(shù)碼游戲1)設(shè)計評價函數(shù)數(shù)f(n)f(n)計算實例初始布局s目標(biāo)布局ngw(s):錯位的棋牌個個數(shù)d(s):當(dāng)前節(jié)點深度度f(s)h(n):n-ng的最小路徑代代價g(n):s-n的最小路徑代代價f(n):s-n-ng的最最小小路路徑徑代代價價044注：：W(S)不考考慮慮空空格格2023/1/1110初始始化化OPEN:={s4}CLOSE:={}2023/1/1111循環(huán)1CLOSE:={s4}OPEN:={abc}OPEN:={a6b4c6}OPEN:={b4a6c6}2023/1/1112循環(huán)2CLOSE:={s4b4}OPEN:={a6c6dei}OPEN:={a6c6d5e5i6}OPEN:={d5e5a6c6i6}2023/1/1113循環(huán)3CLOSE:={s4b4d5}OPEN:={e5a6c6i6jk}OPEN:={e5a6c6i6j7k6}OPEN:={e5a6c6i6k6j7}2023/1/1114循環(huán)4CLOSE:={s4,b4,d5,e5}OPEN:={a6c6i6k6j7lm}OPEN:={a6c6i6k6j7l5m7}OPEN:={l5a6c6i6k6j7m7}2023/1/1115CLOSE:={s4,b4,d5,e5,l5}循環(huán)5OPEN:={a6c6i6k6j7m7n}OPEN:={a6c6i6k6j7m7n5}OPEN:={n5a6c6i6k6j7m7}2023/1/1116循環(huán)6CLOSE:={s4,b4,d5,e5,l5,n5}OPEN:={a6c6i6k6j7m7og}OPEN:={a6c6i6k6j7m7o7g5}OPEN:={g5a6c6i6k6j7m7o7}2023/1/1117循環(huán)7成功結(jié)結(jié)束2023/1/1118最理想想搜索索圖G2023/1/1119判斷失失誤2023/1/1120例2給定4L和3L的水壺壺各一一個，，水壺壺上沒沒有刻刻度，，可以以向水水壺中中加水水。如何在在4L的壺中中準(zhǔn)確確地得得到2L水？（x,y）——4L壺里的的水有有xL，3L壺里的的水有有yL，n表示搜搜索空空間中中的任任一節(jié)節(jié)點。。則給出出下面面的啟啟發(fā)式式函數(shù)數(shù)：2023/1/1121h(n)=2如果果0<x<4并且且0<y<3=4如果果0<x<4或者者0<y<3=8如果果x=0并且且y=3或者者x=4并且且y=0=10如果果x=0并且且y=0或者者x=4并且且y=3假定定g(n)表示示搜搜索索樹樹中中搜搜索索的的深深度度，，則則根根據(jù)據(jù)圖圖搜搜索索策策略略得得下下圖圖的的搜搜索索空空間間。。2023/1/1122水壺壺問問題題的的狀狀態(tài)態(tài)空空間間擴擴展展圖圖在第第0步，，由由節(jié)節(jié)點點O可以以得得到到g+h=10。在第第1步，，得得到到兩兩個個節(jié)節(jié)點點M和N，其其估估價價函函數(shù)數(shù)值值都都為為1+8=9，因因此此可可以以任任選選一一個個節(jié)節(jié)點點擴擴展展。。2023/1/1123水壺壺問問題題的的狀狀態(tài)態(tài)空空間間擴擴展展圖圖假定定選選擇擇了了節(jié)節(jié)點點M，在在第第2步擴擴展展M得到到了了兩兩個個后后繼繼點點P和R，對對于于P有2+4=6，對對于于R有2+10=12?，F(xiàn)現(xiàn)在在，，在在節(jié)節(jié)點點P、R、N中，節(jié)節(jié)點P具有最最小的的估價價函數(shù)數(shù)值，，所以以選擇擇節(jié)點點P擴展。。在第3步，可可以得得到節(jié)節(jié)點S，其中中3+4=7?，F(xiàn)在在，在在節(jié)點點S、R、N中，節(jié)節(jié)點S的估價價函數(shù)數(shù)值最最小，，所以以下一一步就就會選選擇S節(jié)點擴擴展。。該過過程一一直進進行下下去，，直到到到達達目標(biāo)標(biāo)節(jié)點點。2023/1/1124啟發(fā)式式搜索索——2.實現(xiàn)啟啟發(fā)式式搜索索的關(guān)關(guān)鍵因因素（（理解解）實現(xiàn)啟啟發(fā)式式搜索索應(yīng)考考慮的的關(guān)鍵鍵因素素：（1）搜索索算法法的可采納納性(Admissibility);（2）啟發(fā)式式函數(shù)數(shù)h(n)的強弱弱及其影影響；；2023/1/1125啟發(fā)式式搜索索——2.實現(xiàn)啟啟發(fā)式式搜索索的關(guān)關(guān)鍵因因素（1）搜索索算法法的可可采納納性(Admissibility)1)定義在存在從初始狀狀態(tài)節(jié)點到到目標(biāo)狀狀態(tài)節(jié)點解答路路徑的情況況下，，若一一個搜搜索法法總能找找到最最短（（代價價最小?。┑牡慕獯鸫鹇窂綇剑瑒t稱稱該狀態(tài)空空間中的搜索算算法具有可可采納納性，，也叫叫最優(yōu)優(yōu)性。如，寬度優(yōu)優(yōu)先的搜索索算法法是可采納納的，只是是搜索索效率不不高。2)A算法的的可采采納性性——定義f*(n)=g*(n)+h*(n)n-搜索圖圖G中最短解解答路路徑的節(jié)點點；f*(n)-s經(jīng)節(jié)點點n到ng的最短解解答路路徑的路徑徑代價價；g*(n)-該路徑徑前段（從s到n）的路路徑代代價；；h*(n)-該路徑徑后段（從n到ng）的路路徑代代價；；2023/1/1126啟發(fā)式式搜索索——2.實現(xiàn)啟啟發(fā)式式搜索索的關(guān)關(guān)鍵因因素（1）搜索索算法法的可可采納納性(Admissibility)3)評價函函數(shù)f與f*的比較較f(n)、g(n)、h(n)分別是是f*(n)、g*(n)、h*(n)的近似值值（估估計值值）理想情情況下下：若g(n)=g*(n)、h(n)=h*(n)，則搜索索過程程中，，每次都都正確確選擇擇，不擴展展任何何無關(guān)關(guān)的節(jié)節(jié)點。實際情情況：：設(shè)計接接近f*的f是很困困難的的在算法執(zhí)執(zhí)行過程程中，g(n)容易從已已經(jīng)生成成的搜索索樹中計計算出來來Sn搜索圖Gng2023/1/1127啟發(fā)式搜搜索——2.實現(xiàn)啟發(fā)發(fā)式搜索索的關(guān)鍵鍵因素（1）搜索算算法的可可采納性性(Admissibility)3)評價函數(shù)數(shù)f與f*的比價理想情況況下：若g(n)=g*(n)、h(n)=h*(n)，不擴展無無關(guān)的節(jié)節(jié)點實際情況況：設(shè)計接近近f*的f是很困難難的在算法執(zhí)執(zhí)行過程程中，g(n)容易從已已經(jīng)生成成的搜索索樹中計計算出來來，比如如就以節(jié)節(jié)點深度度d(n)當(dāng)做g(n),且有g(shù)(n)>=g*(n)h(n