第1章搜索問題ppt課件

1、人工智能吉林大學珠海學院計算機科學與技術系第第 1 1 章章 搜索問題搜索問題什么是形狀空間？回溯戰(zhàn)略。圖搜索戰(zhàn)略無信息的圖搜索戰(zhàn)略啟發(fā)式圖搜索戰(zhàn)略A*算法。A*算法的性質。搜索算法的討論。人工智能吉林大學珠海學院計算機科學與技術系形狀空間計算機對傳統(tǒng)的問題求解方法帶來了根本性的改動。 傳統(tǒng)方法， 由專家給出公式， 運用者的義務是了解公式， 運用公式。 有些問題用傳統(tǒng)方法描畫很困難, 例如本節(jié)的幾個例子 公式的推導需求很高的程度， 與實踐問題相差較遠，對運用者要求很高。2. 計算機利用本人強大的計算才干和存儲才干, 采用猜的方式, 試探法. 能處理問題的領域更廣, 更結合實踐.人工智能吉林大學

2、珠海學院計算機科學與技術系例 智力游戲問題：傳教士與野人渡河問題 傳教士與野人渡河問題：有 3 個傳教士帶 3 個野人渡河，河的岸邊有一條船， 每次最多可載 2 人，要求無論在河的哪一邊，野人的數(shù)目不能超越傳教士的數(shù)目，問為平安起見， 應如何安排傳教士與野人渡河？ 一種較為簡單的表示方式3 元向量x, y, z x: 河此岸的傳教士數(shù)， y: 河此岸的野人數(shù)。 x,y 取值范圍0，1，2，3 z: 船在此岸，z取值范圍0，1 人工智能吉林大學珠海學院計算機科學與技術系初始形狀： 3，3，1目的形狀： 0，0，02831 647512386475初始形狀Initial 目的形狀 Goal例 設有

3、 8 數(shù)碼難題如下:在 33 的框架中有 8 個標有數(shù)字的硬紙片， 這些硬紙片上標的數(shù)字分別是 1， 2， , 8， 每個紙片都可以移進相鄰的空格， 8 數(shù)碼難題的初始形狀和目的形狀分別列出如下，問如何把這個問題由初始形狀移向目的形狀？ 人工智能吉林大學珠海學院計算機科學與技術系2831 647512386475Initial Goal8 數(shù)碼難題8-puzzle的矩陣描畫 對于8 數(shù)碼難題， 我們選用直接的矩陣描畫，解題過程中的任何一個中間情況都對應一個 3*3的矩陣， 用0,1，2，, 8這9個數(shù)的一個陳列依次去充填這個矩陣的各個單元,就是求解問題的一個能夠的情況, 共有 9!種。人工智能

4、吉林大學珠海學院計算機科學與技術系1 4 3 7 65 8 21 3 7 4 65 8 21 4 3 7 65 8 21 2 3 7 8 65 21 2 3 7 65 8 2 1 3 7 4 65 8 21 3 7 4 65 8 21 4 3 1 7 65 8 21 4 3 5 7 68 21 4 3 7 8 6 5 21 4 3 7 8 65 21 4 37 6 35 8 21 4 3 7 6 25 8 人工智能吉林大學珠海學院計算機科學與技術系例 游覽推銷員問題ABDCE75100125125501005075125100125問題表示, 方式為(A*)的字符串和(A*A)的字符串。其中*

5、為B,C, D, E 的陳列. 問題的節(jié)，方式為(A*A)的字符串, 其中*為B,C, D, E 的陳列.人工智能吉林大學珠海學院計算機科學與技術系游覽推銷員問題的搜索空間EADCBCDEAEDADCEAE10012510075150175425225325275375300250人工智能吉林大學珠海學院計算機科學與技術系1.1 回溯戰(zhàn)略 回溯戰(zhàn)略的主要思想: 只保管從初始形狀到當前形狀的一條解途徑, 給變換形狀的規(guī)那么給出一個排序方法, 對當前形狀運用規(guī)那么產生新的形狀, 不斷地向前延伸解途徑. 當沒有規(guī)那么可用, 或向前延伸的形狀都是無解形狀(稱為死點,deadend)時, 沿解途徑后退到

