人工智能 第三章 基本的問題求解方法課件

第三章基本的問題求解方法問題求解的過程：1）知識表示；2）針對問題，分析特征，選擇合適的方法來求解（包括搜索和推理）方法： 1）基于狀態(tài)圖方法-搜索； 2）基于謂詞邏輯方法-推理； 3）基于結(jié)構(gòu)化的知識表示方法來求解問題；本章介紹搜索技術(shù)第三章基本的問題求解方法問題求解的過程：1）知識表示；2）1搜索技術(shù)是人工智能的基本技術(shù)之一,在人工智能各應(yīng)用領(lǐng)域中被廣泛地使用。早期的人工智能程序與搜索技術(shù)聯(lián)系就更為緊密，幾乎所有的早期的人工智能程序都是以搜索為基礎(chǔ)的。A.Newell和H·A·Simon-LT程序A·Newell和H·A·Simon-GPS(GeneralProblemSolver)R.Fikes和N.Nilsson-STRIPS(StanfordResearchInstituteProblemSolver)現(xiàn)在,搜索技術(shù)滲透在各種人工智能系統(tǒng)中,在專家系統(tǒng)、自然語言理解、自動程序設(shè)計、模式識別、機器人學(xué)、信息檢索和博奕都廣泛使用。搜索技術(shù)是人工智能的基本技術(shù)之一,在人工智能各應(yīng)用領(lǐng)域中被2搜索(search)路徑狀態(tài)序列搜索尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑;S0Sg搜索(search)路徑S0Sg3搜索的必要性AI為什么要研究search?問題沒有直接的解法;解方程組;定理證明;需要探索地求解;搜索的必要性AI為什么要研究search?4搜索與檢索的區(qū)別狀態(tài)是否動態(tài)生成;檢索:靜態(tài);在數(shù)據(jù)庫中檢索某人的紀(jì)錄;搜索:動態(tài)生成;下棋搜索與檢索的區(qū)別狀態(tài)是否動態(tài)生成;5幾個問題目標(biāo)狀態(tài)是否確定?確定:定理證明,eight-puzzle不確定:求積分,下棋;確定目標(biāo)的性質(zhì);問題的解:路徑(解路徑)/目標(biāo)狀態(tài);需要路徑:下棋

不需要路徑:電路設(shè)計

需要/不需要:診病約束條件目標(biāo)狀態(tài)不確定時,用來約束目標(biāo)狀態(tài)的性質(zhì);X+Y=4:非整數(shù)解/整數(shù)解幾個問題目標(biāo)狀態(tài)是否確定?6幾個問題(續(xù)1)多解性;X+Y=4:整數(shù)解最優(yōu)解評價標(biāo)準(zhǔn)/判斷準(zhǔn)則;min(x*y)北京->上海:時間最短/費用最少最優(yōu)解是否唯一?下棋幾個問題(續(xù)1)多解性;7搜索問題狀態(tài)空間237

5148612384765搜索問題狀態(tài)空間237

51486123847658搜索不是檢索237

5148612384765搜索不是檢索237

51486123847659難點237

5148612384765難點237

514861238476510啟發(fā)式方法237

5148612384765啟發(fā)式方法237

514861238476511搜索方法的評價標(biāo)準(zhǔn)

搜索問題是AI核心理論問題之一。一般一個問題可以用好幾種搜索技術(shù)解決,選擇一種好的搜索技術(shù)對解決問題的效率很有關(guān)系,甚至關(guān)系到求解問題有沒有解。

搜索方法好的標(biāo)準(zhǔn),一般認為有兩個：

(1)搜索空間小;

(2)解最佳。搜索方法的評價標(biāo)準(zhǔn)

搜索問題是AI核心理論問題之一。一般一個12搜索分類搜索從問題性質(zhì)上來看,可分為一般搜索和博奕搜索,從處理方法上來看,可分為盲目搜索和啟發(fā)式搜索。還可以分得更細。到目前為止,AI領(lǐng)域中已提出許多具體的搜索方法,概括起來有：

(1)求任一解路的搜索策略

回溯法；爬山法(HillClimbing)；寬度優(yōu)先法(Breadth-first)；深度優(yōu)先法(Depth-first)

(2)求最佳解路的搜索策略

大英博物館法(BritishMuseum)；最佳圖搜索法(A*)

(3)求與或關(guān)系解圖的搜索法

一般與或圖搜索法(AO*)；極小極大法(Minimax)

剪枝法(Alpha-betaPruning)；啟發(fā)式剪枝法(HeuristicPruning)搜索分類搜索從問題性質(zhì)上來看,可分為一般搜索和博奕搜索,13人工智能第三章基本的問題求解方法14TOPICS回溯策略（Backtracking

