2020-10-20

2020-10-21 12:00:01

人工智慧2020秋季

雜談

機器學習比較難,所以我跑到人工智慧這裡來避避風頭

第一關:知識的表示

1. 一階謂詞邏輯

雜談:謂詞邏輯,關鍵是謂詞,其實我覺得就是漢語轉化為「英語」

  • 先上菜鳥題:
  1. 老王喜歡妹子
  2. 並不是所有的男人都喜歡妹子
  3. 有些男人不是老王
  • 再上經典的猴子吃香蕉的題:

設房間裡有一隻猴子,位於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.產生式系統

雜談

步驟就是:列出綜合資料庫->列出初始狀態和目標狀態->窮舉出可能發生的情況(這一步最難)->範例化找到解

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

  1. 上面的猴子吃香蕉問題

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

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

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

  1. 傳教士與野人問題

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

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

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

  1. 倒水的問題

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

3.語意網路

雜談:類似java的UML類圖建模,這裡主要是把握住「物件」,然後建立以此為突破點,將其他事物的關係都扯上去

  1. 事物和概念:

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

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

  1. 事物和概念:

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

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

  1. 情況表示

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

  1. 事件和動作節點

​ 常河給江濤一個優盤

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片儲存下來直接上傳(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)]
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片儲存下來直接上傳(img-haHEZQn5-1603177546125)(知識點.assets/image-20201020144943322.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)]

題四:啟發式搜尋

雜談:啟發式搜尋關鍵是找出一個啟發函數。

設有如下結構的移動將牌遊戲:

BBWWE

其中,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)]