6、前一個形狀(回溯), 重新開場搜索, 直至找到解或宣布失敗. 回溯戰(zhàn)略是一種窮盡的搜索方法.人工智能吉林大學珠海學院計算機科學與技術系 2.1 回溯算法Backtracking Strategies 遞歸過程A simple recursive procedure 輸入: 問題的初始形狀. . The input: the initial state. 輸出:一個規(guī)那么表. 運用這個規(guī)那么表可以把初始形狀變?yōu)槟康男螤? 否那么回答FAIL. The output of the procedure, a list of rules, using it we can get the goal fr

7、om the initial state. If the procedure can not find the solution, it return FAIL.Recursive procedure BACKTRCK(DATA)1 if TERM(DATA), return NIL;2 if DEADEND(DATA), return FAIL;3 RULES APPRULES(DATA);人工智能吉林大學珠海學院計算機科學與技術系4 LOOP: if NULL(RULES), return FAIL;5 R FIRST(RULES);6 RULES TAIL(RULES);7 RDATA

8、R(DATA);8 PATH BACKTRACK( RDATA);9 if PATH = FAIL , go LOOP;10 return CONS( R, PATH)人工智能吉林大學珠海學院計算機科學與技術系In step 3, after get the list of rules using the function APPRULES, we need to order the rules in the lists. The ordering is very important. If the “betterrule is put in the front of the list, it

9、 can be used firstly, the efficiency of the system is high. If the “worse rule is put in the front, the system needs to trymore rules, the efficiency of the system is poor. The Example of Backtracking procedure. The 4 queen problem * * *在利用APPRUKES 得到規(guī)那么表之后, 需求對表中的規(guī)那么排序, 把好的規(guī)那么放在表的前面優(yōu)先運用, 這個排序對算法的效率

10、有很大影響.人工智能吉林大學珠海學院計算機科學與技術系The problem representation the global database: 4*4 array the rule: Rij If i= 1 : there are no queen in the array 1 i= 4: There is a queen in the row i-1 then put a queen in the row i, column jWe order the rules according to the column.我們用Rij表示在棋盤的第 i 行第 j 列放一個王后. 按行的添加順序依

11、次放皇后, 在規(guī)那么的排序上依列的上升次序排序. Termination condition: there are 4 queens in the chess board, they can not kill each other.終止條件: 4 皇后都放到棋盤上, 且不能相互殺死. 人工智能吉林大學珠海學院計算機科學與技術系Order of rules: R11, R12, R13, R14R21, R22, R23,R24deadenddeadenddeadenddeadenddeadenddeadenddeadenddeadenddeadend deadendThere many bac

12、ktrackNIL ()(R43)(R31,R43)(R24,R31,R43)(R12,R24,R31,R43)人工智能吉林大學珠海學院計算機科學與技術系We can use more informed rule ordering using function diag(i,j)我們可以采用含有較多信息的函數(shù)diag(i,j) . Diag(i,j) = the length of the longest diagonal passing through cell(i,j) diag(i,j) 是經過單元(i, j)的最長對角線的長度, 我們按diag(i,j)排序, we order Rmn

13、 before Rij, if diag(m,n) diag(i,j) Rin before Rij, If diag(i,n) = diag(i,j) and n BOUND, return FAIL;6 RULES APPRULES(DATA);人工智能吉林大學珠海學院計算機科學與技術系7 LOOP: if NULL(RULES), return FAIL;8 R FIRST(RULES);9 RULES TAIL(RULES);10 RDATA R(DATA);11 RDATALIST CONS( RDATA, DATALIST);12 PATH BACKTRACK( RDATALIST

14、);13 if PATH = FAIL , go LOOP;14 return CONS( R, PATH)人工智能吉林大學珠海學院計算機科學與技術系1.2 圖搜索戰(zhàn)略graph-search strategies 回溯算法只包含一條探求途徑, 假設發(fā)現(xiàn)deadend節(jié)點或無規(guī)那么可用時要退回來, 因此能夠產生把探求過的節(jié)點擦掉后又重新產生的景象. 在圖搜索算法中.將一切搜索過的形狀用一個圖(搜索圖)記錄下來, 圖的弧反映形狀之間的關系.在圖中選擇節(jié)點加以擴展, 直至把搜索圖擴展到充分大, 包含解途徑在內.人工智能吉林大學珠海學院計算機科學與技術系The main idea of graph

