第五講經(jīng)典人工智能技術—知識表示、推理與搜索77(文件)
【正文】 短路徑呢？ 問題有了，可怎么讓計算機知道這些問題呢？ 智能科學與技術系 問題表示 ——狀態(tài)空間圖 例： 真空吸塵器的世界 假設：吸塵器的世界只有兩塊地毯大小，地毯或者是臟的，或者是干凈的 吸塵器能做的動作只有三個 {向左 (Left)，向右 (Right)，吸塵 (Suck)} 一共有多少種可能的情況？ 狀態(tài) 智能科學與技術系 狀態(tài)轉換 狀態(tài)之間可以互相轉換 狀態(tài)空間圖 智能科學與技術系 傳教士野人問題 （ Missionaries Cannibals， MC問題） 有三個傳教士 M和三個野人 C過河，只有一條能裝下兩個人的船，在河的一方或者船上，如果野人的人數(shù)大于傳教士的人數(shù)，那么傳教士就會有危險，你能不能提出一種安全的渡河方法呢？ 智能科學與技術系 狀態(tài)及其表示 狀態(tài)：問題在某一時刻所處的 “ 位置 ” ， “ 情況 ” 等 根據(jù)問題所關心的因素，一般用向量形式表示，每一位表示一個因素 0：右岸 1：左岸 初始狀態(tài)： (0, 0, 0) 目標狀態(tài)： (3, 3, 1) 哪些操作能導致狀態(tài)變化？ 狀態(tài)可有多種表示方法： (左岸傳教士數(shù) , 右岸傳教士數(shù) , 左岸野人數(shù) , 右岸野人數(shù) , 船的位置 ) 或 (左岸傳教士數(shù) , 左岸野人數(shù) , 船的位置 ) 智能科學與技術系 狀態(tài)的轉換 算子（算符，操作符） ——使狀態(tài)發(fā)生改變的操作 MC問題中的算子 將傳教士或野人運到河對岸 Move1m1clr： 將一個傳教士 (m)一個野人 (c)從左岸 (l)運到右岸 (r) 所有可能操作 Move1m1clr Move1m1crl Move2clr Move2crl Move2mlr Move2mrl Move1clr Move1crl Move1mlr Move1mrl 智能科學與技術系 傳教士野人問題狀態(tài)空間圖 M C 智能科學與技術系 解的搜索 求解過程轉化為在狀態(tài)空間圖中 搜索 一條從初始節(jié)點到目標節(jié)點的路徑問題 圖的搜索 無信息搜索（盲目搜索） 有信息搜索（啟發(fā)式搜索） 寬度優(yōu)先搜索 深度優(yōu)先搜索 A算法 A*算法 圖的一般搜索策略 智能科學與技術系 圖的搜索過程 狀態(tài)： (城市名 ) 算子：常德 → 益陽 益陽 → 常德 益陽 ?汨羅 益陽 ?寧鄉(xiāng) 益陽 ?婁底 … 必須記住哪些點走過了 必須記住下一步還可以走哪些點 深度優(yōu)先搜索 必須記住從目標返回的路徑 智能科學與技術系 圖的搜索過程 必須記住哪些點走過了 必須記住下一步還可以走哪些點 必須記住從目標返回的路徑 OPEN表 (記錄還沒有擴展的點 ) CLOSED表 (記錄已經(jīng)擴展的點 ) 每個表示狀態(tài)的節(jié)點結構中必須有指向父節(jié)點的指針 智能科學與技術系 智能科學與技術系 智能科學與技術系 圖的一般搜索策略 開始 把 S放入 OPEN表 OPEN表為空表？ 把第一個節(jié)點 (n)從 OPEN表移至 CLOSED表 n為目標節(jié)點嗎？ 把 n的后繼節(jié)點放入 OPEN表，提供返回節(jié)點 n的指針 修改指針方向 重排 OPEN表 失敗 成功 是 是 否 否 智能科學與技術系 盲目搜索 不同的搜索策略其搜索的效率是不同的 盲目搜索又稱無信息搜索 寬度優(yōu)先搜索 深度優(yōu)先搜索 特點 搜索過程中不使用與問題有關的經(jīng)驗信息 不重排 OPEN表 搜索效率低 不適合大空間的實際問題求解 智能科學與技術系 是什么影響了搜索的效率？ 八數(shù)碼難題 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 （目標狀態(tài)） （初始狀態(tài) ） 操作 : 空格上移，空格下移，空格左移，空格右移 智能科學與技術系 1 2 3 8 4 5 6 7 1 2 3 8 4 1 2 3 8 4 5 6 7 4 1 2 3 8 5 6 7 1 2 3 8 4 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 6 7 8 9 10 11 12 13 1 2 3 8 4 5 6 7 5 6 7 5 6 7 1 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 2 3 4 5 寬度優(yōu)先搜索樹 1 2 3 8 4 5 6 7 27 1 3 4 5 6 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 23 24 25 26 2 7 8 22 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 14 15 16 17 18 19 20 21 1 2 3 8 4 5 6 7 智能科學與技術系 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 4 1 2 3 8 5 6 7 深度優(yōu)先搜索樹(深度約束 =4) 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 3 4 5 6 2 7 8 能否預先知道下一步應選擇誰？ 智能科學與技術系 啟發(fā)式搜索 有信息搜索 搜索過程中利用與問題有關的經(jīng)驗信息（ 啟發(fā)式信息 ） 引入估價函數(shù)來估計節(jié)點位于解路徑上的 “ 希望 ” ，函數(shù)值越小 “ 希望 ” 越大 搜索過程中按照估價函數(shù)的大小對 OPEN表排序 每次選擇估價函數(shù)值最小的節(jié)點作為下一步考察的節(jié)點 智能科學與技術系 估價函數(shù) 是啟發(fā)式搜索中最重要的因素 啟發(fā)式搜索和盲目搜索的不同就體現(xiàn)在對OPEN表按估價函數(shù)的大小排序 不同的估價函數(shù)所體現(xiàn)出來的搜索效率不同，甚至天差地遠 不同的估價函數(shù)也決定了不同的啟發(fā)式搜索算法 智能科學與技術系 A算法 1964年，尼爾遜提出一種算法以提高最短路徑搜索的效率，被稱為 A1算法 1967年，拉斐爾改進了 A1算法，稱為 A2算法 尼爾遜 拉斐爾 智能科學與技術系 A算法 特征： 估價函數(shù) f (x) = g
教學課件相關推薦
鄂ICP備17016276號-1