人工智能 第三章 基本的問(wèn)題求解方法

1、第三章第三章 基本的問(wèn)題求解方法基本的問(wèn)題求解方法問(wèn)題求解的過(guò)程：?jiǎn)栴}求解的過(guò)程：1 1）知識(shí)表示；）知識(shí)表示；2 2）針對(duì)問(wèn)）針對(duì)問(wèn)題，分析特征，選擇合適的方法來(lái)求解（包題，分析特征，選擇合適的方法來(lái)求解（包括搜索和推理）括搜索和推理）方法：方法：1 1）基于狀態(tài)圖方法）基于狀態(tài)圖方法- -搜索；搜索；2 2）基于謂詞邏輯方法）基于謂詞邏輯方法- -推理；推理；3 3）基于結(jié)構(gòu)化的知識(shí)表示方法來(lái)求解問(wèn)題；）基于結(jié)構(gòu)化的知識(shí)表示方法來(lái)求解問(wèn)題；本章介紹本章介紹搜索技術(shù)搜索技術(shù)搜索技術(shù)是人工智能的基本技術(shù)之一, 在人工智能各應(yīng)用領(lǐng)域中被廣泛地使用。早期的人工智能程序與搜索技術(shù)聯(lián)系就更為緊密，幾乎

2、所有的早期的人工智能程序都是以搜索為基礎(chǔ)的。uA.Newell和HASimon-LT程序uANewell和HASimon-GPS(General Problem Solver)uR.Fikes和N.Nilsson-STRIPS(Stanford Research Institute Problem Solver)現(xiàn)在, 搜索技術(shù)滲透在各種人工智能系統(tǒng)中, 在專(zhuān)家系統(tǒng)、自然語(yǔ)言理解、自動(dòng)程序設(shè)計(jì)、模式識(shí)別、機(jī)器人學(xué)、信息檢索和博奕都廣泛使用。 搜索(search)路徑l狀態(tài)序列搜索l尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑;S0Sg搜索的必要性lAI為什么要研究search?l問(wèn)題沒(méi)有直接的解法;解方程組

3、;定理證明;l需要探索地求解;搜索與檢索的區(qū)別l狀態(tài)是否動(dòng)態(tài)生成;l檢索: 靜態(tài);在數(shù)據(jù)庫(kù)中檢索某人的紀(jì)錄;l搜索: 動(dòng)態(tài)生成;下棋幾個(gè)問(wèn)題l 目標(biāo)狀態(tài)是否確定?l確定: 定理證明, eight-puzzlel不確定: 求積分, 下棋;確定目標(biāo)的性質(zhì);l 問(wèn)題的解: 路徑(解路徑)/目標(biāo)狀態(tài);需要路徑:下棋 不需要路徑:電路設(shè)計(jì) 需要/不需要: 診病l 約束條件l目標(biāo)狀態(tài)不確定時(shí), 用來(lái)約束目標(biāo)狀態(tài)的性質(zhì); lX+Y=4: 非整數(shù)解/整數(shù)解幾個(gè)問(wèn)題(續(xù)1)多解性;lX+Y=4:整數(shù)解最優(yōu)解l評(píng)價(jià)標(biāo)準(zhǔn)/判斷準(zhǔn)則;lmin(x*y)l北京-上海: 時(shí)間最短/費(fèi)用最少最優(yōu)解是否唯一?l下棋搜索問(wèn)題狀

4、態(tài)空間2375148612384765搜索不是檢索2375148612384765難點(diǎn)2375148612384765啟發(fā)式方法2375148612384765搜索方法的評(píng)價(jià)標(biāo)準(zhǔn) 搜索問(wèn)題是AI核心理論問(wèn)題之一。一般一個(gè)問(wèn)題可以用好幾種搜索技術(shù)解決, 選擇一種好的搜索技術(shù)對(duì)解決問(wèn)題的效率很有關(guān)系, 甚至關(guān)系到求解問(wèn)題有沒(méi)有解。 搜索方法好的標(biāo)準(zhǔn), 一般認(rèn)為有兩個(gè)： (1)搜索空間小; (2)解最佳。 搜索分類(lèi)搜索從問(wèn)題性質(zhì)上來(lái)看, 可分為一般搜索和博奕搜索, 從處理方法上來(lái)看, 可分為盲目搜索和啟發(fā)式搜索。還可以分得更細(xì)。到目前為止, AI領(lǐng)域中已提出許多具體的搜索方法, 概括起來(lái)有： (1)

