【正文】 人工智能 吉林大學(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)的最長(zhǎng)對(duì)角線的長(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)。 2 if MEMBER(DATA, TAIL(DATALIST)), return FAIL。 3 if TERM(DATA), return NIL。 4 if DEADEND(DATA), return FAIL。 5 if LENGTH(DATALIST) BOUND, return FAIL。 6 RULES ← APPRULES(DATA)。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 7 LOOP: if NULL(RULES), return FAIL。 8 R ← FIRST(RULES)。 9 RULES ← TAIL(RULES)。 10 RDATA ← R(DATA)。 11 RDATALIST ←CONS( RDATA, DATALIST)。 12 PATH ←BACKTRACK( RDATALIST)。 13 if PATH = FAIL , go LOOP。 14 return CONS( R, PATH) 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 圖搜索策略 graphsearch strategies 回溯算法只包含一條探索路徑 , 如果發(fā)現(xiàn)deadend節(jié)點(diǎn)或無規(guī)則可用時(shí)要退回來 , 因此可能產(chǎn)生把探索過的節(jié)點(diǎn)擦掉后又重新產(chǎn)生的現(xiàn)象 . 在圖搜索算法中 .將所有搜索過的狀態(tài)用一個(gè)圖 (搜索圖 )記錄下來 , 圖的弧反映狀態(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是有向弧的集合。 D E C B A 有向圖中的有關(guān)概念，父親節(jié)點(diǎn)， 兒子節(jié)點(diǎn)， 葉節(jié)點(diǎn)，路徑， 回路， 有向樹。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 用有向圖表示問題的狀態(tài)空間是一種很自然的方式， 節(jié)點(diǎn)代表狀態(tài)描述， 弧代表狀態(tài)之間的轉(zhuǎn)移。 但是， 問題的狀態(tài)描述與有向圖又有許多本質(zhì)上的不同， 需要引起我們注意： 1。 圖論中研究的有向圖是有限的，我們可以把有向圖全部畫出來。而人工智能中描述問題的有向圖一般說來是無限的， 或者說雖然有限， 但是非常大，我們不可能將其畫出來。 2。圖論中的問題求解是在對(duì)圖完全了解的情況下進(jìn)行。而我們對(duì)狀態(tài)空間搜索解的過程是邊產(chǎn)生圖邊求解， 這里所產(chǎn)生的圖是表示狀態(tài)空間的無限圖的顯式部分， 從求解的效率 考慮， 就有把這個(gè)無限圖的顯式部分向哪個(gè)方向以何種方式擴(kuò)展的問題。 人工智能 吉林大學(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 backtracking procedure ? Sometimes, after analyzing we need to reproduce some states again. DB1 DB4 R2 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 DB1 DB2 DB4 R1 R2 DB1 DB2 DB3 DB4 R1 R2 R3 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 問題的狀態(tài)和它們之間的關(guān)系可以用一個(gè)圖隱含地加以描述 . 狀態(tài)用圖的節(jié)點(diǎn)表示 , 狀態(tài)之間的關(guān)系用圖中的弧表示 . the states and their relations are defined by a graph implicitly: states ———————— nodes rule applications —————— arcs 但是 , 我們也應(yīng)該注意到它們之間的區(qū)別 : However, generally the graph is endless , We can not draw the graphsin ordinary way. 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 Starting from the initial state, we generate an subgraph(an explicit part of the graph implicitly defined by production system), then we select the node in the subgraph to expand it, if the subgraph does not conta