15、searchIn the backtracking procedure, we preserve only a pathfrom the initial state to the current state, so sometimes we need to product some states again after the states were removed. However, in graph search method, We preserve a graph in the memory, the graph include all the states we passed thr

16、ough and the relation of their sequences. When we find some node(state) in the graph is suited to expand for search, we expand it, continue our searching, until a solution is finded.人工智能吉林大學珠海學院計算機科學與技術系圖論與形狀空間表示 有向圖 G是一個偶對(N, E), 其中 N 是節(jié)點集合，E是有向弧的集合。 DECBA有向圖中的有關概念，父親節(jié)點， 兒子節(jié)點， 葉節(jié)點，途徑， 回路， 有向樹。人工智能吉

17、林大學珠海學院計算機科學與技術系用有向圖表示問題的形狀空間是一種很自然的方式， 節(jié)點代表形狀描畫， 弧代表形狀之間的轉移。但是， 問題的形狀描畫與有向圖又有許多本質上的不同， 需求引起我們留意：1。 圖論中研討的有向圖是有限的，我們可以把有向圖全部畫出來。而人工智能中描畫問題的有向圖普通說來是無限的， 或者說雖然有限， 但是非常大，我們不能夠將其畫出來。2。圖論中的問題求解是在對圖完全了解的情況下進展。而我們對形狀空間搜索解的過程是邊產生圖邊求解， 這里所產生的圖是表示形狀空間的無限圖的顯式部分， 從求解的效率 思索， 就有把這個無限圖的顯式部分向哪個方向以何種方式擴展的問題。人工智能吉林大學

18、珠海學院計算機科學與技術系Motivation: the limitation of backtracking procedureSometimes, after analyzing we need to reproduce some states again. DB1 DB2 DB3 DB4R1R2R3人工智能吉林大學珠海學院計算機科學與技術系2.2 graph-search strategies2.2 graph-search strategies Motivation: the limitation of backtracking procedure Sometimes, after a

19、nalyzing we need to reproduce some states again. DB1 DB4R2人工智能吉林大學珠海學院計算機科學與技術系 DB1 DB2 DB4R1R2 DB1 DB2 DB3 DB4R1R2R3人工智能吉林大學珠海學院計算機科學與技術系問題的形狀和它們之間的關系可以用一個圖隱含地加以描畫. 形狀用圖的節(jié)點表示, 形狀之間的關系用圖中的弧表示.the states and their relations are defined by a graph implicitly: states nodes rule applications arcs但是, 我們也

20、應該留意到它們之間的區(qū)別: However, generally the graph is endless , We can not draw the graphsin ordinary way.人工智能吉林大學珠海學院計算機科學與技術系Starting from the initial state, we generate an sub-graph(an explicit part of the graph implicitly defined by production system), then we select the node in the sub-graph to expand