5、求任一解路的搜索策略回溯法；爬山法(Hill Climbing)；寬度優(yōu)先法(Breadth-first)；深度優(yōu)先法(Depth-first) (2)求最佳解路的搜索策略大英博物館法(British Museum)；最佳圖搜索法(A*) (3)求與或關(guān)系解圖的搜索法一般與或圖搜索法(AO*)；極小極大法(Minimax)剪枝法(Alpha-beta Pruning)；啟發(fā)式剪枝法(Heuristic Pruning) TOPICS回溯策略（ Backtracking ）圖搜索（GRAPHSEARCH）無(wú)信息搜索啟發(fā)式搜索TOPIC1 BacktrackingN1N0N2 N3 N4 N5 回

6、溯策略例：四皇后問(wèn)題QQQQ()()Q(1,1)()QQ(1,1)(1,1)(2,3)()Q(1,1)(1,1)(2,3)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)()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,1)(2,4)(1,1)(2,4)(3.2)()Q(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4

7、)(3.2)Q(1,2)()(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)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)QQQQ()(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)存在問(wèn)題及解決辦法問(wèn)題和解決方法：l深度問(wèn)題對(duì)搜索深度加以限制l死循環(huán)問(wèn)題狀態(tài)重復(fù): AB，BC, CA 記錄從初始

8、狀態(tài)到當(dāng)前狀態(tài)的路徑TOPIC2 GRAPH SEARCH圖搜索策略問(wèn)題的引出l回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。l圖搜索：保留所有已經(jīng)搜索過(guò)的路徑。N5 N1N0N2 N3 N4 一些基本概念圖：一個(gè)節(jié)點(diǎn)的集合。節(jié)點(diǎn)由弧連接起來(lái)。 有向圖：弧是一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)的圖，稱(chēng)為有向圖。 后繼/父親：如果有一條弧從ni指向nj，則nj稱(chēng)為n i的后繼，ni稱(chēng)為nj的父輩（父親）； 一些基本概念(續(xù)1)路徑：如果存在一個(gè)節(jié)點(diǎn)序列（ni0，ni1，nik），nij是nij-1是的后繼，j=1，k，則稱(chēng)這個(gè)序列是從節(jié)點(diǎn)ni0到節(jié)點(diǎn)nik的一條路徑，長(zhǎng)度為k。祖先/后裔：如果存在一條從ni

9、到nj的路徑，則稱(chēng)nj是ni的后裔，ni稱(chēng)為nj的祖先。樹(shù)：每個(gè)節(jié)點(diǎn)最多只有一個(gè)父輩。沒(méi)有父輩的節(jié)點(diǎn)稱(chēng)為根節(jié)點(diǎn)。沒(méi)有后繼的節(jié)點(diǎn)稱(chēng)為葉節(jié)點(diǎn)。 一些基本概念(續(xù)2)節(jié)點(diǎn)深度：根節(jié)點(diǎn)深度=0其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+10123一些基本概念（續(xù)3）擴(kuò)展一個(gè)節(jié)點(diǎn)l生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)?；〉馁M(fèi)用l有一條弧連接ni和nj兩個(gè)節(jié)點(diǎn), 用C(ni, nj)表示使用規(guī)則從ni到nj的費(fèi)用(耗散值)。 玉泉路-天安門(mén)路徑的耗散值l一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用C(ni, nj)表示從ni到nj的路徑的耗散值。GRAPHSEARCH的思路OPEN表l已經(jīng)生成但未擴(kuò)展節(jié)點(diǎn)CLOSED

