【正文】 式 , 試探法 . 能解決問題的領(lǐng)域更廣 , 更結(jié)合實(shí)際 . 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 例 智力游戲問題：傳教士與野人渡河問題 傳教士與野人渡河問題：有 3 個(gè)傳教士帶 3 個(gè)野人渡河，河的岸邊有一條船， 每次最多可載 2 人，要求無論在河的哪一邊，野人的數(shù)目不能超過傳教士的數(shù)目，問為安全起見， 應(yīng)如何安排傳教士與野人渡河？ 一種較為簡單的表示方式 3 元向量（ x, y, z） x: 河此岸的傳教士數(shù)， y: 河此岸的野人數(shù)。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(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é)院計(jì)算機(jī)科學(xué)與技術(shù)系 例 旅行推銷員問題 A B D C E 75 100 125 125 50 100 50 75 125 100 125 問題表示 , 形式為 (A****)的字符串和 (A****A)的字符串。 2 if DEADEND(DATA), return FAIL。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 4 LOOP: if NULL(RULES), return FAIL。 6 RULES ← TAIL(RULES)。 8 PATH ←BACKTRACK( RDATA)。 10 return CONS( R, PATH) 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(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)先使用 , 這個(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表示在棋盤的第 i 行第 j 列放一個(gè)王后 . 按行的增加順序依次放皇后 , 在規(guī)則的排序上依列的上升次序排序 . Termination condition: there are 4 queens in the chess board, they can not kill each other. 終止條件 : 4 皇后都放到棋盤上 , 且不能互相殺死 . 人工智能 吉林大學(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) 是通過單元 (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 人工智能 吉林大學(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)。 3 if TERM(DATA), return NIL。 5 if LENGTH(DATALIST) BOUND, return FAIL。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 7 LOOP: if NULL(RULES), return FAIL。 9 RULES ← TAIL(RULES)。 11 RDATALIST ←CONS( RDATA, DATALIST)。 13 if PATH = FAIL , go LOOP。 D E C B A 有向圖中的有關(guān)概念，父親節(jié)點(diǎn)， 兒子節(jié)點(diǎn)， 葉節(jié)點(diǎn)，路徑， 回路， 有向樹。 但是， 問題的狀態(tài)描述與有向圖又有許多本質(zhì)上的不同， 需要引起我們注意： 1。而人工智能中描述問題的有向圖一般說來是無限的， 或者說雖然有限， 但是非常大，我們不可能將其畫出來。圖論中的問題求解是在對圖完全了解的情況下進(jìn)行。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 ? Motivation: the limitation of backtracking procedure ? Sometimes, after analyzing we need to reproduce some states again. DB1 DB2 DB3 DB4 R1 R2 R3 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 graphsearch strategies ? Motivation: the limitation of backtrack