【正文】 The Example of Backtracking procedure. The 4 queen problem * * * 在利用 APPRUKES 得到規(guī)則表之后 , 需要對表中的規(guī)則排序 , 把好的規(guī)則放在表的前面優(yōu)先使用 , 這個排序對算法的效率有很大影響 . 人工智能 吉林大學珠海學院計算機科學與技術系 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 皇后都放到棋盤上 , 且不能互相殺死 . 人工智能 吉林大學珠海學院計算機科學與技術系 Order of rules: R11, R12, R13, R14 R21, R22, R23,R24 deadend deadend deadend deadend deadend deadend deadend deadend deadend deadend There many backtrack NIL () (R43) (R31,R43) (R24,R31,R43) (R12,R24,R31,R43) 人工智能 吉林大學珠海學院計算機科學與技術系 We can use more informed rule ordering using function diag(i,j) 我們可以采用含有較多信息的函數 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 before Rij, if diag(m,n) diag(i,j) Rin before Rij, If diag(i,n) = diag(i,j) and nj Homework: Solve the 4 queens problem by using backtracking procedure and function diag BACKTRACK1: to avoid cycle 1. The argument of the procedure is changed, from a single state to a list of state. 2. Use MEMBER function to check cycle. 3. Add depth bound 人工智能 吉林大學珠海學院計算機科學與技術系 Backtracking Strategies A simple recursive procedure The input of the procedure, DATA : the initial state. 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(DATALIST) 1 DATA ← FIRST(DATALIST)。 6 RULES ← TAIL(RULES)。 2 if DEADEND(DATA), return FAIL。 2. 計算機利用自己強大的計算能力和存儲能力 , 采用”猜”的方式 , 試探法 . 能解決問題的領域更廣 , 更結合實際 . 人工智能 吉林大學珠海學院計算機科學與技術系 例 智力游戲問題：傳教士與野人渡河問題 傳教士與野人渡河問題：有 3 個傳教士帶 3 個野人渡河，河的岸邊有一條船， 每次最多可載 2 人，要求無論在河的哪一邊，野人的數目不能超過傳教士的數目，問為安全起見， 應如何安排傳教士與野人渡河？ 一種較為簡單的表示方式 3 元向量（ x, y, z） x: 河此岸的傳教士數， y: 河此岸的野人數。 8. 搜索算法的討論。人工智能 吉林大學珠海學院計算機科學與技術系 第 1 章 搜索問題 1. 什么是狀態(tài)空間？ 2. 回溯策略。 人工智能 吉林大學珠海學院計算機科學與技術系 狀態(tài)空間 1. 計算機對傳統(tǒng)的問題求解方法帶來了根本性的改變。 x,y 取值范圍 {0， 1， 2， 3} z: 船在此岸， z取值范圍 {0， 1} 人工智能 吉林大學珠海學院計算機科學與技術系 初始狀態(tài) ： （ 3， 3， 1） 目標狀態(tài)： （ 0， 0， 0） 2 8 3 1 6 4 7 5 1 2 3 8 6 4 7 5 初始狀態(tài) Initial 目標狀態(tài) Goal 例 設有 8 數碼難題如下 :在 3 3 的框架中有 8 個標有數字的硬紙片， 這些硬紙片上標的數字分別是 1， 2， …, 8 ， 每個紙片都可以移進相鄰的空格， 8 數碼難題的初始狀態(tài)和目標狀態(tài)分別列出如下，問如何把這個問題由初始狀態(tài)移向目標狀態(tài)？ 人工智能 吉林大學珠海學院計算機科學與技術系 2 8 3 1 6 4 7 5 1 2 3 8 6 4 7 5 Initial Goal 8 數碼難題（ 8puzzle）的矩陣描述 對于 8 數碼難題， 我們選用直接的矩陣描述，解題過程中的任何一個中間情況都對應一個 3*3的矩陣， 用 0,1，2， … , 8這 9個數的一個排列依次去充填這個矩陣的各個單元 ,就是求解問題的一個可能的情況 , 共有 9!種。 3 RULES ← APPRULES(DATA)。 7 RDATA ← R(DATA)。 2 if MEMBER(DATA, TAIL(DATALIST)), return FAIL。 6 RULES ← APPRULES(DATA)。 10 RDATA ← R(DATA)。 14 return CONS( R, PATH) 人工智能 吉林大學珠海學院計算機科學與技術系 圖搜索策略 graphsearch strategies 回溯算法只包含一條探索路徑 , 如果發(fā)現(xiàn)deadend節(jié)點或無規(guī)則可用時要退回來 , 因此可能產生把探索過的節(jié)點擦掉后又重新產生的現(xiàn)象 . 在圖搜索算法中 .將所有搜索過的狀態(tài)用一個圖 (搜索圖 )記錄下來 , 圖的弧反映狀態(tài)之間的關系 .在圖中選擇節(jié)點加以擴展 , 直至把搜索圖擴展到充分大 , 包含解路徑在內 . 人工智能 吉林大學珠海學院計算機科學與技術系 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. 人工智