【正文】 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 第 1 章 搜索問題 1. 什么是狀態(tài)空間？ 2. 回溯策略。 3. 圖搜索策略 4. 無信息的圖搜索策略 5. 啟發(fā)式圖搜索策略 6. A*算法。 7. A*算法的性質(zhì)。 8. 搜索算法的討論。 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 狀態(tài)空間 1. 計算機對傳統(tǒng)的問題求解方法帶來了根本性的改變。 2. 傳統(tǒng)方法， 由專家給出公式， 使用者的任務(wù)是理解公式， 應(yīng)用公式。 3. 有些問題用傳統(tǒng)方法描述很困難 , 例如本節(jié)的幾個例子 4. 公式的推導(dǎo)需要很高的水平， 與實際問題相差較遠(yuǎn)，對應(yīng)用者要求很高。 5. 2. 計算機利用自己強大的計算能力和存儲能力 , 采用”猜”的方式 , 試探法 . 能解決問題的領(lǐng)域更廣 , 更結(jié)合實際 . 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 例 智力游戲問題：傳教士與野人渡河問題 傳教士與野人渡河問題：有 3 個傳教士帶 3 個野人渡河，河的岸邊有一條船， 每次最多可載 2 人，要求無論在河的哪一邊，野人的數(shù)目不能超過傳教士的數(shù)目，問為安全起見， 應(yīng)如何安排傳教士與野人渡河？ 一種較為簡單的表示方式 3 元向量（ x, y, z） x: 河此岸的傳教士數(shù)， y: 河此岸的野人數(shù)。 x,y 取值范圍 {0， 1， 2， 3} z: 船在此岸， z取值范圍 {0， 1} 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(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 個標(biāo)有數(shù)字的硬紙片， 這些硬紙片上標(biāo)的數(shù)字分別是 1， 2， ?, 8 ， 每個紙片都可以移進(jìn)相鄰的空格， 8 數(shù)碼難題的初始狀態(tài)和目標(biāo)狀態(tài)分別列出如下，問如何把這個問題由初始狀態(tài)移向目標(biāo)狀態(tài)？ 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 2 8 3 1 6 4 7 5 1 2 3 8 6 4 7 5 Initial Goal 8 數(shù)碼難題（ 8puzzle）的矩陣描述 對于 8 數(shù)碼難題， 我們選用直接的矩陣描述，解題過程中的任何一個中間情況都對應(yīng)一個 3*3的矩陣， 用 0,1，2， ?, 8 這 9個數(shù)的一個排列依次去充填這個矩陣的各個單元 ,就是求解問題的一個可能的情況 , 共有 9!種。 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 1 4 3 7 6 5 8 2 1 3 7 4 6 5 8 2 1 4 3 7 6 5 8 2 1 2 3 7 8 6 5 2 1 2 3 7 6 5 8 2 1 3 7 4 6 5 8 2 1 3 7 4 6 5 8 2 1 4 3 1 7 6 5 8 2 1 4 3 5 7 6 8 2 1 4 3 7 8 6 5 2 1 4 3 7 8 6 5 2 1 4 3 7 6 3 5 8 2 1 4 3 7 6 2 5 8 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 例 旅行推銷員問題 A B D C E 75 100 125 125 50 100 50 75 125 100 125 問題表示 , 形式為 (A****)的字符串和 (A****A)的字符串。 其中 ****為 B,C, D, E 的排列 . 問題的節(jié)，形式為 (A****A)的字符串 , 其中 ****為 B,C, D, E 的排列 . 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 旅行推銷員問題的搜索空間 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é)院計算機科學(xué)與技術(shù)系 回溯策略 回溯策略的主要思想 : 只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條解路徑 , 給變換狀態(tài)的規(guī)則給出一個排序方法 , 對當(dāng)前狀態(tài)使用規(guī)則產(chǎn)生新的狀態(tài) , 不斷地向前延伸解路徑 . 當(dāng)沒有規(guī)則可用 , 或向前延伸的狀態(tài)都是無解狀態(tài) (稱為死點 ,deadend)時 , 沿解路徑后退到前一個狀態(tài) (回溯 ), 重新開始搜索 , 直至找到解或宣布失敗 . 回溯策略是一種窮盡的搜索方法 . 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 回溯算法 Backtracking Strategies 遞歸過程 A simple recursive procedure 輸入 : 問題的初始狀態(tài) . . The input: the initial state. 輸出 :一個規(guī)則表 . 應(yīng)用這個規(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。 2 if DEADEND(DATA), return FAIL。 3 RULES ← APPRULES(DATA)。 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 4 LOOP: if NULL(RULES), return FAIL。 5 R ← FIRST(RULES)。 6 RULES ← TAIL(RULES)。 7 RDATA ← R(DATA)。 8 PATH ←BACKTRACK( RDATA)。 9 if PATH = FAIL , go LOOP。 10 return CONS( R, PATH) 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 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 “ better” rule is put in the front of the list, it can be used firstly, the efficiency of the system is high. If the “ worse” rule is put in the front, the system needs to try more rules, the efficiency of the system is poor. The Example of Backtracking procedure. The 4 queen problem * * * 在利用 APPRUKES 得到規(guī)則表之后 , 需要對表中的規(guī)則排序 , 把好的規(guī)則放在表的前面優(yōu)先使用 , 這個排序?qū)λ惴ǖ男视泻艽笥绊?. 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 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 i1 then put a queen in the row i, column j We order the rules according to the column. 我們用 Rij表示在棋盤的第 i 行第 j 列放一個王后 . 按行的增加順序依次放皇后 , 在規(guī)則的排序上依列的上升次序排序 . Termination condition: there are 4 queens in the chess board, they can not kill each other. 終止條件 : 4 皇后都放到棋盤上 , 且不能互相殺死 .