）圖搜索（GRAPHSEARCH）無信息搜索啟發(fā)式搜索TOPICS回溯策略（Backtracking）15TOPIC1BacktrackingN1N0N2N3N4N5回溯策略TOPIC1BacktrackingN1N0N2N316例：四皇后問題例：四皇后問題17()()18()Q((1,1))()Q((1,1))19()QQ((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))20()Q((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))21()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,122()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,123()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,124()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()Q((1,1))((1,1)(2,3))((1,1)25()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)26()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))()((1,1))((1,1)(2,3))((1,1)27()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))()((1,1))((1,1)(2,3))((1,1)28()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))()((1,1))((1,1)(2,3))((1,1)29QQQQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1,2)(2,4)(3,1))((1,2)(2,4)(3,1)(4,3))QQQQ()((1,1))((1,1)(2,3))((130存在問題及解決辦法問題和解決方法：深度問題對搜索深度加以限制死循環(huán)問題狀態(tài)重復(fù):A→B，B→C,C→A記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑存在問題及解決辦法問題和解決方法：31TOPIC2GRAPHSEARCH圖搜索策略問題的引出回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。圖搜索：保留所有已經(jīng)搜索過的路徑。

N5N1N0N2

N3

N4TOPIC2GRAPHSEARCH圖搜索策略N5N132一些基本概念圖：一個節(jié)點的集合。節(jié)點由弧連接起來。

有向圖：弧是一個節(jié)點指向另一個節(jié)點的圖，稱為有向圖。

后繼/父親：如果有一條弧從ni指向nj，則nj稱為ni的后繼，ni稱為nj的父輩（父親）；

一些基本概念圖：一個節(jié)點的集合。節(jié)點由弧連接起來。33一些基本概念(續(xù)1)路徑：如果存在一個節(jié)點序列（ni0，ni1，……，nik），nij是nij-1是的后繼，j=1，……，k，則稱這個序列是從節(jié)點ni0到節(jié)點nik的一條路徑，長度為k。祖先/后裔：如果存在一條從ni到nj的路徑，則稱nj是ni的后裔，ni稱為nj的祖先。樹：每個節(jié)點最多只有一個父輩。沒有父輩的節(jié)點稱為根節(jié)點。沒有后繼的節(jié)點稱為葉節(jié)點。

一些基本概念(續(xù)1)路徑：如果存在一個節(jié)點序列（ni0，ni34一些基本概念(續(xù)2)節(jié)點深度： 根節(jié)點深度=0 其它節(jié)點深度=父節(jié)點深度+10123一些基本概念(續(xù)2)節(jié)點深度：012335一些基本概念（續(xù)3）擴展一個節(jié)點生成出該節(jié)點的所有后繼節(jié)點?；〉馁M用有一條弧連接ni和nj兩個節(jié)點,用C(ni,nj)表示使用規(guī)則從ni到nj的費用(耗散值)。玉泉路---天安門路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。一些基本概念（續(xù)3）擴展一個節(jié)點36GRAPHSEARCH的思路OPEN表已經(jīng)生成但未擴展節(jié)點CLOSED表已擴展節(jié)點擴展節(jié)點i生成節(jié)點j指針

調(diào)整指針GRAPHSEARCH的思路OPEN表37圖搜索（GraphSearch）的一般過程

1、建立一個只有起始節(jié)點S的搜索圖G，把S放入一個叫open的未擴展節(jié)點表；2、

建立已擴展節(jié)點表closed，初始為空；3、

LOOP；若open為空，則失敗退出；4、

選open表中的第一個節(jié)點，設(shè)為n，移入closed表；5、若n為目標(biāo)節(jié)點，則成功退出，該問題的解即是G中沿S指向n的路徑；6、若不是目標(biāo)節(jié)點，則擴展n，生成不是n的祖先的那些后繼節(jié)點的集合m，把m的成員作為n的后繼加入G中；7、對未曾在G中出現(xiàn)過的m成員，設(shè)一通向n的指針，把它們加入open表。對已在closed或open表上的m成員，確定是否要更改到n的指針方向，對已在closed上的m成員，確定是否要更改G中通向每個后裔節(jié)點的指針方向。8、按某一方式（深度優(yōu)先、寬度優(yōu)先、A*算法）重排open表9、GOLOOP圖搜索（GraphSearch）的一般過程1、建立一個只38例子SOPENCLOSE{S}{}123{}{S}{1,2,3}{S}{2,1,3}{S}45{1,3}{S,2}{1,3,4,5}{S,2}{3,1,4,5}{S,2}{1,4,5}{S,2,3}6{1,4,5,6}{S,2,3}例子SOPENCLOSE{S}{}123{}{S}39例：右圖中黑節(jié)點表示已擴展，白節(jié)點表示未擴展，問題：先擴展6號節(jié)點生成m1={4，7}，然后擴展節(jié)點1，生成m2={2}，按算法第七步重新修改原圖。612453難點?。?！算法中第七步7例：右圖中黑節(jié)點表示已擴展，白節(jié)點表示未擴展，問題：先擴展640擴展節(jié)點6生成m1={4，7}的調(diào)整61245371235467×擴展節(jié)點6生成m1={4，7}的調(diào)整61245371235441再擴展節(jié)點1生成m2={2}的調(diào)整12354671235467××再擴展節(jié)點1生成m2={2}的調(diào)整123546712354642最終結(jié)果61245371235467最終結(jié)果6124537123546743圖搜索與回溯算法的區(qū)別

擴展節(jié)點:回溯算法:生成一個兒子節(jié)點.

圖搜索:擴展節(jié)點,生成所有兒子節(jié)點.

候選節(jié)點:回溯算法:一個.

圖搜索:多個.

回溯:回溯算法:返回父親節(jié)點.

圖搜索:不一定返回父親節(jié)點.圖搜索與回溯算法的區(qū)別擴展節(jié)點:44TOPIC3無信息搜索如果在GRAPHSEARCH中，對節(jié)點的排序不使用與問題相關(guān)的信息，則稱為無信息圖搜索（盲目搜索）寬度優(yōu)先和深度優(yōu)先TOPIC3無信息搜索如果在GRAPHSEARCH中，對節(jié)451、breadth-firstsearch寬度優(yōu)先搜索：如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的。

搜索逐層進行；在對下一層的任一節(jié)點進行搜索之前，必須搜索完本層的所有節(jié)點。1、breadth-firstsearch寬度優(yōu)先搜索：如46(1)把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標(biāo)節(jié)點，則求得一個解答)。(2)如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。(3)把第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED的擴展節(jié)點表中。(4)擴展節(jié)點n。如果沒有后繼節(jié)點，則轉(zhuǎn)向上述第(2)步。(5)把n的所有后繼節(jié)點放到OPEN表的末端，并提供從這些后繼節(jié)點回到n的指針。(6)如果n的任一個后繼節(jié)點是個目標(biāo)節(jié)點，則找到一個解答，成功退出；否則轉(zhuǎn)向第(2)步。算法(1)把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標(biāo)節(jié)4712345678910111213141516171819★21222324★26272829303112345678910111213141516171819★234567891011121314151617181912345678910123456789搜索演示★已擴展節(jié)點

正在擴展節(jié)點擴展的子節(jié)點

未擴展節(jié)點目標(biāo)12345678910111213141516171819★48寬度優(yōu)先法應(yīng)用示例寬度優(yōu)先法求九宮重排問題2318476512384765寬度優(yōu)先法應(yīng)用示例寬度優(yōu)先法求九宮重排問題24923184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)82341876542323283250寬度優(yōu)先搜索是圖搜索一般過程的特殊情況，將圖搜索一般過程中的第8步具體化為本算法中的第6步，這實際是將OPEN表作為“先進先出”的隊列進行操作。一定能找到解找到的解一定是最佳解(在每個路徑消耗是同樣的意義上)搜索的空間大、慢。