10、表l已擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)i生成節(jié)點(diǎn)j 指針 調(diào)整指針圖搜索（圖搜索（Graph Search）的一般過(guò)程的一般過(guò)程 1 1、建立一個(gè)只有起始節(jié)點(diǎn)、建立一個(gè)只有起始節(jié)點(diǎn)S S的搜索圖的搜索圖G G，把，把S S放入一個(gè)叫放入一個(gè)叫openopen的的未擴(kuò)展節(jié)點(diǎn)表；未擴(kuò)展節(jié)點(diǎn)表；2 2、 建立已擴(kuò)展節(jié)點(diǎn)表建立已擴(kuò)展節(jié)點(diǎn)表closedclosed，初始為空；初始為空；3 3、 LOOPLOOP；若；若openopen為空，則失敗退出；為空，則失敗退出；4 4、 選選openopen表中的第一個(gè)節(jié)點(diǎn)，設(shè)為表中的第一個(gè)節(jié)點(diǎn)，設(shè)為n n，移入移入closedclosed表；表；5 5、若、若n n為目標(biāo)節(jié)點(diǎn)

11、，則成功退出，該問(wèn)題的解即是為目標(biāo)節(jié)點(diǎn)，則成功退出，該問(wèn)題的解即是G G中沿中沿S S指向指向n n的路徑；的路徑；6 6、若不是目標(biāo)節(jié)點(diǎn)，則擴(kuò)展、若不是目標(biāo)節(jié)點(diǎn)，則擴(kuò)展n n，生成不是生成不是n n的祖先的那些后繼的祖先的那些后繼節(jié)點(diǎn)的集合節(jié)點(diǎn)的集合m m，把，把m m的成員作為的成員作為n n的后繼加入的后繼加入G G中；中；7 7、對(duì)未曾在、對(duì)未曾在G G中出現(xiàn)過(guò)的中出現(xiàn)過(guò)的m m成員，設(shè)一通向成員，設(shè)一通向n n的指針，把它們加的指針，把它們加入入openopen表。對(duì)已在表。對(duì)已在closedclosed或或openopen表上的表上的m m成員，確定是否要更成員，確定是否要更改到改

12、到n n的指針?lè)较?，?duì)已在的指針?lè)较颍瑢?duì)已在closedclosed上的上的m m成員，確定是否要更改成員，確定是否要更改G G中通向每個(gè)后裔節(jié)點(diǎn)的指針?lè)较?。中通向每個(gè)后裔節(jié)點(diǎn)的指針?lè)较颉? 8、按某一方式（深度優(yōu)先、寬度優(yōu)先、按某一方式（深度優(yōu)先、寬度優(yōu)先、A A* *算法）重排算法）重排openopen表表9 9、GO LOOP GO LOOP 例子SOPENCLOSES 123 S 1,2,3 S 2,1,3 S 451,3 S,2 1,3,4,5 S,2 3,1,4,5 S,2 1,4,5 S,2,3 61,4,5,6 S,2,3 例：右圖中黑節(jié)點(diǎn)表示例：右圖中黑節(jié)點(diǎn)表示已擴(kuò)展，白節(jié)點(diǎn)

13、表示未已擴(kuò)展，白節(jié)點(diǎn)表示未擴(kuò)展，問(wèn)題：先擴(kuò)展擴(kuò)展，問(wèn)題：先擴(kuò)展6 6號(hào)號(hào)節(jié)點(diǎn)生成節(jié)點(diǎn)生成m1=4m1=4，77，然，然后擴(kuò)展節(jié)點(diǎn)后擴(kuò)展節(jié)點(diǎn)1 1，生成，生成m2=2m2=2，按算法第七步按算法第七步重新修改原圖。重新修改原圖。612453難點(diǎn)！算法中第七步7擴(kuò)展節(jié)點(diǎn)6生成m1=4，7的調(diào)整61245371235467再擴(kuò)展節(jié)點(diǎn)1生成m2=2的調(diào)整12354671235467最終結(jié)果61245371235467圖搜索與回溯算法的區(qū)別 擴(kuò)展節(jié)點(diǎn):l回溯算法:生成一個(gè)兒子節(jié)點(diǎn). l圖搜索:擴(kuò)展節(jié)點(diǎn), 生成所有兒子節(jié)點(diǎn). 候選節(jié)點(diǎn):l回溯算法:一個(gè). l圖搜索:多個(gè). 回溯:l回溯算法:返回父親節(jié)點(diǎn).

