人工智能2020秋季

雜談：

機器學習比較難，所以我跑到人工智能這里來避避風頭

第一關：知識的表示

1. 一階謂詞邏輯

雜談：謂詞邏輯，關鍵是謂詞，其實我覺得就是漢語轉化為“英語”

先上菜鳥題：

老王喜歡妹子
并不是所有的男人都喜歡妹子
有些男人不是老王

再上經典的猴子吃香蕉的題：

設房間里有一只猴子，位于a

在c處有一串香蕉，（猴子想吃，但摘不到）

房間b處有一個箱子（如果猴子站到箱子上，就可以摘到香蕉）

? 決議：要解決這個問題，需要一定的套路，首先，找到有哪些東西（猴子，香蕉，箱子）；其次，定義謂詞

? 靜態屬性：

? 位置關系：AT（x,y） ,其中x的個體域為{monkey,banana,box},y的個體域為{a,b,c}

? （如果以后涉及到位移的問題，首先應該想到的就是位置關系）

? ONBOX：表示猴子在箱子上面

? HB：猴子摘到香蕉

? 從上面就可以找到問題的初始狀態和目標狀態：

? AT（monkey,a） AT（monkey,c）

? AT(box,b) AT(box,c)

? AT(banana,c) AT(banana,c)

? ~ONBOX ONBOX

? ~HB HB

? 動態屬性：動作

? GOTO(x,y):表示猴子從x處走到y處

? PUSHBOX(x,y):表示猴子推著箱子從x處移動到y處

? CLIMBBOX:表示猴子爬上箱子

? GRASP：表示猴子摘到香蕉

這些條件對應的先決條件和動作：

? …(這個東西比較長，一階謂詞用來表示一個狀態程序，我懷疑一面紙才能寫下，考試應該不會出這種型別的大題，大家熟悉一下他的流程就好，個人覺得像這種給出一個解決方案的題目是不會限制你使用那種知識表示的方法的，下面還會講一些其他的知識表示和推理的方法)

2.產生式系統

雜談：

步驟就是：列出綜合資料庫->列出初始狀態和目標狀態->窮舉出可能發生的情況（這一步最難）->實體化找到解

要是第三步暫時想不到，可以先把第四步的解得到，然后再抽象出第三步

上面的猴子吃香蕉問題

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-WXYiDQoL-1603177546085)(知識點.assets/image-20201020144530278.png)]

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-YnogmaGt-1603177546095)(知識點.assets/image-20201020144552810.png)]

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-HsYPKFK3-1603177546100)(知識點.assets/image-20201020144609608.png)]

傳教士與野人問題

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-940iRSV1-1603177546104)(知識點.assets/image-20201020144635009.png)]

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-DcSIEphr-1603177546107)(知識點.assets/image-20201020144650910.png)]

? [外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-0H9mepZ1-1603177546109)(知識點.assets/image-20201020144716064.png)]

倒水的問題

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-kjKjBcZr-1603177546112)(知識點.assets/image-20201020144728748.png)]

3.語意網路

雜談：類似java的UML類圖建模，這里主要是把握住“物件”，然后建立以此為突破點，將其他事物的關系都扯上去

事物和概念：

動物能運動、會吃，
鳥是一種動物，鳥有翅膀、會飛，
魚是一種動物，魚生活在水中、會游泳，

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-6GNwE6lR-1603177546114)(知識點.assets/image-20201020144754387.png)]

事物和概念：

王強是理想公司的經理;
理想公司在中關村;
王強28歲，

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-TPUiHSuO-1603177546116)(知識點.assets/image-20201020144801743.png)]

情況表示

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-Z72vGB7y-1603177546117)(知識點.assets/image-20201020144810456.png)]

事件和動作節點

? 常河給江濤一個優盤

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-TvaHJiWe-1603177546119)(知識點.assets/image-20201020144821802.png)]

4.框架

雜談：就是填寫個人資訊表（不僅是填實體，還要抽象出實體的型別），英語水平差就很難受了

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-9kPde4iQ-1603177546120)(知識點.assets/image-20201020144837195.png)]

第二關：確定性知識推理

雜談：這一章雖然寫的多，但是難點就兩個：解釋，置換，其實指派就是自己根據個體域賦值，置換記住常/變可替換變就行，

題一（解釋）

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-sp2oyo1j-1603177546121)(知識點.assets/image-20201020144900445.png)]

簡單理解，我給你一個解釋：要是某某為1（1是個體域的值），xxx，然后謂詞的值將會是xxx,最后這個公式的值就是T/F，

題二（魯濱遜歸結原理的證明題）

雜談：復習一下步驟，假設已知F1，F2要推出G，

把{F1,F2,~G}放在一起做成一個子句集，如果能歸結出空，則證明，

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-WLfgkhBL-1603177546123)(知識點.assets/image-20201020144909284.png)]

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-ie9JsLFI-1603177546124)(知識點.assets/image-20201020144920744.png)]

題三（歸結反演用來求取問題的答案）

雜談：愛或者不愛，只能選擇一個，

假設張被盜，公安局派出5個人去調查，案情分析時，偵察員A說：“趙與錢至少有一個人作案”；