分析寬度優(yōu)先搜索是圖搜索一般過程的特殊情況，將圖搜索一般過程中的51深度優(yōu)先搜索：首先擴展最新產(chǎn)生的(即最深的)節(jié)點。深度相等的節(jié)點可以任意排列。特點：擴展最深的節(jié)點,使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點向下進行下去；只有當(dāng)搜索到達一個沒有后裔的狀態(tài)時，它才考慮另一條替代的路徑。算法：與寬度優(yōu)先相似，不同在于：(5)把n的所有后繼節(jié)點放到OPEN表的前端2、depth-firstsearch深度優(yōu)先搜索：首先擴展最新產(chǎn)生的(即最深的)節(jié)點。深度相等的523456789101112131415161718192021★2324★26272829303112活結(jié)點表1121124224844816881616817881717884944918991818919919194425225105510209991010202010211010212110105115511★演示34567891011121314151617181920253例九宮重排問題83647■5初始狀態(tài)1238■4765目標(biāo)狀態(tài)應(yīng)用示例例九宮重排問題83初始狀態(tài)1254231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abd12384765目標(biāo)2323283255分析①不一定能找到解。②解不一定是最佳解。分析①不一定能找到解。563、其他方法含有深度界限的深度優(yōu)先搜索算法：基于代價樹的搜索算法：3、其他方法含有深度界限的深度優(yōu)先搜索算法：57TOPIC4heuristicsearch盲目搜索效率低，耗費過多的計算空間與時間，這是組合爆炸的一種表現(xiàn)形式。利用知識來引導(dǎo)搜索，達到減少搜索范圍，降低問題復(fù)雜度的目的。啟發(fā)式方法的本質(zhì)是部分地放棄算法"一般化,通用化"的概念,把所要解的問題的具體領(lǐng)域的知識加進算法中去,以提高算法的效率。

TOPIC4heuristicsearch盲目搜索效率低58啟發(fā)式搜索：就是利用與問題有關(guān)的啟發(fā)信息進行搜索啟發(fā)信息：與具體問題有關(guān)的特性信息啟發(fā)信息的強度強：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解難點：獲??；強度的確定；啟發(fā)式搜索：就是利用與問題有關(guān)的啟發(fā)信息進行搜索59啟發(fā)信息的用途a、用于決定要擴展的下一節(jié)點（避免盲目擴展）b、在擴展過程中，用于決定生成哪一個或哪幾個后繼（以免太多無用節(jié)點）C、用于決定被拋棄or被修剪的節(jié)點（博羿中常用，其它不常見）。。。啟發(fā)信息的用途a、用于決定要擴展的下一節(jié)點（避免盲目擴展）60基本思想啟發(fā)式搜索過程中,要對OPEN表進行排序,這就需要有一種方法來計算待擴展節(jié)點有希望通向目標(biāo)節(jié)點的不同程度,我們總是希望能找到最有希望通向目標(biāo)節(jié)點的待擴展節(jié)點優(yōu)先擴展。希望的量度就是通過估價函數(shù)f（n）來描述的基本思想啟發(fā)式搜索過程中,要對OPEN表進行排序,這就需61估價函數(shù)：定義為從初始節(jié)點經(jīng)過n節(jié)點到達目的節(jié)點的路徑的最小代價的估計值，XWZg(X)h(X)估價函數(shù)的形式為f(n)=g(n)+h(n)g（n）—是到目前為止,從s到n的最小路徑