14、 l圖搜索:不一定返回父親節(jié)點(diǎn).TOPIC3 無(wú)信息搜索如果在GRAPHSEARCH中，對(duì)節(jié)點(diǎn)的排序不使用與問(wèn)題相關(guān)的信息，則稱(chēng)為無(wú)信息圖搜索（盲目搜索）寬度優(yōu)先和深度優(yōu)先1 1、breadth-first searchbreadth-first searchp寬度優(yōu)先搜索：如果搜索是以接近起始節(jié)點(diǎn)寬度優(yōu)先搜索：如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的的程度依次擴(kuò)展節(jié)點(diǎn)的 。 p搜索逐層進(jìn)行；在對(duì)下一層的任一節(jié)點(diǎn)進(jìn)行搜索逐層進(jìn)行；在對(duì)下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。(1) (1) 把起始節(jié)點(diǎn)放到把起始節(jié)點(diǎn)放到OPENOPEN表中表

15、中( (如果該起始節(jié)點(diǎn)為如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答) )。(2) (2) 如果如果OPENOPEN是個(gè)空表，則沒(méi)有解，失敗退出；是個(gè)空表，則沒(méi)有解，失敗退出；否則繼續(xù)。否則繼續(xù)。(3) (3) 把第一個(gè)節(jié)點(diǎn)把第一個(gè)節(jié)點(diǎn)( (節(jié)點(diǎn)節(jié)點(diǎn)n)n)從從OPENOPEN表移出，并把它表移出，并把它放入放入CLOSEDCLOSED的擴(kuò)展節(jié)點(diǎn)表中。的擴(kuò)展節(jié)點(diǎn)表中。(4) (4) 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n n。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第第(2)(2)步。步。(5) (5) 把把n n的所有后繼節(jié)點(diǎn)放到的所有后繼節(jié)點(diǎn)放到OPENOPEN表的末

16、端，并提表的末端，并提供從這些后繼節(jié)點(diǎn)回到供從這些后繼節(jié)點(diǎn)回到n n的指針。的指針。(6) (6) 如果如果n n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出；否則轉(zhuǎn)向第到一個(gè)解答，成功退出；否則轉(zhuǎn)向第(2)(2)步。步。算法1234567891011121314151617 1819 2122 23 24 2627 282930311234567891011121314151617 1819 2 34 5 678 9 10 11 12 13 14 15 16 17 18 1912345678910123456789搜索演示已擴(kuò)展節(jié)點(diǎn)正在擴(kuò)展節(jié)點(diǎn)擴(kuò)展

17、的子節(jié)點(diǎn)未擴(kuò)展節(jié)點(diǎn)目標(biāo)寬度優(yōu)先法應(yīng)用示例寬度優(yōu)先法應(yīng)用示例寬度優(yōu)先法求九宮重排問(wèn)題寬度優(yōu)先法求九宮重排問(wèn)題231847651238476523184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)8234187654p寬度優(yōu)先搜索是圖搜索一般過(guò)程的特殊情寬度優(yōu)先搜索是圖搜索一般過(guò)程的特殊情況，將圖搜索一般過(guò)程中的第況，將圖搜索一般過(guò)程中的第8 8步具體化為本步具體化為本算法中的第算法