21、it, if the sub-graph does not contain the goal node, we continue to expand it, until the sub-graph is large enough to include the goal node , and we find the solution path from the initial node to the goal node.The procedure GRAPHSEARCH input : the production system(the initial nose, production rule

22、, goal node) output: the solution path from the initial node to a goal node人工智能吉林大學珠海學院計算機科學與技術系 Procedure GRAPHSEARCHG=s, OPEN=(s); G為搜索圖, 初始化為問題的初始形狀s, 建立OPEN表,初始化為只含初始形狀s.CLOSED = (),建立CLOSED表,初始化為空表.LOOP: IF OPEN=(), THEN EXIT(FAIL)n=FIRST(OPEN), REMOVE(n, OPEN), ADD(n, CLOSED); 稱n為當前節(jié)點.IF GOAL(

23、n) THEN EXIT(SUCCESS); 由n循指針前往s, 可以獲得解途徑.EXPAND(n)mi, G=ADD(mi, G), 子節(jié)點集mi中不包含n的父輩節(jié)點.人工智能吉林大學珠海學院計算機科學與技術系 7 標志和修正指針 ADD(mj, OPEN), 并標志mj銜接到n的指針, mj是未在OPEN和CLOSED中出現(xiàn)過的子節(jié)點. 計算能否需求修正mk, ml到n的指針; mk是出如今OPEN表中的子節(jié)點, ml是出如今CLOSED表中的子節(jié)點, Mi=MjMkMl 計算能否需求修正mi到其后記節(jié)點的指針.8.對OPEN表中的節(jié)點按某種原那么重新排序.9.GO LOOP. 人工智能吉

24、林大學珠海學院計算機科學與技術系對 GRAPHSEARCH算法的幾點闡明:兩個圖, G: 搜索圖, 它是記錄算法訪問過的一切節(jié)點的圖,初始化為問題的初始形狀s, 在搜索過程中不斷地擴展. T: G的有向支撐樹, 與G有同樣的節(jié)點, 由指針定義. 記錄由該節(jié)點到s的最短途徑, 在搜索過程中需求不斷調整.2. 兩個表: OPEN和CLOSED, OPEN表記錄搜索圖的前沿, CLOSED表記錄曾經擴展過的節(jié)點.3. 樹T的指針的建立和調整. 樹T中節(jié)點的指針記錄從該節(jié)點到初始節(jié)點s的最短途徑, 隨著算法的進展, 圖的擴展, 這些指針需求不斷地調整. 對新產生的節(jié)點, 為其建立指針. 對OPEN和C

25、LOSED表中的節(jié)點, 需求思索調整其指針, 對于CLOSED表中節(jié)點, 還需求思索調整其后繼節(jié)點的指針.人工智能吉林大學珠海學院計算機科學與技術系Notes about the procedure GRAPHSEARCH 1. Two graphs: G: The explicit part of the graph generated by the production system, its initial node is the initial state, it is expanded constantly. T: the directed support tree of G, it

26、 has same nodesas the graph G, his arc(only one outgoing arc from a node) direct the shortest path from one node to another node. The arcs are marked by pointers. In order to preserve the character, the procedure need to readjust the arcs of the tree constantly.人工智能吉林大學珠海學院計算機科學與技術系2. Two list: OPEN

27、 the frontier nodes of graph G, from which, we select a node to expand. CLOSED the interior nodes of graph G, the node have been expanded. 3. The establishment and readjustment of the pointers of tree T. For the newly generated nodes, we need to establish the pointer for them. For the nodes in the l

28、ists on OPEN and CLOSED , we need to consider to readjust their pointers. For the nodes of CLOSED, we need to consider the readjustment of their descendants, for the adjustment of the nodes of CLOSED may influence their descendants pointers 人工智能吉林大學珠海學院計算機科學與技術系s12人工智能吉林大學珠海學院計算機科學與技術系12人工智能吉林大學珠海學院

29、計算機科學與技術系1.3 1.3 無信息的圖搜索過程無信息的圖搜索過程 深度優(yōu)先和寬度優(yōu)先深度優(yōu)先和寬度優(yōu)先 深度優(yōu)先和寬度優(yōu)先的思想在數(shù)據(jù)構造中曾經講過深度優(yōu)先和寬度優(yōu)先的思想在數(shù)據(jù)構造中曾經講過, , 在在數(shù)據(jù)構造中是作為樹的遍歷的方法講的數(shù)據(jù)構造中是作為樹的遍歷的方法講的, , 人工智能中在形狀人工智能中在形狀空間中搜索解的過程也類似于遍歷空間中搜索解的過程也類似于遍歷. . 所不同的是這里搜索的所不同的是這里搜索的是圖而不是樹是圖而不是樹. .所以這里我們只討論與解有關的問題所以這里我們只討論與解有關的問題 寬度優(yōu)先在搜索解的過程中總是在探求了層數(shù)小于或等寬度優(yōu)先在搜索解的過程中總是在