（實際值）h（n）—n節(jié)點到目標(biāo)節(jié)點最佳路徑的估計值，體現(xiàn)了啟發(fā)信息通常f（n）由經(jīng)驗和直覺得到的，有很多種取法，關(guān)鍵在于h（n）。估價函數(shù)：定義為從初始節(jié)點經(jīng)過n節(jié)點到達目的節(jié)點的路徑的最小62e．g．八數(shù)碼難題的估價函數(shù) f（n）=g（n）+h（n） d（n）：節(jié)點n的深度 w（n）：不在位的數(shù)字個數(shù) p（n）：不在位的數(shù)字離目標(biāo)的距離之和例：右圖（a）中2、8、1、6不在位，w（n）=4，p（n）=1+2+1+1=5；（b）6、8、2、1不在位，w（n）=4，p（n）=3+2+2+2=92831647568321475abc81263754e．g．八數(shù)碼難題的估價函數(shù)2836863s（n）：沿著周圍那些非中心方格上依順時針方向檢查n格局中每一將牌，如果其后緊跟的將牌正好是目標(biāo)格局中該將牌的后續(xù)者，則該將牌得0分，否則得2分；在中中方格上有將牌得1分，無得0分；將所有將牌得分之和即為s（n）。圖（c）中s（a）=6。2831647568321475abc81263754s（n）：沿著周圍那些非中心方格上依順時針方向檢查n格局中每64例子:eight-puzzle評價函數(shù)f(n)=d(n)+W(n)d(n):節(jié)點n的深度;W(n):與目標(biāo)相比,錯位的數(shù)字數(shù)目，即不在位的數(shù)字個數(shù);1238476528316475初始狀態(tài)目標(biāo)狀態(tài)例子:eight-puzzle評價函數(shù)1238476528652831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標(biāo)123456283283283266由前例看出,與深度優(yōu)先搜索和寬度優(yōu)先搜索相比較,啟發(fā)式搜索大大減少了搜索范圍,大大減少了擴展的節(jié)點,大大減少了生成的節(jié)點,從而達到降低問題復(fù)雜度,提高算法的效率的目的。由前例看出,與深度優(yōu)先搜索和寬度優(yōu)先搜索相比較,啟發(fā)式搜67估價函數(shù)的進一步說明nSg*(n)h*(n)gf*(n)=g*(n)+h*(n)：從s經(jīng)過n到g的最短路徑g*(n)：從s到n的最短路徑h*(n)：從n到g的最短路徑f（n）=g（n）+h（n）：從s經(jīng)過n到g的最短路徑的估計值g(n)、h(n)分別是g*(n)、h*(n)的估計值估價函數(shù)的進一步說明nSg*(n)h*(n)gf*(n)=68g(n)一般取實際走過的路徑的費用和.g(n)g*(n)隨著算法的執(zhí)行，由于指針的變動，g(n)會下降.

h0沒有啟發(fā)式信息;g(n)69啟發(fā)式搜索算法A算法A*算法啟發(fā)式搜索算法A算法70A算法在Graphsearch過程中，如果第8步的重排open表是依據(jù)f（n）=g（n）+h（n）進行的，則稱該過程為A算法。g(n)取實際走過的路徑的費用和;節(jié)點排序是按照f(n)從小到大排;如前例-九宮重排問題A算法在Graphsearch過程中，如果第8步的重排ope71算法A*在A算法中，如果滿足條件： 0≤h(n)≤h*(n) 則A算法稱為A*算法。稱h（x）為h*（x）的下界，它表示某種偏于保守的估計。啟發(fā)式搜索算法A*又稱為最佳圖搜索算法(OptimalSearch)。算法A*在A算法中，如果滿足條件：725、經(jīng)典例題（八數(shù)碼難題）：設(shè)有八數(shù)碼難題，起始狀態(tài)如右圖，要求找出九宮重排的最終解路徑，并畫框圖。283164755、經(jīng)典例題（八數(shù)碼難題）：28373解法一：第一步：取估價函數(shù)為f（n）=d（n）+w（n），則顯然按照定義1它是A算法；第二步：因為w（n）指的是不在位的個數(shù)，所以w（n）=4，即估計只需要走4步即可到達目標(biāo)狀態(tài)，而實際上要到達目標(biāo)狀態(tài)肯定要大于3步，即w（x）≤w*（x），滿足定義，所以是A*算法；第三步：畫圖，并計算各個狀態(tài)f（n）的值，取f（n）值最小的節(jié)點進行擴充。(圖見前)解法一：74解法二：取估價函數(shù)為f（n）=d（n）+P（n），同理也是A*算法；如圖解法二：取估價函數(shù)為f（n）=d（n）+P（n），同理也是A75人工智能第三章基本的問題求解方法76TipsA算法與A*算法區(qū)別區(qū)別在于在A*算法中，0≤h(n)≤h*(n)示例：八數(shù)碼難題中h(n)的三種定義h(n)=w(n),h(n)=p(n)-A*算法h(n)=p(n)+3s(n)-A算法TipsA算法與A*算法區(qū)別區(qū)別在于在A*算法中，0≤h77A*算法具有可采納性一般地說對任意一個圖,當(dāng)s到目標(biāo)節(jié)點有一條路徑存在時,如果搜索算法總是在找到一條從s到目標(biāo)節(jié)點的最佳路徑上結(jié)束,則稱該搜索算法是可采納的(Admissibility)。A*就具有可采納性即當(dāng)問題有解時,A*一定能找到一條到達目標(biāo)節(jié)點的最佳路徑。（why？）證明見參考資料-A*算法具有可采納性考慮h(n)≡0的情況?。。?！A*算法具有可采納性一般地說對任意一個圖,當(dāng)s到目標(biāo)節(jié)點78A*算法的理論意義A*算法的理論意義在于給出了求解最佳解的條件h(n)≤h*(n)

對給定的問題,函數(shù)h*(n)在問題有解的條件下客觀上是存在的。但在問題求解過程中不可能都明確知道。因此,對實際問題,能不能使所定義的啟發(fā)函數(shù)滿足下界范圍條件?這是個問題。如果困難很大,那未A*算法的實際應(yīng)用就會受到限制。A*算法的理論意義A*算法的理論意義在于給出了求解最佳解的79以前面-八數(shù)碼難題為例定義h(n)為任意節(jié)點與目標(biāo)之間的差異若取=w(n)(將牌不在位個數(shù)),那未很容易看出,盡管我們對具體的h*(n)是多少很難確切知道,但根據(jù)“不在位”將牌個數(shù)這個估計,就能得出至少要移動W(n)步才能到達目標(biāo),顯然有h(n)=W(n)≤h*(n)。進一步考慮任意節(jié)點與目標(biāo)之間距離的信息,即取h(n)=p(n),p(n)定義為每一個將牌與其目標(biāo)位置之間距離(不考慮夾在其間的將牌)的總和,那未同樣能斷定至少也要移動p(n)步才能達到目標(biāo)，仍然有P(n)≤h*(n)。以前面-八數(shù)碼難題為例80啟發(fā)信息的強度的進一步分析強：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉鳎赡芸梢哉业阶顑?yōu)解啟發(fā)信息的強度的進一步分析強：降低搜索工作量，但可能導(dǎo)致找不81h(n)取不同函數(shù)時的八數(shù)碼難題求解情況進行比較,比較h(n)=0、h(n)=W(n)和h(n)=p(n)三種情況的求解結(jié)果。