18、中的第6 6步，這實(shí)際是將步，這實(shí)際是將OPENOPEN表作為表作為“先先進(jìn)先出進(jìn)先出”的隊(duì)列進(jìn)行操作。的隊(duì)列進(jìn)行操作。p一定能找到解一定能找到解p找到的解一定是最佳解找到的解一定是最佳解u(在每個(gè)路徑消耗是同樣的意義上在每個(gè)路徑消耗是同樣的意義上)p搜索的空間大、慢。搜索的空間大、慢。 分析分析p深度優(yōu)先搜索：首先擴(kuò)展最新產(chǎn)生的深度優(yōu)先搜索：首先擴(kuò)展最新產(chǎn)生的( (即最即最深的深的) )節(jié)點(diǎn)。深度相等的節(jié)點(diǎn)可以任意排列。節(jié)點(diǎn)。深度相等的節(jié)點(diǎn)可以任意排列。p特點(diǎn)：擴(kuò)展最深的節(jié)點(diǎn)特點(diǎn)：擴(kuò)展最深的節(jié)點(diǎn), ,使得搜索沿著狀態(tài)使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點(diǎn)向下進(jìn)行下空間某條單一的路徑從起

19、始節(jié)點(diǎn)向下進(jìn)行下去；只有當(dāng)搜索到達(dá)一個(gè)沒(méi)有后裔的狀態(tài)時(shí)，去；只有當(dāng)搜索到達(dá)一個(gè)沒(méi)有后裔的狀態(tài)時(shí)，它才考慮另一條替代的路徑。它才考慮另一條替代的路徑。p算法：與寬度優(yōu)先相似，不同在于：算法：與寬度優(yōu)先相似，不同在于：(5) (5) 把把n n的所有后繼節(jié)點(diǎn)放到的所有后繼節(jié)點(diǎn)放到OPENOPEN表的前端表的前端2 2、depth-first searchdepth-first search34567891011121314151617 1819 20 21 23 24 2627 2829303112活結(jié)點(diǎn)表活結(jié)點(diǎn)表1 1211242248448168816168178817178 84944918

20、991818919919194 425225105510209 9 91010202010211010212110105115511演示例 九宮重排問(wèn)題九宮重排問(wèn)題28 3 16 427 5初始狀態(tài)初始狀態(tài)1 2 3 8 47 6 5目標(biāo)狀態(tài)目標(biāo)狀態(tài)應(yīng)用示例應(yīng)用示例2 32 31 8 41 8 47 6 57 6 5 2 32 31 8 41 8 47 6 57 6 52 8 32 8 31 41 47 6 57 6 52 32 31 8 41 8 47 6 57 6 52 8 32 8 31 41 47 6 57 6 52 8 32 8 31 6 41 6 47 57 52 8 32 8 3

21、 1 4 1 47 6 57 6 52 8 32 8 31 6 41 6 47 57 52 8 32 8 31 6 41 6 4 7 5 7 52 8 32 8 37 1 47 1 4 6 5 6 5 8 38 32 1 42 1 47 6 57 6 52 82 81 4 31 4 37 6 57 6 52 8 32 8 31 4 51 4 57 6 7 6 1 2 31 2 37 8 47 8 4 6 5 6 51 2 31 2 38 48 47 6 57 6 52 8 32 8 3 6 4 6 41 7 51 7 52 8 32 8 31 61 67 5 47 5 48 38 32 1 4

22、2 1 47 6 57 6 52 8 32 8 37 1 47 1 46 56 52 82 81 4 31 4 37 6 57 6 52 8 32 8 31 4 51 4 57 67 612 23 34 45 56 67 78 89 9a ab bd d1 2 31 2 3 8 4 8 47 6 57 6 5目標(biāo)目標(biāo)分析不一定能找到解。解不一定是最佳解。 3 3、其他方法、其他方法p含有深度界限的深度優(yōu)先搜索算法：含有深度界限的深度優(yōu)先搜索算法：p基于代價(jià)樹(shù)的搜索算法：基于代價(jià)樹(shù)的搜索算法：TOPIC4 TOPIC4 heuristic searchp盲目搜索效率低，耗費(fèi)過(guò)多的計(jì)算空間與時(shí)盲目

