【正文】 珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 MIN MAX 5 4 4 3 2 4 3 4 4 4 5 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 啟發(fā)式搜索算法 最佳優(yōu)先搜索。 0 簡(jiǎn)介 heuristic Of or relating to a usually speculative formulation serving as a guide in the investigation or solution of a problem: 探索的 ,做為調(diào)查或解決問(wèn)題的向?qū)У囊环N通常為推測(cè)性系統(tǒng)闡述 回溯式搜索， 深度優(yōu)先和寬度優(yōu)先都不使用領(lǐng)域知識(shí)， 效率很低。 6 EXPAND(n)→{mi}, G=ADD(mi, G)。 4 IF GOAL(n) THEN EXIT(SUCCESS)。 由 n循指針?lè)祷?s, 可以獲得解路徑 . 6. EXPAND(n)→mi, G=ADD(mi, G), 子節(jié)點(diǎn)集 {mi}中不包含 n的父輩節(jié)點(diǎn) . 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 7 標(biāo)記和修改指針 ADD(mj, OPEN), 并標(biāo)記 mj連接到 n的指針 , mj是未在 OPEN和 CLOSED中出現(xiàn)過(guò)的子節(jié)點(diǎn) . 計(jì)算是否需要修改 mk, ml到 n的指針 。 G為搜索圖 , 初始化為問(wèn)題的初始狀態(tài) s, 建立 OPEN表 ,初始化為只含初始狀態(tài) s. 2. CLOSED = (),建立 CLOSED表 ,初始化為空表 . 3. LOOP: IF OPEN=(), THEN EXIT(FAIL) 4. n=FIRST(OPEN), REMOVE(n, OPEN), ADD(n, CLOSED)。而我們對(duì)狀態(tài)空間搜索解的過(guò)程是邊產(chǎn)生圖邊求解， 這里所產(chǎn)生的圖是表示狀態(tài)空間的無(wú)限圖的顯式部分， 從求解的效率 考慮， 就有把這個(gè)無(wú)限圖的顯式部分向哪個(gè)方向以何種方式擴(kuò)展的問(wèn)題。 2。 圖論中研究的有向圖是有限的，我們可以把有向圖全部畫出來(lái)。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 用有向圖表示問(wèn)題的狀態(tài)空間是一種很自然的方式， 節(jié)點(diǎn)代表狀態(tài)描述， 弧代表狀態(tài)之間的轉(zhuǎn)移。 14 return CONS( R, PATH) 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 圖搜索策略 graphsearch strategies 回溯算法只包含一條探索路徑 , 如果發(fā)現(xiàn)deadend節(jié)點(diǎn)或無(wú)規(guī)則可用時(shí)要退回來(lái) , 因此可能產(chǎn)生把探索過(guò)的節(jié)點(diǎn)擦掉后又重新產(chǎn)生的現(xiàn)象 . 在圖搜索算法中 .將所有搜索過(guò)的狀態(tài)用一個(gè)圖 (搜索圖 )記錄下來(lái) , 圖的弧反映狀態(tài)之間的關(guān)系 .在圖中選擇節(jié)點(diǎn)加以擴(kuò)展 , 直至把搜索圖擴(kuò)展到充分大 , 包含解路徑在內(nèi) . 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 The main idea of graph search In the backtracking procedure, we preserve only a path from 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 through 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. 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 圖論與狀態(tài)空間表示 有向圖 G是一個(gè)偶對(duì) (N, E), 其中 N 是節(jié)點(diǎn)集合， E是有向弧的集合。 12 PATH ←BACKTRACK( RDATALIST)。 10 RDATA ← R(DATA)。 8 R ← FIRST(RULES)。 6 RULES ← APPRULES(DATA)。 4 if DEADEND(DATA), return FAIL。 2 if MEMBER(DATA, TAIL(DATALIST)), return FAIL。 9 if PATH = FAIL , go LOOP。 7 RDATA ← R(DATA)。 5 R ← FIRST(RULES)。 3 RULES ← APPRULES(DATA)。 其中 ****為 B,C, D, E 的排列 . 問(wèn)題的節(jié)，形式為 (A****A)的字符串 , 其中 ****為 B,C, D, E 的排列 . 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 旅行推銷員問(wèn)題的搜索空間 E A D C B C D E A E D A D C E A E 100 125 100 75 150 175 425 225 325 275 375 300 250 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 回溯策略 回溯策略的主要思想 : 只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條解路徑 , 給變換狀態(tài)的規(guī)則給出一個(gè)排序方法 , 對(duì)當(dāng)前狀態(tài)使用規(guī)則產(chǎn)生新的狀態(tài) , 不斷地向前延伸解路徑 . 當(dāng)沒(méi)有規(guī)則可用 , 或向前延伸的狀態(tài)都是無(wú)解狀態(tài) (稱為死點(diǎn) ,deadend)時(shí) , 沿解路徑后退到前一個(gè)狀態(tài) (回溯 ), 重新開(kāi)始搜索 , 直至找到解或宣布失敗 . 回溯策略是一種窮盡的搜索方法 . 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 回溯算法 Backtracking Strategies 遞歸過(guò)程 A simple recursive procedure 輸入 : 問(wèn)題的初始狀態(tài) . . The input: the initial state. 輸出 :一個(gè)規(guī)則表 . 應(yīng)用這個(gè)規(guī)則表可以把初始狀態(tài)變?yōu)槟繕?biāo)狀態(tài) . 否則回答 FAIL. The output of the procedure, a list of rules, using it we can get the goal from the initial state. If the procedure can not find the solution, it return FAIL. Recursive procedure BACKTRCK(DATA) 1 if TERM(DATA), return NIL。 x,y 取值范圍 {0， 1， 2， 3} z: 船在此岸， z取值范圍 {0， 1} 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 初始狀態(tài) ： （ 3， 3， 1） 目標(biāo)狀態(tài)： （ 0， 0， 0） 2 8 3 1 6 4 7 5 1 2 3 8 6 4 7 5 初始狀態(tài) Initial 目標(biāo)狀態(tài) Goal 例 設(shè)有 8 數(shù)碼難題如下 :在 3 3 的框架中有 8 個(gè)標(biāo)有數(shù)字的硬紙片， 這些硬紙片上標(biāo)的數(shù)字分別是 1， 2， …, 8 ， 每個(gè)紙片都可以移進(jìn)相鄰的空格， 8 數(shù)碼難題的初始狀態(tài)和目標(biāo)狀態(tài)分別列出如下，問(wèn)如何把這個(gè)問(wèn)題由初始狀態(tài)移向目標(biāo)狀態(tài)？ 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 2 8 3 1 6 4 7 5 1 2 3 8 6 4 7 5 Initial Goal 8 數(shù)碼難題（ 8puzzle）的矩陣描述 對(duì)于 8 數(shù)碼難題， 我們選用直接的矩陣描述，解題過(guò)程中的任何一個(gè)中間情況都對(duì)應(yīng)一個(gè) 3*3的矩陣， 用 0,1，2， … , 8這 9個(gè)數(shù)的一個(gè)排列依次去充填這個(gè)矩陣的各個(gè)單元 ,就是求解問(wèn)題的一個(gè)可能的情況 , 共有 9!種。 有些問(wèn)題用傳統(tǒng)方法描述很困難 , 例如本節(jié)的幾個(gè)例子 公式的推導(dǎo)需要很高的水平， 與實(shí)際問(wèn)題相差較遠(yuǎn)，對(duì)應(yīng)用者要求很高。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 狀態(tài)空間 1. 計(jì)算機(jī)對(duì)傳統(tǒng)的問(wèn)題求解方法帶來(lái)了根本性的改變。 7. A*算法的性質(zhì)。人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 第 1 章 搜索問(wèn)題 1. 什么是狀態(tài)空間？ 2. 回溯策略。 3. 圖搜索策略 4. 無(wú)信息的圖搜索策略 5. 啟發(fā)式圖搜索策略 6. A*算法。 8. 搜索算法的討論。 傳統(tǒng)方法， 由專家給出公式， 使用者的任務(wù)是理解公式， 應(yīng)用公式。 2. 計(jì)算機(jī)利用自己強(qiáng)大的計(jì)算能力和存儲(chǔ)能力 , 采用”猜”的方式 , 試探法 . 能解決問(wèn)題的領(lǐng)域更廣 , 更結(jié)合實(shí)際 . 人