①h(n)=0:即啟發(fā)函數(shù)啟發(fā)信息為0,f(n)=h(n)+g(n)=g(n)＝d(n)(搜索深度),此實際上是寬度優(yōu)先搜索。

②h(n)=W(n):即啟發(fā)函數(shù)取將牌不在位的信息,f(n)=h(n)+g(n)=W(n)+d(n)(搜索深度)。

③h(n)=p(n):即啟發(fā)函數(shù)取每一個將牌與其目標(biāo)位置之間距離的總和的信息

h(n)取不同函數(shù)時的八數(shù)碼難題求解情況進行比較,比較h(82實際上①中h(n)=0≤h*(n)，②和③均已證明W(n)≤h*(n)，P（n）≤h*(n)，即3種算法都是A*算法。比較搜索空間，分析啟發(fā)信息強弱的效果：啟發(fā)函數(shù)h(n)=0h(n)=W(n)h(n)=p(n)擴展節(jié)點數(shù)2665生成節(jié)點數(shù)461311實際上①中h(n)=0≤h*(n)，②和③均已證明W(83附：評價搜索算法的指標(biāo)1、外顯率（Penetrance）P=L/TL—從初始狀態(tài)到目標(biāo)狀態(tài)的長度；T—從初始狀態(tài)到目標(biāo)狀態(tài)所產(chǎn)生的所有狀態(tài)的個數(shù)；顯然P=1時，說明有效路徑所經(jīng)歷的節(jié)點都有用附：評價搜索算法的指標(biāo)1、外顯率（Penetrance）842、有效分支數(shù)（EffectiveBranchingFactor）B—搜索過程中，平均每個節(jié)點產(chǎn)生的分支數(shù)目；因為每個節(jié)點產(chǎn)生的平均分支數(shù)為B，所以從初始到目標(biāo)狀態(tài)產(chǎn)生的總分支數(shù)T為：2、有效分支數(shù)（EffectiveBranchingFa85本章回顧教學(xué)內(nèi)容：本章在上一章知識表示的基礎(chǔ)上研究問題求解的方法，是人工智能研究的又一核心問題。本章主要介紹基本的搜索技術(shù)教學(xué)重點：圖搜索策略、啟發(fā)式搜索教學(xué)難點：啟發(fā)式搜索教學(xué)方法：課堂教學(xué)為主，輔以恰當(dāng)?shù)膶嶒?。注意結(jié)合前面所學(xué)知識表示的基礎(chǔ)內(nèi)容，將其與問題求解方法融為一體。教學(xué)要求：重點掌握一般圖搜索策略，掌握各種搜索方法，尤其是啟發(fā)式搜索中的A*算法。

本章回顧教學(xué)內(nèi)容：本章在上一章知識表示的基礎(chǔ)上研究問題求解的86homework選做：利用A*算法求解九宮重排問題。要求：同前

----THEEND----homework選做：利用A*算法求解九宮重排問題。----87第三章基本的問題求解方法問題求解的過程：1）知識表示；2）針對問題，分析特征，選擇合適的方法來求解（包括搜索和推理）方法： 1）基于狀態(tài)圖方法-搜索； 2）基于謂詞邏輯方法-推理； 3）基于結(jié)構(gòu)化的知識表示方法來求解問題；本章介紹搜索技術(shù)第三章基本的問題求解方法問題求解的過程：1）知識表示；2）88搜索技術(shù)是人工智能的基本技術(shù)之一,在人工智能各應(yīng)用領(lǐng)域中被廣泛地使用。早期的人工智能程序與搜索技術(shù)聯(lián)系就更為緊密，幾乎所有的早期的人工智能程序都是以搜索為基礎(chǔ)的。A.Newell和H·A·Simon-LT程序A·Newell和H·A·Simon-GPS(GeneralProblemSolver)R.Fikes和N.Nilsson-STRIPS(StanfordResearchInstituteProblemSolver)現(xiàn)在,搜索技術(shù)滲透在各種人工智能系統(tǒng)中,在專家系統(tǒng)、自然語言理解、自動程序設(shè)計、模式識別、機器人學(xué)、信息檢索和博奕都廣泛使用。搜索技術(shù)是人工智能的基本技術(shù)之一,在人工智能各應(yīng)用領(lǐng)域中被89搜索(search)路徑狀態(tài)序列搜索尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑;S0Sg搜索(search)路徑S0Sg90搜索的必要性AI為什么要研究search?問題沒有直接的解法;解方程組;定理證明;需要探索地求解;搜索的必要性AI為什么要研究search?91搜索與檢索的區(qū)別狀態(tài)是否動態(tài)生成;檢索:靜態(tài);在數(shù)據(jù)庫中檢索某人的紀(jì)錄;搜索:動態(tài)生成;下棋搜索與檢索的區(qū)別狀態(tài)是否動態(tài)生成;92幾個問題目標(biāo)狀態(tài)是否確定?確定:定理證明,eight-puzzle不確定:求積分,下棋;確定目標(biāo)的性質(zhì);問題的解:路徑(解路徑)/目標(biāo)狀態(tài);需要路徑:下棋

不需要路徑:電路設(shè)計

需要/不需要:診病約束條件目標(biāo)狀態(tài)不確定時,用來約束目標(biāo)狀態(tài)的性質(zhì);X+Y=4:非整數(shù)解/整數(shù)解幾個問題目標(biāo)狀態(tài)是否確定?93幾個問題(續(xù)1)多解性;X+Y=4:整數(shù)解最優(yōu)解評價標(biāo)準(zhǔn)/判斷準(zhǔn)則;min(x*y)北京->上海:時間最短/費用最少最優(yōu)解是否唯一?下棋幾個問題(續(xù)1)多解性;94搜索問題狀態(tài)空間237

5148612384765搜索問題狀態(tài)空間237

514861238476595搜索不是檢索237

5148612384765搜索不是檢索237

514861238476596難點237

5148612384765難點237

514861238476597啟發(fā)式方法237

5148612384765啟發(fā)式方法237

514861238476598搜索方法的評價標(biāo)準(zhǔn)

搜索問題是AI核心理論問題之一。一般一個問題可以用好幾種搜索技術(shù)解決,選擇一種好的搜索技術(shù)對解決問題的效率很有關(guān)系,甚至關(guān)系到求解問題有沒有解。

搜索方法好的標(biāo)準(zhǔn),一般認為有兩個：

(1)搜索空間小;

(2)解最佳。搜索方法的評價標(biāo)準(zhǔn)

搜索問題是AI核心理論問題之一。一般一個99搜索分類搜索從問題性質(zhì)上來看,可分為一般搜索和博奕搜索,從處理方法上來看,可分為盲目搜索和啟發(fā)式搜索。還可以分得更細。到目前為止,AI領(lǐng)域中已提出許多具體的搜索方法,概括起來有：

(1)求任一解路的搜索策略

回溯法；爬山法(HillClimbing)；寬度優(yōu)先法(Breadth-first)；深度優(yōu)先法(Depth-first)

(2)求最佳解路的搜索策略

大英博物館法(BritishMuseum)；最佳圖搜索法(A*)

(3)求與或關(guān)系解圖的搜索法

一般與或圖搜索法(AO*)；極小極大法(Minimax)

剪枝法(Alpha-betaPruning)；啟發(fā)式剪枝法(HeuristicPruning)搜索分類搜索從問題性質(zhì)上來看,可分為一般搜索和博奕搜索,100人工智能第三章基本的問題求解方法101TOPICS回溯策略（Backtracking

）圖搜索（GRAPHSEARCH）無信息搜索啟發(fā)式搜索TOPICS回溯策略（Backtracking）102TOPIC1BacktrackingN1N0N2N3N4N5回溯策略TOPIC1BacktrackingN1N0N2N3103例：四皇后問題例：四皇后問題104()()105()Q((1,1))()Q((1,1))106()QQ((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))107()Q((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))108()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,1109()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,1110()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,1111()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()Q((1,1))((1,1)(2,3))((1,1)112()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)113()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))()((1,1))((1,1)(2,3))((1,1)114()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))()((1,1))((1,1)(2,3))((1,1)115()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))()((1,1))((1,1)(2,3))((1,1)116QQQQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1,2)(2,4)(3,1))((1,2)(2,4)(3,1)(4,3))QQQQ()((1,1))((1,1)(2,3))((1117存在問題及解決辦法問題和解決方法：深度問題對搜索深度加以限制死循環(huán)問題狀態(tài)重復(fù):A→B，B→C,C→A記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑存在問題及解決辦法問題和解決方法：118TOPIC2GRAPHSEARCH圖搜索策略問題的引出回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。圖搜索：保留所有已經(jīng)搜索過的路徑。

N5N1N0N2

N3

N4TOPIC2GRAPHSEARCH圖搜索策略N5N1119一些基本概念圖：一個節(jié)點的集合。節(jié)點由弧連接起來。

有向圖：弧是一個節(jié)點指向另一個節(jié)點的圖，稱為有向圖。

后繼/父親：如果有一條弧從ni指向nj，則nj稱為ni的后繼，ni稱為nj的父輩（父親）；

一些基本概念圖：一個節(jié)點的集合。節(jié)點由弧連接起來。120一些基本概念(續(xù)1)路徑：如果存在一個節(jié)點序列（ni0，ni1，……，nik），nij是nij-1是的后繼，j=1，……，k，則稱這個序列是從節(jié)點ni0到節(jié)點nik的一條路徑，長度為k。祖先/后裔：如果存在一條從ni到nj的路徑，則稱nj是ni的后裔，ni稱為nj的祖先。樹：每個節(jié)點最多只有一個父輩。沒有父輩的節(jié)點稱為根節(jié)點。沒有后繼的節(jié)點稱為葉節(jié)點。

一些基本概念(續(xù)1)路徑：如果存在一個節(jié)點序列（ni0，ni121一些基本概念(續(xù)2)節(jié)點深度： 根節(jié)點深度=0 其它節(jié)點深度=父節(jié)點深度+10123一些基本概念(續(xù)2)節(jié)點深度：0123122一些基本概念（續(xù)3）擴展一個節(jié)點生成出該節(jié)點的所有后繼節(jié)點。弧的費用有一條弧連接ni和nj兩個節(jié)點,用C(ni,nj)表示使用規(guī)則從ni到nj的費用(耗散值)。玉泉路---天安門路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。一些基本概念（續(xù)3）擴展一個節(jié)點123GRAPHSEARCH的思路OPEN表已經(jīng)生成但未擴展節(jié)點CLOSED表已擴展節(jié)點擴展節(jié)點i生成節(jié)點j指針

調(diào)整指針GRAPHSEARCH的思路OPEN表124圖搜索（GraphSearch）的一般過程

1、建立一個只有起始節(jié)點S的搜索圖G，把S放入一個叫open的未擴展節(jié)點表；2、

建立已擴展節(jié)點表closed，初始為空；3、

LOOP；若open為空，則失敗退出；4、

選open表中的第一個節(jié)點，設(shè)為n，移入closed表；5、若n為目標(biāo)節(jié)點，則成功退出，該問題的解即是G中沿S指向n的路徑；6、若不是目標(biāo)節(jié)點，則擴展n，生成不是n的祖先的那些后繼節(jié)點的集合m，把m的成員作為n的后繼加入G中；7、對未曾在G中出現(xiàn)過的m成員，設(shè)一通向n的指針，把它們加入open表。對已在closed或open表上的m成員，確定是否要更改到n的指針方向，對已在closed上的m成員，確定是否要更改G中通向每個后裔節(jié)點的指針方向。8、按某一方式（深度優(yōu)先、寬度優(yōu)先、A*算法）重排open表9、GOLOOP圖搜索（GraphSearch）的一般過程1、建立一個只125例子SOPENCLOSE{S}{}123{}{S}{1,2,3}{S}{2,1,3}{S}45{1,3}{S,2}{1,3,4,5}{S,2}{3,1,4,5}{S,2}{1,4,5}{S,2,3}6{1,4,5,6}{S,2,3}例子SOPENCLOSE{S}{}123{}{S}126例：右圖中黑節(jié)點表示已擴展，白節(jié)點表示未擴展，問題：先擴展6號節(jié)點生成m1={4，7}，然后擴展節(jié)點1，生成m2={2}，按算法第七步重新修改原圖。612453難點?。?！算法中第七步7例：右圖中黑節(jié)點表示已擴展，白節(jié)點表示未擴展，問題：先擴展6127擴展節(jié)點6生成m1={4，7}的調(diào)整61245371235467×擴展節(jié)點6生成m1={4，7}的調(diào)整612453712354128再擴展節(jié)點1生成m2={2}的調(diào)整12354671235467××再擴展節(jié)點1生成m2={2}的調(diào)整1235467123546129最終結(jié)果61245371235467最終結(jié)果61245371235467130圖搜索與回溯算法的區(qū)別

擴展節(jié)點:回溯算法:生成一個兒子節(jié)點.

圖搜索:擴展節(jié)點,生成所有兒子節(jié)點.

候選節(jié)點:回溯算法:一個.

圖搜索:多個.

回溯:回溯算法:返回父親節(jié)點.

圖搜索:不一定返回父親節(jié)點.圖搜索與回溯算法的區(qū)別擴展節(jié)點:131TOPIC3無信息搜索如果在GRAPHSEARCH中，對節(jié)點的排序不使用與問題相關(guān)的信息，則稱為無信息圖搜索（盲目搜索）寬度優(yōu)先和深度優(yōu)先TOPIC3無信息搜索如果在GRAPHSEARCH中，對節(jié)1321、breadth-firstsearch寬度優(yōu)先搜索：如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的。

搜索逐層進行；在對下一層的任一節(jié)點進行搜索之前，必須搜索完本層的所有節(jié)點。1、breadth-firstsearch寬度優(yōu)先搜索：如133(1)把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標(biāo)節(jié)點，則求得一個解答)。(2)如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。(3)把第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED的擴展節(jié)點表中。(4)擴展節(jié)點n。如果沒有后繼節(jié)點，則轉(zhuǎn)向上述第(2)步。(5)把n的所有后繼節(jié)點放到OPEN表的末端，并提供從這些后繼節(jié)點回到n的指針。(6)如果n的任一個后繼節(jié)點是個目標(biāo)節(jié)點，則找到一個解答，成功退出；否則轉(zhuǎn)向第(2)步。算法(1)把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標(biāo)節(jié)13412345678910111213141516171819★21222324★26272829303112345678910111213141516171819★234567891011121314151617181912345678910123456789搜索演示★已擴展節(jié)點

正在擴展節(jié)點擴展的子節(jié)點

未擴展節(jié)點目標(biāo)12345678910111213141516171819★135寬度優(yōu)先法應(yīng)用示例寬度優(yōu)先法求九宮重排問題2318476512384765寬度優(yōu)先法應(yīng)用示例寬度優(yōu)先法求九宮重排問題213623184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)823418765423232832137寬度優(yōu)先搜索是圖搜索一般過程的特殊情況，將圖搜索一般過程中的第8步具體化為本算法中的第6步，這實際是將OPEN表作為“先進先出”的隊列進行操作。一定能找到解找到的解一定是最佳解(在每個路徑消耗是同樣的意義上)搜索的空間大、慢。