30、探求了層數(shù)小于或等于于n n的節(jié)點之后才進入到的節(jié)點之后才進入到n+1n+1層節(jié)點的探求層節(jié)點的探求, , 所以這中方法獲所以這中方法獲得的解具有最短的解途徑得的解具有最短的解途徑. .但假設圖的分枝系數(shù)很高但假設圖的分枝系數(shù)很高, , 或者解或者解途徑很長途徑很長, ,效率會很低效率會很低. . 深度優(yōu)先可以很快地使實驗解途徑延伸到很長深度優(yōu)先可以很快地使實驗解途徑延伸到很長, , 假設剛假設剛好在延伸的過程中遇到解好在延伸的過程中遇到解, , 這種方法的效率會很高這種方法的效率會很高, , 但不能但不能保證找到有最短的解途徑保證找到有最短的解途徑. . 甚至即使在原問題有解的時候甚至即使在

31、原問題有解的時候, , 也會發(fā)生會在錯誤的方向上無限延伸下去而找不到解的情況也會發(fā)生會在錯誤的方向上無限延伸下去而找不到解的情況, , 人工智能吉林大學珠海學院計算機科學與技術系深度優(yōu)先算法Procedure DEPTH-FIRTST SEARCH1 G=s, OPEN=(s), CLOSED = ().2 LOOP: IF OPEN=(), THEN EXIT(FAIL) n=FIRST(OPEN);4 IF GOAL(n) THEN EXIT(SUCCESS); 5 REMOVE(n, OPEN), ADD(n, CLOSED); 6 EXPAND(n)mi, G=ADD(mi, G);

32、ADD(mi, OPEN), 并標志mi到n的指針, 把不在OPEN和 CLOSED 中的節(jié)點放在最前面, 使深度大的節(jié)點可以優(yōu)先擴展.8 GO LOOP人工智能吉林大學珠海學院計算機科學與技術系運用 DEPTH-FIRST-SEARCH搜索的例D6C4B4A5H3G4F5E5O2JIKP3TSKKLMNgoal人工智能吉林大學珠海學院計算機科學與技術系為保證深度優(yōu)先算法在問題有解的情況下總能找到解, 需求添加深度限制, 而且深度限制必需超越解的長度.人工智能吉林大學珠海學院計算機科學與技術系 1.4 1.4 啟發(fā)式搜索啟發(fā)式搜索4 4。0 0 簡介簡介 heuristicheuristicO

33、f or relating to a usually speculative Of or relating to a usually speculative formulation serving as a guide in the formulation serving as a guide in the investigation or solution of a problem:investigation or solution of a problem: 探求的探求的, ,做為調查或處理問題的導游的一種通常做為調查或處理問題的導游的一種通常為推測性系統(tǒng)論述為推測性系統(tǒng)論述 回溯式搜索，

34、回溯式搜索， 深度優(yōu)先和寬度優(yōu)先都不運深度優(yōu)先和寬度優(yōu)先都不運用領域知識，用領域知識， 效率很低。效率很低。 啟發(fā)式搜索運用關于領域的信息指點，啟發(fā)式搜索運用關于領域的信息指點， 使使搜索向著有利于獲得解的方向進展。假設運用得搜索向著有利于獲得解的方向進展。假設運用得好，可以明顯地減少搜索空間，好，可以明顯地減少搜索空間， 提高搜索效率提高搜索效率 例如，例如， 在九宮游戲中運用啟發(fā)式搜索，在九宮游戲中運用啟發(fā)式搜索， 就可以顯著地減少搜索空間就可以顯著地減少搜索空間人工智能吉林大學珠海學院計算機科學與技術系MINMAX人工智能吉林大學珠海學院計算機科學與技術系在九宮游戲中運用啟發(fā)式搜索： 運