B說：“錢和孫至少有一個人作案”；

C說：“孫和李至少有一個人作案”

D說：“趙和孫至少有一個人與此案無關”

E說：“錢和李至少有一個人與此案無關”

? 如果這5個人的話都可信，試用歸結演繹推理求出誰是盜竊犯，

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-9JAED2hZ-1603177546126)(知識點.assets/image-20201020144958240.png)]

在這里插入圖片描述

第三關：搜索策略(這一關是最難的)

雜談：搜索策略解決問題的方法有兩種：狀態空間法（畫圈圈）和問題規約法（與/或樹），

題一（狀態空間）

雜談：其實這類問題和上面說的產生式系統很像的，大家可以仔細對比一下

農夫問題

有一農夫帶一條狼，一只羊和一筐菜欲從河的左岸乘船到河的右岸，但受下列條件的限制：

（1）船太小，農夫每次只能帶一樣東西過河；

（2）如果沒有農夫看管，則狼要吃羊，羊要吃菜；

請設計一個過河方案，使得農夫，狼，羊，菜都能不受損失地過河，畫出相應的狀態空間圖，

提示：

（1）用四元組（農夫，狼，羊，菜）表示狀態，其中每個元素都為0或1，用0表示在作案，1表示在右岸，

（2）把每次過河的一種安排作為一種操作，每次過河都必須有農夫，因為只有他可以劃船，

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-8OZISyX8-1603177546128)(知識點.assets/image-20201020145022568.png)]

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-qbPQ1aac-1603177546130)(知識點.assets/image-20201020145032786.png)]

題二（盲目的深搜和廣搜）

雜談：圖搜索演算法比較難，下面討論的主要是樹搜索演算法，結點的擴展順序是最重要的，以往大家都是在一個的具體圖上討論深搜和廣搜，這里擴展結點十分形象，下面的一個題是需要自己抽象的，

圓盤問題：

設有大小不等的三個圓盤A,B,C，套在一根軸上，每個盤上都標有數字1，2，3，4，并且每個圓盤上都可以獨立地繞軸逆時針轉動，每次轉動90°，其初始狀態S0和目標狀態Sg如下圖所示，請用廣度優先搜索和深度優先搜索，求出從S0到Sg的路徑，

在這里插入圖片描述

題三：代價樹的廣度優先搜索

雜談：在生成的結點中按照代價從小到大排序，每次找到代價最小的結點進行擴展，

下面是一個比較經典的演算法題——旅行商問題，由于篇幅比較長，有些分支就沒有畫出來了，

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-sfeB7D18-1603177546133)(知識點.assets/image-20201020145249417.png)]

題四：啟發式搜索

雜談：啟發式搜索關鍵是找出一個啟發函式，

設有如下結構的移動將牌游戲：


B	B	W	W	E

其中，B表示黑色將牌，W表示白色將牌，E表示空格，游戲規則走法：

（1）任意一個將牌可移入相鄰的空格，規定其代價為1；

（2）任何一個將牌可相隔一個其他的將牌跳入空格，其代價為跳過將牌的數目加1，

游戲要達到的目標是把所有的W都移到B的左邊，對這個問題，請定義一個啟發函式h(n),并給出這個啟發函式產生的搜索樹，判別這個啟發函式是否滿足下界要求？在求出的搜索樹中，對所有節點是否滿足單調限制，

補充一個小知識點：

不可納的，一定不滿足單調限制，

在這里插入圖片描述

題五：與或樹（計算解樹的代價）

雜談：要想找到最優解樹，必須要計算解樹的代價，本題就是一個計算解樹代價的題，熟悉一下套路即可，

在這里插入圖片描述

題六：博弈樹，α-β剪枝

第四關：貝葉斯網路

雜談：貝葉斯網路這一塊兒，主要是掌握兩個規則，鏈式法則和條件依賴，

題一：獨立性判斷

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-62OzFPn6-1603177546139)(知識點.assets/image-20201020145225768.png)]

條件獨立詳細說明

題二基于貝葉斯網路的概率計算

雜談:這里主要指的是列舉法的精確計算，也沒有MCMC演算法，比較容易理解，大家掌握一下基本套路就行，

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-NoYKLuKW-1603177546140)(知識點.assets/image-20201020145306772.png)]

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/185662.html

標籤：其他

上一篇：有什么建站軟體可以快速建網站？

下一篇：記2020年(第16屆)湖南ACM省賽

人工智能2020秋季總結

人工智能2020秋季

第一關：知識的表示

1. 一階謂詞邏輯

2.產生式系統

3.語意網路

4.框架

第二關：確定性知識推理

題一（解釋）

題二（魯濱遜歸結原理的證明題）

題三（歸結反演用來求取問題的答案）

第三關：搜索策略(這一關是最難的)

題一（狀態空間）

題二（盲目的深搜和廣搜）

題三：代價樹的廣度優先搜索

題四：啟發式搜索

題五：與或樹（計算解樹的代價）

題六：博弈樹，α-β剪枝

第四關：貝葉斯網路

題一：獨立性判斷

題二基于貝葉斯網路的概率計算