分析寬度優(yōu)先搜索是圖搜索一般過程的特殊情況，將圖搜索一般過程中的138深度優(yōu)先搜索：首先擴展最新產(chǎn)生的(即最深的)節(jié)點。深度相等的節(jié)點可以任意排列。特點：擴展最深的節(jié)點,使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點向下進行下去；只有當(dāng)搜索到達一個沒有后裔的狀態(tài)時，它才考慮另一條替代的路徑。算法：與寬度優(yōu)先相似，不同在于：(5)把n的所有后繼節(jié)點放到OPEN表的前端2、depth-firstsearch深度優(yōu)先搜索：首先擴展最新產(chǎn)生的(即最深的)節(jié)點。深度相等的1393456789101112131415161718192021★2324★26272829303112活結(jié)點表1121124224844816881616817881717884944918991818919919194425225105510209991010202010211010212110105115511★演示345678910111213141516171819202140例九宮重排問題83647■5初始狀態(tài)1238■4765目標(biāo)狀態(tài)應(yīng)用示例例九宮重排問題83初始狀態(tài)12141231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abd12384765目標(biāo)23232832142分析①不一定能找到解。②解不一定是最佳解。分析①不一定能找到解。1433、其他方法含有深度界限的深度優(yōu)先搜索算法：基于代價樹的搜索算法：3、其他方法含有深度界限的深度優(yōu)先搜索算法：144TOPIC4heuristicsearch盲目搜索效率低，耗費過多的計算空間與時間，這是組合爆炸的一種表現(xiàn)形式。利用知識來引導(dǎo)搜索，達到減少搜索范圍，降低問題復(fù)雜度的目的。啟發(fā)式方法的本質(zhì)是部分地放棄算法"一般化,通用化"的概念,把所要解的問題的具體領(lǐng)域的知識加進算法中去,以提高算法的效率。