23、搜索效率低，耗費(fèi)過(guò)多的計(jì)算空間與時(shí)間，這是組合爆炸的一種表現(xiàn)形式。間，這是組合爆炸的一種表現(xiàn)形式。 p利用知識(shí)來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍，利用知識(shí)來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問(wèn)題復(fù)雜度的目的。降低問(wèn)題復(fù)雜度的目的。p啟發(fā)式方法啟發(fā)式方法的本質(zhì)是部分地放棄算法的本質(zhì)是部分地放棄算法一般一般化化, 通用化通用化的概念的概念, 把所要解的問(wèn)題的具體領(lǐng)把所要解的問(wèn)題的具體領(lǐng)域域 的知識(shí)加進(jìn)算法中去的知識(shí)加進(jìn)算法中去, 以提高算法的效率。以提高算法的效率。 啟發(fā)式搜索啟發(fā)式搜索：就是利用與問(wèn)題有關(guān)的啟發(fā)信：就是利用與問(wèn)題有關(guān)的啟發(fā)信息進(jìn)行搜索息進(jìn)行搜索啟發(fā)信息：與具體問(wèn)題有關(guān)的特性信息啟發(fā)信息：

24、與具體問(wèn)題有關(guān)的特性信息啟發(fā)信息的強(qiáng)度啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解最優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?nèi)酰阂话銓?dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解為盲目搜索，但可能可以找到最優(yōu)解難點(diǎn)：難點(diǎn)：獲取；獲?。粡?qiáng)度的確定；強(qiáng)度的確定；啟發(fā)信息的用途a a、用于決定要擴(kuò)展的下一節(jié)點(diǎn)（避免盲目、用于決定要擴(kuò)展的下一節(jié)點(diǎn)（避免盲目擴(kuò)展）擴(kuò)展）b b、在擴(kuò)展過(guò)程中，用于決定生成哪一個(gè)或、在擴(kuò)展過(guò)程中，用于決定生成哪一個(gè)或哪幾個(gè)后繼（以免太多無(wú)用節(jié)點(diǎn)）哪幾個(gè)后繼（以免太多無(wú)用節(jié)點(diǎn)）C C、用于決定被拋棄、用于決定被拋棄

25、oror被修剪的節(jié)點(diǎn)（博羿被修剪的節(jié)點(diǎn)（博羿中常用，其它不常見(jiàn)）中常用，其它不常見(jiàn)）。基本思想啟發(fā)式搜索過(guò)程中, 要對(duì)OPEN表進(jìn)行排序, 這就需要有一種方法來(lái)計(jì)算待擴(kuò)展節(jié)點(diǎn)有希望通向目標(biāo)節(jié)點(diǎn)的不同程度, 我們總是希望能找到最有希望通向目標(biāo)節(jié)點(diǎn)的待擴(kuò)展節(jié)點(diǎn)優(yōu)先擴(kuò)展。 希望的量度就是通過(guò)估價(jià)函數(shù)f（n）來(lái)描述的p估價(jià)函數(shù)：定義為從初始節(jié)點(diǎn)經(jīng)過(guò)估價(jià)函數(shù)：定義為從初始節(jié)點(diǎn)經(jīng)過(guò)n n節(jié)點(diǎn)到達(dá)節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的路徑的最小代價(jià)的估計(jì)值，目的節(jié)點(diǎn)的路徑的最小代價(jià)的估計(jì)值，XWZg(X)h(X)估價(jià)函數(shù)的形式為估價(jià)函數(shù)的形式為f(n)=g(n)+h(n)g g（n n）是是到目前為止到目前為止, , 從從s

26、s到到n n的最小路徑的最小路徑 （實(shí)（實(shí)際值）際值）h h（n n） n n節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)值，節(jié)點(diǎn)最佳路徑的估計(jì)值，體現(xiàn)了啟發(fā)信息體現(xiàn)了啟發(fā)信息通常通常f f（n n）由經(jīng)驗(yàn)和直）由經(jīng)驗(yàn)和直覺(jué)得到的，有很多種取法，覺(jué)得到的，有很多種取法，關(guān)鍵在于關(guān)鍵在于h h（n n）。）。e eg g八數(shù)碼難題的估價(jià)函數(shù)八數(shù)碼難題的估價(jià)函數(shù)f f（n n）=g=g（n n）+h+h（n n）d d（n n）：）：節(jié)點(diǎn)節(jié)點(diǎn)n n的深度的深度w w（n n）：）：不在位的數(shù)字個(gè)數(shù)不在位的數(shù)字個(gè)數(shù)p p（n n）：）：不在位的數(shù)字離目標(biāo)的距離之和不在位的數(shù)字離目標(biāo)的距離之和例：右圖（例：

