第五講經(jīng)典人工智能技術(shù)—知識表示、推理與搜索77-全文預覽
【正文】 (x) + h (x) 從起始狀態(tài)到當前狀態(tài) x的代價 從當前狀態(tài) x到目標狀態(tài)的估計代價（啟發(fā)函數(shù)） 雖提高了算法效率，但不能保證找到最優(yōu)解 智能科學與技術(shù)系 A*算法 1968年，彼得 .哈特對 A算法進行了很小的修改，并證明了當估價函數(shù)滿足一定的限制條件時，算法一定可以找到最優(yōu)解 估價函數(shù)滿足一定限制條件的算法稱為 A*算法 f (x) = g (x) + h (x) A*算法的限制條件 大于 0 不大于 x到目標的實際代價 彼得 .哈特 智能科學與技術(shù)系 利用 A*算法求解八數(shù)碼問題 估價函數(shù)的定義 f (x) = g (x) + h (x) g (x)：從初始狀態(tài)到 x需要進行的移動操作的次數(shù) h (x)：？ 誰更接近目標狀態(tài)？ 錯放的棋子越少越好！ =x狀態(tài)下錯放的棋子數(shù) 滿足限制條件 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 8 1 3 2 4 5 6 7 h(x)=1 h(x)=2 h(x)=4 智能科學與技術(shù)系 4 5 6 3 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 1+5 1+5 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+4 2+3 2+3 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 3+2 3+4 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 3+3 3+4 1 2 3 8 4 5 6 7 4+1 8 1 3 2 4 5 6 7 1 2 3 8 4 5 6 7 5+0 5+2 5 7 1 1 2 3 8 4 6 0+4 5 2 OPEN表 CLOSED表 智能科學與技術(shù)系 估價函數(shù)對算法的影響 不同的估價函數(shù)對算法的效率可能產(chǎn)生極大的影響 不同的估價函數(shù)甚至產(chǎn)生不同的算法 f (x) = g (x) + h (x) h (x)=0： Dijkstra算法，非啟發(fā)式算法 g (x)=0：貪婪搜索，無法保證找到解 即使采用同樣的形式 f (x) = g (x) + h (x) ，不同的定義和不同的值也會影響搜索過程 智能科學與技術(shù)系 估價函數(shù)對算法的影響示例 例：八數(shù)碼問題 f (x) = g (x) + h (x) g (x)：從初始狀態(tài)到 x需要進行的移動操作的次數(shù) h (x)：所有棋子與目標位置的曼哈頓距離之和 曼哈頓距離：兩點之間水平距離和垂直距離之和 仍滿足估價函數(shù)的限制條件 1 2 3 8 4 5 6 7 h(x)= 2 +1 +1 +2=6 智能科學與技術(shù)系 3 4 5 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+4 1+6 1+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 2+5 2+5 2+3 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 3+2 3+4 1 2 3 8 4 5 6 7 4+1 8 1 3 2 4 5 6 7 1 2 3 8 4 5 6 7 5+0 5+2 0+5 5 7 1 1 2 3 8 4 6 5 2 智能科學與技術(shù)系 例：路徑規(guī)劃 S G 45 6 4 4 5 5 6 6 A*算法被廣泛應用于靜態(tài)路網(wǎng)中的最短路徑規(guī)劃 用距離表示代價 每一步可以往相鄰的 8個無障礙格子移動，移動距離為 1 g (x)：從出發(fā)點 S到當前點 x的距離 h (x)：從當前點 x到目標點 G的距離 5 6 6 7 5 6 7 7 7 7 7 5 5 5 6 7 7 6 6 6 7 智能科學與技術(shù)系 謝謝大家！ 智能科學與技術(shù)系 靜夜四無鄰，荒居舊業(yè)貧。例如： 如果一個人發(fā)燒、肚子痛，那么很可能是感染了。李明能看書且不貧窮，快樂的人過著激動人心的生活。 C2=~P∨ C239。我們稱表達式集 {Ei}是可合一的（ unifiable） ,s為合一者（ unifier） mgu(most general unifier, 最一般合一者 ) 若 s為 {Fi}的任一合一者，又存在某個置換 s39。 2023年 5月 4日，國際小行星中心發(fā)布公報通知國際社會，將國際永久編號為第 7683號的小行星永久命名為 “ 吳文俊星 ” 。 智能科學與技術(shù)系 自動證明的發(fā)展 1977年，美國年輕的數(shù)學家阿佩爾等在高速電子計算機上耗費 1200 小時的計算時間，證明了著名的 “四色定理 ” ，人類百年懸而未決的疑問最終被圓滿解決了。 1972年回國時曾受周恩來總理的接見。 智能科學與技術(shù)系 自動證明的發(fā)展 —王浩 美籍華裔王浩 1983 年，獲國際人工智能聯(lián)合會 “ 數(shù)學定理機械證明里程碑獎 ” ，表彰他在數(shù)學定理機械證明研究領域的開創(chuàng)性貢獻。 簡歷 生于山東濟南市 1943年畢業(yè)于西南聯(lián)合大學數(shù)學系 1945年畢業(yè)于清華大學研究生院哲學系 1948年獲哈佛大學哲學博士學位 19541956年在牛津大學任高級教職 19611967年任哈佛大學教授 19671991年任洛克菲勒大學邏輯學教授 20世紀 50年代初當選美國科學院院士及不列顛科學院外籍院士。已知信息： 1. 英國人在紅房間中 2. 西班牙人有一條狗 3. 挪威人住在左邊第一間房里 4. 黃房間中的人在抽庫爾斯牌香煙 5. 抽切斯菲爾德牌香煙的人是養(yǎng)了一只狐貍的人的鄰居 6. 挪威人住在藍房間隔壁 7. 抽溫斯頓牌香煙的人有一只蝸牛 8. 抽幸運牌香煙的人喝橘子汁 9. 烏克蘭人喝茶 10. 日本人抽國會牌香煙 11. 抽庫爾斯牌煙的房間在有匹馬的房間隔壁 12. 綠房間中的人喝咖啡 13. 綠房間在白房間的左邊 14. 中間房間的人喝牛奶 問題：斑馬在哪個房間中？哪個房間中的人喝水？ 智能科學與技術(shù)系 自動推理示例 ： 5個房間問題 房間號 1 2 3 4 5 顏色 國籍 香煙 飲料 寵物 挪威人 牛奶 咖啡 庫爾斯 馬 英國人 水 橘子汁 西班牙 幸運 狗 茶 烏克蘭 日本人 國會 溫斯頓 切斯菲爾德 蝸牛 狐貍 斑馬 牌香煙 匹馬的房間隔壁 只蝸牛 機器真的能自動完成這樣的推理嗎？ 智能科學與技術(shù)系 自動推理示例 求 解 智能科學與技術(shù)系 自動推理證明的發(fā)展史 笛卡爾 萊布尼茨 自動證明的提出 笛卡爾、萊布尼茨（ 17世紀） 萌發(fā)了用機械系統(tǒng)實現(xiàn)定理證明的想法 把一類數(shù)學問題當作一個整體，建立統(tǒng)一的證明過程，按照規(guī)定的程序步驟機械地進行下去，在有限步驟之后判斷出定理的正確性 智能科學與技術(shù)系 自動證明的發(fā)展 由于傳統(tǒng)的興趣和應用
教學課件相關(guān)推薦
鄂ICP備17016276號-1