TOPIC4heuristicsearch盲目搜索效率低145啟發(fā)式搜索：就是利用與問題有關(guān)的啟發(fā)信息進行搜索啟發(fā)信息：與具體問題有關(guān)的特性信息啟發(fā)信息的強度強：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解難點：獲??；強度的確定；啟發(fā)式搜索：就是利用與問題有關(guān)的啟發(fā)信息進行搜索146啟發(fā)信息的用途a、用于決定要擴展的下一節(jié)點（避免盲目擴展）b、在擴展過程中，用于決定生成哪一個或哪幾個后繼（以免太多無用節(jié)點）C、用于決定被拋棄or被修剪的節(jié)點（博羿中常用，其它不常見）。。。啟發(fā)信息的用途a、用于決定要擴展的下一節(jié)點（避免盲目擴展）147基本思想啟發(fā)式搜索過程中,要對OPEN表進行排序,這就需要有一種方法來計算待擴展節(jié)點有希望通向目標(biāo)節(jié)點的不同程度,我們總是希望能找到最有希望通向目標(biāo)節(jié)點的待擴展節(jié)點優(yōu)先擴展。希望的量度就是通過估價函數(shù)f（n）來描述的基本思想啟發(fā)式搜索過程中,要對OPEN表進行排序,這就需148估價函數(shù)：定義為從初始節(jié)點經(jīng)過n節(jié)點到達目的節(jié)點的路徑的最小代價的估計值，XWZg(X)h(X)估價函數(shù)的形式為f(n)=g(n)+h(n)g（n）—是到目前為止,從s到n的最小路徑