27、右圖（a a）中中2 2、8 8、1 1、6 6不在位，不在位，w w（n n）=4 =4 ，p p（n n）=1+2+1+1=5=1+2+1+1=5；（b b）6 6、8 8、2 2、1 1不不在位，在位，w w（n n）=4 =4 ，p p（n n）=3+2+2+2=9 =3+2+2+2=9 2831647568321475abc81263754s（n）：沿著周?chē)切┓侵行姆礁裆弦理槙r(shí)針?lè)较驒z查n格局中每一將牌，如果其后緊跟的將牌正好是目標(biāo)格局中該將牌的后續(xù)者，則該將牌得0分，否則得2分；在中中方格上有將牌得1分，無(wú)得0分；將所有將牌得分之和即為s（n）。圖（c）中s（a）=6。 2831

28、647568321475abc81263754例子: eight-puzzlen評(píng)價(jià)函數(shù)nf(n) = d(n) + W(n)nd(n): 節(jié)點(diǎn)n的深度;nW(n):與目標(biāo)相比, 錯(cuò)位的數(shù)字?jǐn)?shù)目，即不在位的數(shù)字個(gè)數(shù);1238476528316475初始狀態(tài)目標(biāo)狀態(tài) 2831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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

29、)目標(biāo)123456由前例看出, 與深度優(yōu)先搜索和寬度優(yōu)先搜索相比較, 啟發(fā)式搜索大大減少了搜索范圍, 大大減少了擴(kuò)展的節(jié)點(diǎn), 大大減少了生成的節(jié)點(diǎn), 從而達(dá)到降低問(wèn)題復(fù)雜度, 提高算法的效率的目的。 估價(jià)函數(shù)的進(jìn)一步說(shuō)明nSg*(n)h*(n) gf*(n)=g*(n)+h*(n)：從s經(jīng)過(guò)n到g的最短路徑lg*(n)：從s到n的最短路徑lh*(n)：從n到g的最短路徑f（n）=g（n）+h（n）：從s經(jīng)過(guò)n到g的最短路徑的估計(jì)值lg(n)、h(n) 分別是g*(n)、h*(n) 的估計(jì)值g(n)l一般取實(shí)際走過(guò)的路徑的費(fèi)用和.lg(n) g*(n)l隨著算法的執(zhí)行，由于指針的變動(dòng)，g(n)會(huì)

30、下降. h0l沒(méi)有啟發(fā)式信息;啟發(fā)式搜索算法A算法A*算法A算法在Graphsearch過(guò)程中，如果第8步的重排open表是依據(jù)f（n）=g（n）+h（n）進(jìn)行的，則稱(chēng)該過(guò)程為A算法。lg(n)取實(shí)際走過(guò)的路徑的費(fèi)用和;l節(jié)點(diǎn)排序是按照f(shuō)(n)從小到大排;l如前例-九宮重排問(wèn)題算法A*在A(yíng)算法中，如果滿(mǎn)足條件： 0h(n)h*(n)則A算法稱(chēng)為A*算法。l稱(chēng)h（x）為h*（x）的下界，它表示某種偏于保守的估計(jì)。啟發(fā)式搜索算法A*又稱(chēng)為最佳圖搜索算法(Optimal Search)。 5 5、經(jīng)典例題（八數(shù)碼難題）：、經(jīng)典例題（八數(shù)碼難題）：設(shè)有八數(shù)碼難題，起始狀態(tài)如右圖，設(shè)有八數(shù)碼難題，起始狀

