【正文】 xample of Backtracking procedure. The 4 queen problem * * * 在利用 APPRUKES 得到規(guī)則表之后 , 需要對(duì)表中的規(guī)則排序 , 把好的規(guī)則放在表的前面優(yōu)先使用 , 這個(gè)排序?qū)λ惴ǖ男视泻艽笥绊?. 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(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表示在棋盤(pán)的第 i 行第 j 列放一個(gè)王后 . 按行的增加順序依次放皇后 , 在規(guī)則的排序上依列的上升次序排序 . Termination condition: there are 4 queens in the chess board, they can not kill each other. 終止條件 : 4 皇后都放到棋盤(pán)上 , 且不能互相殺死 . 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 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) 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 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) 是通過(guò)單元 (i, j)的最長(zhǎng)對(duì)角線(xiàn)的長(zhǎng)度 , 我們按 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 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 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。 5. 2. 計(jì)算機(jī)利用自己強(qiáng)大的計(jì)算能力和存儲(chǔ)能力 , 采用”猜”的方式 , 試探法 . 能解決問(wèn)題的領(lǐng)域更廣 , 更結(jié)合實(shí)際 . 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 例 智力游戲問(wèn)題：傳教士與野人渡河問(wèn)題 傳教士與野人渡河問(wèn)題：有 3 個(gè)傳教士帶 3 個(gè)野人渡河，河的岸邊有一條船， 每次最多可載 2 人，要求無(wú)論在河的哪一邊，野人的數(shù)目不能超過(guò)傳教士的數(shù)目，問(wèn)為安全起見(jiàn)， 應(yīng)如何安排傳教士與野人渡河？ 一種較為簡(jiǎn)單的表示方式 3 元向量（ x, y, z） x: 河此岸的傳教士數(shù)， y: 河此岸的野人數(shù)。 8. 搜索算法的討論。人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 第 1 章 搜索問(wèn)題 1. 什么是狀態(tài)空間？ 2. 回溯策略。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 狀態(tài)空間 1. 計(jì)算機(jī)對(duì)傳統(tǒng)的問(wèn)題求解方法帶來(lái)了根本性的改變。 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!種。 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) 人工智能 吉林大學(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)空間表示