（實際值）h（n）—n節(jié)點到目標(biāo)節(jié)點最佳路徑的估計值，體現(xiàn)了啟發(fā)信息通常f（n）由經(jīng)驗和直覺得到的，有很多種取法，關(guān)鍵在于h（n）。估價函數(shù)：定義為從初始節(jié)點經(jīng)過n節(jié)點到達目的節(jié)點的路徑的最小149e．g．八數(shù)碼難題的估價函數(shù) f（n）=g（n）+h（n） d（n）：節(jié)點n的深度 w（n）：不在位的數(shù)字個數(shù) p（n）：不在位的數(shù)字離目標(biāo)的距離之和例：右圖（a）中2、8、1、6不在位，w（n）=4，p（n）=1+2+1+1=5；（b）6、8、2、1不在位，w（n）=4，p（n）=3+2+2+2=92831647568321475abc81263754e．g．八數(shù)碼難題的估價函數(shù)28368150s（n）：沿著周圍那些非中心方格上依順時針方向檢查n格局中每一將牌，如果其后緊跟的將牌正好是目標(biāo)格局中該將牌的后續(xù)者，則該將牌得0分，否則得2分；在中中方格上有將牌得1分，無得0分；將所有將牌得分之和即為s（n）。圖（c）中s（a）=6。2831647568321475abc81263754s（n）：沿著周圍那些非中心方格上依順時針方向檢查n格局中每151例子:eight-puzzle評價函數(shù)f(n)=d(n)+W(n)d(n):節(jié)點n的深度;W(n):與目標(biāo)相比,錯位的數(shù)字數(shù)目，即不在位的數(shù)字個數(shù);1238476528316475初始狀態(tài)目標(biāo)狀態(tài)例子:eight-puzzle評價函數(shù)12384765281522831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標(biāo)1234562832832832153由前例看出,與深度優(yōu)先搜索和寬度優(yōu)先搜索相比較,啟發(fā)式搜索大大減少了搜索范圍,大大減少了擴展的節(jié)點,大大減少了生成的節(jié)點,從而達到降低問題復(fù)雜度,提高算法的效率的目的。由前例看出,與深度優(yōu)先搜索和寬度優(yōu)先搜索相比較,啟發(fā)式搜154估價函數(shù)的進一步說明nSg*(n)h*(n)gf*(n)=g*(n)+h*(n)：從s經(jīng)過n到g的最短路徑g*(n)：從s到n的最短路徑h*(n)：從n到g的最短路徑f（n）=g（n）+h（n）：從s經(jīng)過n到g的最短路徑的估計值g(n)、h(n)分別是g*(n)、h*(n)的估計值估價函數(shù)的進一步說明nSg*(n)h*(n)gf*(n)=155g(n)一般取實際走過的路徑的費用和.g(n)g*(n)隨著算法的執(zhí)行，由于指針的變動，g(n)會下降.

h0沒有啟發(fā)式信息;g(n)156啟發(fā)式搜索算法A算法A*算法啟發(fā)式搜索算