1、圖搜索與問題求解第一次作業1.什么是狀態空間圖、狀態（節點）、狀態轉換規則（邊）、狀態空間、隱式狀態圖2.狀態圖搜索問題求解需要哪些知識?求解過程的本質是什么？3.對以下3個問題，試分別設計該問題的狀態、狀態轉換規則、狀態空間，并描述求解過程（1）傳教士與野人問題：傳教士（M）與野人（C）數目均為五人，渡船（B）最多可乘3人。 （2）翻錢幣問題：三枚錢幣，能否從下面狀態翻動三次后出現全正或全反狀態反正反正正正反反反初始狀態s目標狀態集合0 , 7（3）已知桶、罐和瓶分別能存放水5000ml、3500ml、1500ml，現在桶中有5000ml水，如何只利用這三件容器把水分成兩份，每份2500ml

2、（4）N皇后問題就是在N*N的棋盤上放置N個皇后的方法解，滿足每行、每列和對角線上只允許出現一個皇后，如以下是8皇后問題的解。試解決4皇后問題 第二次1.什么是啟發性信息、完備的搜索、啟發函數、加權狀態圖？2.深度優先搜索和廣度優先搜索過程的OPEN表有何不同？3.深度優先搜索和廣度優先搜索的優缺點是什么？4.估價函數綜合了哪些信息？5.為“倒水”問題設計一個啟發函數第三次1.什么是與等價？什么是或等價？試分別用一個例子說明。2.什么是與或圖的本原問題？什么是端節點？什么是與節點、或節點？3.與或圖搜索的可見性判別條件是什么？4.設有如下圖的與/或/樹，請分別按和代價法及最大代價法求解樹的代價

3、。ABCDt2t3t4t1與/或樹56217223E 5. 設有如圖所示的博弈樹，其中最下面的數字是假設的估值，請對該博弈樹作如下工作：(1) 計算各節點的倒推值；(2) 利用-剪枝技術剪去不必要的分枝。博弈樹305-336-2354-3068-3369S0ABCDEFGHIJKLNM第四次1、請將下列語句翻譯成命題公式（1）如果交通不堵塞，老王將準時到達火車站（2）你去聽課，他也去聽課（3）如果明天不下雪，我就去登山（4）盡管他參加了考試，但他沒有通過考試2、請將下列語句翻譯成謂詞公式（1）有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花。 （2）他每天下午都去打籃球。 （3）西安

4、市的夏天既干燥又炎熱。 （4）并不是每一個人都喜歡吃臭豆腐。 （5）喜歡讀三國演義的人必讀水滸。 （6）欲窮千里目，更上一層樓。第5次1.將下列謂詞公式整理為子句集形式（1）$x$y(P(x,y) ÙQ(x,y)（2）"x "y(P(x,y) ®Q(x,y)（3）"x$y(P(x,y) ÚQ(x,y) ®R(x,y)（4）"x (P(x) ®$y (P(y) ÙR(x,y)（5）$x(P(x) Ù"x(P(y) ®R(x,y)（6）$x$y"z $u&qu

5、ot;v $w(p(x,y,z,u,v,w) Ù(Q(x,y,z,u,v,w) Ú¬R(x,z,w)第6次1.教材課后題2.寢室有甲、乙、丙三名同學，一天晚自習時，班主任老師巡查寢室發現該寢室有同學滯留寢室，沒有參加晚自習；班主任調查得知：如甲在寢室并乙不在寢室時，則丙一定在寢室；如乙在寢室，則丙一定在寢室。班主任得出結論：丙一定在寢室。請試用基于命題公式的歸結證明班主任的結論。3.判斷以下公式對是否可合一，若可合一，則求出最一般的合一：（1）（2）（3）第7次作業1. 試判斷下列子句集中哪些是不可滿足的。（1）S=P(y) Ú¬Q(y), &

6、#172;P(f(x) ÚQ(y)（2）S=¬ P(x) ÚQ(x), ¬ Q(y) ÚR(y),P(a),R(a) （3）S=¬ P(x) Ú¬Q(y) Ú¬L(x,y),P(a), ¬ R(z) ÚL(a,z) ,R(b),Q(b)（4）S=P(x) ÚQ(x) ÚR(x),¬ P(y) ÚR(y), ¬ Q(a), ¬R(b) （5）S=P(x) ÚQ(x),¬ Q(y) ÚR(y

7、), ¬ P(z) ÚQ(z), ¬R(u) 2對下列各題請分別證明，G是否可肯定是F1，F2，的邏輯結論（1）F："x(P(x) Ù Q(x) G：$x(P(x) Ù Q(x)（2）F1："x(P(x)®"y(Q(y)® ¬ L(x,y) F2：$x(P(x)Ù"y(R(y)® L(x,y) G："x(R(x)®¬ Q(x)（3）F1：("x)(P(x)®(Q(x)R(x)F2：($x) (P(x) S(x)G： ($x)(S(x) R(x)4設已知：(1)凡是清潔的東西就有人喜歡；(2)人們都不喜歡蒼蠅；用歸結原理證明：蒼蠅是不清潔的5張某被盜，公安局派出五個偵探去調查研究案情時