【正文】 算法 1， f1(n) = g1(n) + h1(n) 算法 2， f2(n) = g2(n) + h2(n) 哪一個(gè)更好一些呢？ 定義 信息度 對(duì)于兩個(gè) A*啟發(fā)式函數(shù) h1(n)和 h2(n)， 如果對(duì)于搜索空間中的所有的節(jié)點(diǎn) n, 都有 h1(n) ≦ h2(n) 則稱(chēng) h2(n) 比 h1(n)有更高的信息度。 如果在 A算法中使用的啟發(fā)函數(shù)滿(mǎn)足 h(n) ≦ h*(n) 則稱(chēng)之為 A* 算法。 closed = [] 1. 測(cè)試 s4, Open = [B4, A6, C6]。如果應(yīng)用得好，可以明顯地縮小搜索空間， 提高搜索效率 例如， 在九宮游戲中使用啟發(fā)式搜索， 就可以顯著地減少搜索空間 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 MIN MAX 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 在九宮游戲中使用啟發(fā)式搜索： 使用啟發(fā)函數(shù) h(s) = MAX 已投下的子可以占據(jù)的行， 列和對(duì)角線數(shù) 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 MIN MAX 5 4 4 3 2 4 3 4 4 4 5 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 啟發(fā)式搜索算法 最佳優(yōu)先搜索。 由 n循指針?lè)祷?s, 可以獲得解路徑 . 6. EXPAND(n)→mi, G=ADD(mi, G), 子節(jié)點(diǎn)集 {mi}中不包含 n的父輩節(jié)點(diǎn) . 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 7 標(biāo)記和修改指針 ADD(mj, OPEN), 并標(biāo)記 mj連接到 n的指針 , mj是未在 OPEN和 CLOSED中出現(xiàn)過(guò)的子節(jié)點(diǎn) . 計(jì)算是否需要修改 mk, ml到 n的指針 。 圖論中研究的有向圖是有限的，我們可以把有向圖全部畫(huà)出來(lái)。 10 RDATA ← R(DATA)。 2 if MEMBER(DATA, TAIL(DATALIST)), return FAIL。 3 RULES ← APPRULES(DATA)。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 狀態(tài)空間 1. 計(jì)算機(jī)對(duì)傳統(tǒng)的問(wèn)題求解方法帶來(lái)了根本性的改變。 8. 搜索算法的討論。 2 if DEADEND(DATA), return FAIL。 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ī)則表之后 , 需要對(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ì)角線的長(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)。 9 RULES ← TAIL(RULES)。 但是， 問(wèn)題的狀態(tài)描述與有向圖又有許多本質(zhì)上的不同， 需要引起我們注意： 1。 稱(chēng)n為當(dāng)前節(jié)點(diǎn) . 5. IF GOAL(n) THEN EXIT(SUCCESS)。 啟發(fā)式搜索使用關(guān)于領(lǐng)域的信息指導(dǎo)， 使搜索向著有利于獲得解的方向進(jìn)展。 7 建立和調(diào)整指針 , 計(jì)算各節(jié)點(diǎn)的 f 值 . 并按各點(diǎn)的 f值調(diào)整指針 . ? 7 把 OPEN表中的節(jié)點(diǎn)按 f值從小到大排序 . ? 8 GO LOOP 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 4 1+5=6 1+3=4 1+5=6 1 2 3 8 4 7 6 5 目標(biāo)狀態(tài) h 值是偏離目標(biāo)位置的塊數(shù) W(n) 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2