35、用啟發(fā)函數(shù) h(s) = MAX 已投下的子可以占據(jù)的行， 列和對角線數(shù)人工智能吉林大學珠海學院計算機科學與技術系MINMAX54432434445人工智能吉林大學珠海學院計算機科學與技術系 啟發(fā)式搜索算法啟發(fā)式搜索算法 最正確優(yōu)先搜索。最正確優(yōu)先搜索。 根據(jù)啟發(fā)函數(shù)對尚為探求的節(jié)點進根據(jù)啟發(fā)函數(shù)對尚為探求的節(jié)點進展排序，展排序， 把最有希望的節(jié)點排再前面，把最有希望的節(jié)點排再前面， 在擴展節(jié)點時把最在擴展節(jié)點時把最有希望的節(jié)點拿出來思索。有希望的節(jié)點拿出來思索。 最正確優(yōu)先搜索算法最正確優(yōu)先搜索算法 function best-first-searchfunction best-first-

36、search 算法保管算法保管 2 2 個表，個表， 一個是一個是openopen表，表， 記錄曾經產生但尚記錄曾經產生但尚未探求的節(jié)點，未探求的節(jié)點， 另一個是另一個是closed closed 表，表， 記錄曾經探求過的節(jié)記錄曾經探求過的節(jié)點，點， 算法把新產生的節(jié)點參與到算法把新產生的節(jié)點參與到open open 表中，表中， 然后按啟發(fā)函然后按啟發(fā)函數(shù)值將它們排序，數(shù)值將它們排序， 把最有希望的節(jié)點排在前面，把最有希望的節(jié)點排在前面， 選出來加選出來加以測試和擴展以測試和擴展人工智能吉林大學珠海學院計算機科學與技術系啟發(fā)式搜索算法A評價函數(shù) 根據(jù)領域知識， 對形狀空間的形狀的好壞程度的

37、度量。 通常運用的評價函數(shù)為： f(n)=g(n)+h(n) g*(n) 初始節(jié)點到節(jié)點 n 的間隔. h*(n) 節(jié)點 n 到目的節(jié)點g 的間隔. f*(n)=g*(n)+h*(n), 從初始節(jié)點到目的節(jié)點 g 的間隔. f(n),g(n),h(n)分別是 f*(n), g*(n), h*(n)的估計值.人工智能吉林大學珠海學院計算機科學與技術系A算法Procedure A1 G=s, OPEN=(s), CLOSED = ().2 LOOP: IF OPEN=(), THEN EXIT(FAIL)3 n=FIRST(OPEN);4 IF 4 IF GOAL(n) THEN EXIT(SUC

38、CESS); 5 REMOVE(n, OPEN), ADD(n, CLOSED); EXPAND(n)mi, G=ADD(mi, G); 建立和調整指針, 計算各節(jié)點的f 值. 并按各點的f值調整指針.7 把OPEN表中的節(jié)點按f值從小到大排序.8 GO LOOP人工智能吉林大學珠海學院計算機科學與技術系2 8 31 6 47 52 8 31 6 4 7 52 8 31 47 6 52 8 31 6 47 541+5=61+3=41+5=61 2 38 47 6 5目的形狀h 值是偏離目的位置的塊數(shù)W(n)人工智能吉林大學珠海學院計算機科學與技術系2 8 31 6 47 52 8 31 6 4

39、 7 52 8 31 47 6 52 8 31 6 47 5 2 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5 8 32 1 47 6 52 8 37 1 4 6 512345Goal node6s4A6B4C6D5E5F6G6H7I5J7K5L5M77人工智能吉林大學珠海學院計算機科學與技術系初始化. Open = s4; closed = 1. 測試s4, Open = B4, A6, C6; closed = s42. 測