31、態(tài)如右圖，要求找出九宮重排的最終解路徑，要求找出九宮重排的最終解路徑，并畫(huà)框圖。并畫(huà)框圖。28316475解法一：解法一：第一步：取估價(jià)函數(shù)為第一步：取估價(jià)函數(shù)為f f（n n）=d=d（n n）+w+w（n n），），則顯然按照定義則顯然按照定義1 1它是它是A A算法；算法；第二步：因?yàn)榈诙剑阂驗(yàn)閣 w（n n）指的是不在位的個(gè)數(shù)，所以指的是不在位的個(gè)數(shù)，所以w w（n n）=4=4，即估計(jì)只需要走，即估計(jì)只需要走4 4步即可到達(dá)目標(biāo)狀步即可到達(dá)目標(biāo)狀態(tài)，而實(shí)際上要到達(dá)目標(biāo)狀態(tài)肯定要大于態(tài)，而實(shí)際上要到達(dá)目標(biāo)狀態(tài)肯定要大于3 3步，步，即即w w（x x）w w* *（x x），），滿(mǎn)足

32、定義，所以是滿(mǎn)足定義，所以是A A* *算法；算法；第三步：畫(huà)圖，并計(jì)算各個(gè)狀態(tài)第三步：畫(huà)圖，并計(jì)算各個(gè)狀態(tài)f f（n n）的值，取的值，取f f（n n）值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)充。值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)充。( (圖見(jiàn)前圖見(jiàn)前) )解法二：取估價(jià)函數(shù)為f（n）=d（n）+P（n），同理也是A*算法；如圖Tips A算法與A*算法區(qū)別區(qū)別在于在A(yíng)*算法中， 0h(n)h*(n)示例：八數(shù)碼難題中h(n)的三種定義h(n)=w(n), h(n)=p(n)-A*算法h(n)=p(n)+3s(n)-A算法A*算法具有可采納性 一般地說(shuō)對(duì)任意一個(gè)圖, 當(dāng)s到目標(biāo)節(jié)點(diǎn)有一條路徑存在時(shí), 如果搜索算法總是在找到一條

33、從s到目標(biāo)節(jié)點(diǎn)的最佳路徑上結(jié)束, 則稱(chēng)該搜索算法是可采納的(Admissibility)。lA*就具有可采納性即當(dāng)問(wèn)題有解時(shí), A*一定能找到一條到達(dá)目標(biāo)節(jié)點(diǎn)的最佳路徑。（why？）證明見(jiàn)參考資料-A*算法具有可采納性考慮h(n)0的情況！A*算法的理論意義 A*算法的理論意義在于給出了求解最佳解的條件h(n) h*(n) 對(duì)給定的問(wèn)題,函數(shù)h*(n)在問(wèn)題有解的條件下客觀(guān)上是存在的。但在問(wèn)題求解過(guò)程中不可能都明確知道。因此, 對(duì)實(shí)際問(wèn)題, 能不能使所定義的啟發(fā)函數(shù)滿(mǎn)足下界范圍條件? 這是個(gè)問(wèn)題。如果困難很大, 那未A*算法的實(shí)際應(yīng)用就會(huì)受到限制。 以前面-八數(shù)碼難題為例定義h(n)為任意節(jié)點(diǎn)與目標(biāo)之間的差異若取= w(n)(將牌不在位個(gè)數(shù)), 那未很容易看出, 盡管我們對(duì)具體的h*(n)是多少很難確切知道, 但根據(jù)“不在位”將牌個(gè)數(shù)這個(gè)估計(jì), 就能得出至少要移動(dòng)W(n)步才能到達(dá)目標(biāo), 顯然有h(n) = W(n) h*(n)。進(jìn)一步考慮任意節(jié)點(diǎn)與目標(biāo)之間距離的信息, 即取h(n) = p(n), p(n)定義為每一個(gè)將牌與其目標(biāo)位置之間距離(不考慮夾在其間的將牌)的總和,那未同樣能斷定至少也要移動(dòng)p(n)步才能達(dá)到目