40、試B4, Open = D5, E5,A6, C6, F6; closed = s4, B4 3. 測試D5, Open = E5,A6, C6, F6,G6, H7; closed = s4, B4, D5 4. 測試E5, Open = I5,A6, C6, F6,G6, H7, J7; closed = s4, B4, D5,E5 5. 測試I5, Open = K5,A6, C6, F6,G6, H7, J7; closed = s4, B4, D5,E5, I5 6. 測試K5, Open = L5,A6, C6, F6,G6, H7, J7, M7; closed = s4, B4

41、, D5,E5, I5,K5 7. L = goal, 勝利找到了解人工智能吉林大學珠海學院計算機科學與技術系2 8 31 6 47 52 8 31 6 4 7 52 8 31 47 6 52 8 31 6 47 5 2 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5 8 32 1 47 6 52 8 37 1 4 6 512345Goal node644646556675755772 8 31 6 47 52 8 31 6 47

42、 5 Closed表中的節(jié)點open表中的節(jié)點選擇節(jié)點 D 擴展時的Open表和closed 表人工智能吉林大學珠海學院計算機科學與技術系2. 爬山法 f(n)=h(n)分支界限法 f(n)=g(n)4. 動態(tài)規(guī)劃法 對分支界限法的改良, 假設有多條到達某一節(jié)點的途徑, 只保管費用最小的一條.人工智能吉林大學珠海學院計算機科學與技術系分支界限法sDAEFtBC32534544設有 7 城市, 城市之間的間隔如圖, 求從s到t的最短通路人工智能吉林大學珠海學院計算機科學與技術系分支界限法sDA1g=02g=33g=4人工智能吉林大學珠海學院計算機科學與技術系分支界限法sDA1g=02g=33g=

43、4DB5g=76g=8人工智能吉林大學珠海學院計算機科學與技術系分支界限法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6人工智能吉林大學珠海學院計算機科學與技術系分支界限法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6Bg=11g=13F109人工智能吉林大學珠海學院計算機科學與技術系分支界限法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6ECg=11g=121112109Bg=11g=13F人工智能吉林大學珠海學院計算機科學與技術系分支界限法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6ECg=1

44、1g=12BEg=10g=11Bg=13FDFBFACtg=14g=16g=15g=14g=15g=15g=1311128109人工智能吉林大學珠海學院計算機科學與技術系動態(tài)規(guī)劃法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6ECBg=11Fg=10tg=14g=131112109人工智能吉林大學珠海學院計算機科學與技術系5. 5. 最正確圖搜索算法最正確圖搜索算法A A* * 在啟發(fā)式搜索中運用評價函數(shù)在啟發(fā)式搜索中運用評價函數(shù) f(n) = g(n) + h(n) f(n) = g(n) + h(n) 其中，其中， g(n) g(n) 是從初始形狀到是從初始形狀到

45、n n 費用；費用； h(n) h(n)是從是從 n n 到目的的啟發(fā)式估計費用到目的的啟發(fā)式估計費用把運用這種估值函數(shù)的啟發(fā)式程序叫做把運用這種估值函數(shù)的啟發(fā)式程序叫做A A算法。算法。 假設形狀空間的圖搜索問題存在解途徑，假設形狀空間的圖搜索問題存在解途徑， 搜索算搜索算法法 f f 一定能找到該問題的最優(yōu)解途徑，一定能找到該問題的最優(yōu)解途徑， 那么稱算那么稱算法法 f f 是可采用的。是可采用的。 假設在假設在A A算法中運用的啟發(fā)函數(shù)滿足算法中運用的啟發(fā)函數(shù)滿足 h(n) h h(n) h* *(n) (n) 那么稱之為那么稱之為 A A* * 算法。算法。人工智能吉林大學珠海學院計算

46、機科學與技術系 A*算法是可采用的假設存在從初始節(jié)點s到目的節(jié)點t的途徑， 那么A*算法必能找到最正確解途徑。 例如， 在寬度優(yōu)先搜索中， h(n) 0，滿足 h(n) h*(n) ， 是可采用的。和前面舉例的f(n) = g(n) + h(n)中， h(n)取為偏離目的位置的塊數(shù)， 滿足h(n) h*(n) ，也是可采用的。人工智能吉林大學珠海學院計算機科學與技術系單調性單調性 在算法在算法 A 中，中， g(n)是是 g*(n) 的估計值，的估計值， 定義為在曾經產生定義為在曾經產生的節(jié)點中從初始節(jié)點到的節(jié)點中從初始節(jié)點到 n 的最短途徑的費用，的最短途徑的費用， 在算法進展的在算法進展的

47、過程中，過程中， 我們需求不斷地計算，我們需求不斷地計算， 比較和調整這條最短途徑，比較和調整這條最短途徑， 這要耗費大量的計算時間，因此也影響算法的效率，假設能這要耗費大量的計算時間，因此也影響算法的效率，假設能對啟發(fā)函數(shù)添加某些限制條件，對啟發(fā)函數(shù)添加某些限制條件， 使得在這種限制條件下，實使得在這種限制條件下，實際上就可以證明際上就可以證明 g(n) 就是就是 g*(n), 那么為獲得那么為獲得 g(n)所需求的計所需求的計算就可以省略了。算就可以省略了。 這個條件就是單調性。這個條件就是單調性。 定義：定義： 單調性單調性 啟發(fā)函數(shù)單調的條件是：啟發(fā)函數(shù)單調的條件是： 1。 對于一切的

48、形狀對于一切的形狀ni和和nj， 其中其中nj是是ni的后繼的后繼 h(ni) - h(nj) cost(ni, nj) cost(ni, nj)是節(jié)點是節(jié)點ni和和nj之間的實踐最小費用之間的實踐最小費用 2。 h(goal) = 0 人工智能吉林大學珠海學院計算機科學與技術系啟發(fā)函數(shù)的比較啟發(fā)函數(shù)的比較 設有兩個算法，設有兩個算法， 分別運用兩個啟發(fā)函數(shù)分別運用兩個啟發(fā)函數(shù) 算法算法1， f1(n) = g1(n) + h1(n) 算法算法2， f2(n) = g2(n) + h2(n) 哪一個更好一些呢？哪一個更好一些呢？定義定義 信息度信息度 對于兩個對于兩個A*啟發(fā)式函數(shù)啟發(fā)式函數(shù)h

49、1(n)和和 h2(n)， 假設對于搜索假設對于搜索空間中的一切的節(jié)點空間中的一切的節(jié)點 n, 都有都有 h1(n) h2(n)那么稱那么稱h2(n) 比比 h1(n)有更高的信息度。有更高的信息度。 假設假設h2(n) 比比 h1(n)有更高的信息度，有更高的信息度， 那么算法那么算法2所擴展所擴展的節(jié)點一定會被算法的節(jié)點一定會被算法1所擴展，所擴展， 換句話說，換句話說， 算法算法2所擴展所擴展的節(jié)點比算法的節(jié)點比算法1擴展的節(jié)點少。擴展的節(jié)點少。人工智能吉林大學珠海學院計算機科學與技術系 A*算法的運用舉例算法的運用舉例. (1) 8 數(shù)碼問題數(shù)碼問題 h(n) = P(n), P(n)

50、為每一方塊與目的位置的間隔的總和為每一方塊與目的位置的間隔的總和. (2) 傳教士與野人問題傳教士與野人問題 h(n)=0 h(n)=M+C h(n)=M+C-2B傳教士與野人渡河問題：有 N 個傳教士帶 N 個野人渡河，河的岸邊有一條船， 每次最多可載 K 人，要求無論在河的哪一邊，或是在船上，野人的數(shù)目不能超越傳教士的數(shù)目，問為平安起見， 應如何安排傳教士與野人渡河？N=5， K=3。人工智能吉林大學珠海學院計算機科學與技術系2 8 31 6 47 52 8 31 6 4 7 52 8 31 47 6 52 8 31 6 47 5 2 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5 8 32 1 47 6 52 8 37 1 4