哈工大人工智能復(fù)習(xí)題.pdf

1 第一章 人工智能概述 1 請舉例說明人工智能這門科學(xué)研究的內(nèi)容 特點 難點 研究目標 答 研究的內(nèi)容 啟發(fā)式搜索理論 搜索的方法很多 如回溯 圖搜索 啟發(fā)式等等 主要是給定一些經(jīng)驗做指導(dǎo)提高搜索 效率 該方面的研究已經(jīng)有了比較成熟的技術(shù) 各種推理方法 常識推理有知識不完全 不夠用等問題 如鳥會飛 但是鴕鳥不會飛 知識的模型化和表示方法 知識表示很重要 方法主要有邏輯 產(chǎn)生式 語義網(wǎng)絡(luò) 框架等 現(xiàn)在還不能完全說清 楚知識表示到底是什么 人工智能系統(tǒng)結(jié)構(gòu)及語言 Lisp 語言主要在美國 Prolog 語言主要在歐洲使用比較廣泛 機器學(xué)習(xí) 當前系統(tǒng)大多用歸納的學(xué)習(xí) 依賴知識庫的學(xué)習(xí) 沒有很成熟的方法 神經(jīng)網(wǎng)絡(luò) 遺傳 算法等理論的應(yīng)用也在探討之中 特點 人工智能是一門知識的科學(xué) 以知識為對象 研究知識的獲取 表示和使用 人工智能的系統(tǒng)過程是 數(shù)據(jù)處理 知識處理 數(shù)據(jù) 符號 符號表示的是知識而不 是數(shù)值 數(shù)據(jù) 問題求解過程有啟發(fā) 有推導(dǎo) 人工智能是引起爭論最多的科學(xué)之一 難點 知識獲取 知識表示 機器學(xué)習(xí) 實現(xiàn)時的規(guī)模擴大問題 應(yīng)用前景 封閉的專家系統(tǒng) 機器學(xué)習(xí)問題 研究目標 遠期目標 揭示人類智能的根本機理 用智能機器去模擬 延伸和擴展人類智能 近期目標 建造智能計算機代替人類的部分智力勞動 2 請舉例說明人工智能有哪些研究及應(yīng)用領(lǐng)域 參考教材 P12 18 3 人工智能研究有哪此不同學(xué)派 它們的基本思想是什么 你認同哪一種觀點 為什么 參考教材 P18 20 第二章 知識表示 1 設(shè)有如下語句 請用相應(yīng)的謂詞公式分別把他們表示出來 a 有的人喜歡梅花 有的人喜歡菊花 有的人既喜歡梅花又喜歡菊花 b 有的人每天下午都去打籃球 c 新型計算機速度又快 存儲容量又大 d 不是每個計算機系的學(xué)生都喜歡在計算機上編程序 e 凡是喜歡編程序的人都喜歡計算機 答 a 定義謂詞 LIKE x y 表示 x 喜歡 y PERSON x x PERSON x LIKE x 梅花 y PERSON y LIKE y 菊花 x PERSON x LIKE x 梅花 LIKE y 菊花 2 b PLAY x y 表示 x 打 y AFTERNOON t 表示 t 是下午 x t AFTERNOON t PLAY x 籃球 c Computer x x 是計算機 NewType x x 是新型的 HaveSpeed x y x 的速度是 y High y y 是高的 HaveMemory x z x 的存儲容量是 z Large z z 是大的 Computer x NewType x High y HaveSpeed x y Large z HaveMemory x z d Computer x x 是計算機系的 Student x x 是學(xué)生 Like x y x Computer x Student x Like x programming e x Person x Like x programming Like x computer 2 請畫圖說明產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu)及其各組成部分 請參考教材 P38 3 設(shè)有如下問題 八數(shù)碼難題 a 在一個 3 3 的方框內(nèi)放有 8 個編號的小方塊 b 緊鄰空位的小方塊可以移入到空位上 c 通過平移小方塊可將某一布局變換為另一布局 請用產(chǎn)生式規(guī)則表示移動小方塊的操作 解 空格向上移 IF 空格上方有數(shù)字 THEN 空格向上移 4 請把下列命題用一個語義網(wǎng)絡(luò)表示出來 1 樹和草都是植物 2 樹和草都有葉和根 3 水草是草 且生長在水中 4 果樹是樹 且會結(jié)果 5 梨樹是果樹中的一種 它會結(jié)梨 5 請對下列命題分別寫出它們的語義網(wǎng)絡(luò) a 每個學(xué)生都有一臺計算機 b 高老師從 3 月到 7 月給計算機系學(xué)生講 計算機網(wǎng)絡(luò) 課 c 學(xué)習(xí)班的學(xué)員有男 有女 有研究生 有本科生 d 創(chuàng)新公司在科海大街 56 號 劉洋是該公司的經(jīng)理 他 32 歲 碩士學(xué)位 e 紅隊與藍隊進行足球比賽 最后以 3 2 的比分結(jié)束 第三章 確定性推理 1 下列子句是否可以合一 如果可以 寫出最一般合一 3 a P x B B 和 P A y z b P g f v g u 和 P x x c P x f x 和 P y y d P y y B 和 P z x z 解 1 P x B B 和 P A y z 可以合一 Mgu A x B y B z 2 P g f v g u 和 P x x 不可以合一 3 P x f x 和 P y y 不可以合一 4 P y y B 和 P z x z 可以合一 Mgu B x B y B z 2 將下面的公式化成子句集 P Q R P R 解 P Q R P R P Q R P R P Q R P R P R Q R P R 建立子句集 S P R Q R P R 3 Herbrand 定理解決了一個什么意義上的問題 答 將無限的不可數(shù)的論域上的問題 轉(zhuǎn)化成為在可數(shù)的 H 論域上討論的問題 該定理在理論上保證 了歸結(jié)原理的可靠性 4 設(shè) S P x Q f x y 試寫出 H 域上的元素 并寫出 S 的一個基例 解 H a f a f f a S 中子句的一個基例為 P a Q f a f a 或者 P f a Q f f a a 5 設(shè)已知 a 如果 x 是 y 的父親 y 是 z 的父親 則 x 是 z 的祖父 b 每個人都有一個父親 試用歸結(jié)演繹推理證明 對于某個 u 一定存在一個人 v v 是 u 的祖父 解 定義謂詞 father x y 表示 x 是 y 的父親 Grandfather x y 表示 x 是 y 的祖父 已知條件的謂詞公式表示如下 1 1 x y z father x y father y z Grandfather x z 2 y x father x y 結(jié)論的謂詞公式表示 u v Grandfather v u 將結(jié)論取反并入條件形成公式集 F x y z father x y father y z Grandfather x z y x father x y u v Grandfather v u 將公式集 F 化為子句集 S father x y father y z Grandfather x z father f w w 4 Grandfather f u u 對子句集 S 進行歸結(jié) 對于子句 father x y father y z Grandfather x z 可以先在內(nèi)部進行合一 6 用歸結(jié)法證明 存在一個綠色物體 如果有如下條件存在 a 如果可以推動的物體是藍色的 那么不可以推動的物體是綠色的 b 所有的物體或者是藍色的 或者是綠色的 但不能同時具有兩種顏色 c 如果存在一個不能推動的物體 那么所有的可推動的物體是藍色的 d 物體 O1 是可以推動的 e 物體 O2 是不可以推動的 解 把上述條件化為邏輯表達式 1 x pushable x blue x x pushable x green x 2 x blue x green x blue x green x 3 x pushable x x pushable x blue x 4 pushable O1 5 pushable O2 將結(jié)果命題否定 x green x 將條件表達式和結(jié)果命題化為子句形 由條件 1 1 pushable x green x 2 blue a pushable y green x 由條件 2 3 green x blue x 4 green x blue x 由條件 3 5 pushable x pushable y blue y 由條件 4 6 pushable O1 由條件 5 7 pushable O2 由結(jié)論 8 green x 歸結(jié) 9 blue x pushable y 2 8 10 blue x 7 9 11 blue x 4 8 12 10 11 7 已知事實公式為 x y z Gt x y Gt y z Gt x z u v Succ u v Gt u v x Gt x x 求證 Gt 5 2 試判斷下面的歸結(jié)過程是否正確 若有錯誤應(yīng)如何改進 5 8 我們來考慮下列一段知識 a Tony Mike 和 John 屬于 Alpine 俱樂部 b Alpine 俱樂部的每個成員不是滑雪運動員就是一個登山運動員 c 登山運動員不喜歡雨而且任一不喜歡雪的人不是滑雪運動員 d Mike 討厭 Tony 所喜歡的一切東西 而喜歡 Tony 所討厭的一切東西 e Tony 喜歡雨和雪 以謂詞演算語句的集合表示這段知識 使得這些語句適合一個逆向的基 于規(guī)則的演繹系統(tǒng) 若想利用基于規(guī)則的逆向推理回答問題 有沒有 Alpine 俱樂部的一個成員 他是一個登山運動員但不是一個滑雪運動員呢 問 題應(yīng)該如何表示呢 答 我們用 Skier x 表示 x 是滑雪運動員 Alpinist x 表示 x 是登山運動員 Alpine x 表示 x 是 Alpine 俱樂部的成員 問題用謂詞公式表示如下 已知 1 Alpine Tony 2 Alpine Mike 3 Alpine John 4 x Alpine x Skier x Alpinist x 5 x Alpinist x Like x Rain 6 x Like x Snow Skier x 7 x Like Tony x Like Mike x 8 x Like Tony x Like Mike x 9 Like Tony Snow 10 Like Tony Rain 目標 x Alpine x Alpinist x Skier x 6 9 一個積木世界的狀態(tài)由下列公式集描述 ONTABLE A CLEAR E ONTABLE C CLEAR D ON D C HEAVY D ON B A WOODEN B HEAVY B ON E B 下列語句提供了有關(guān)這個積木世界的一般知識 每個大的藍色積木塊是在一個綠色積木塊上 每個重的木制積木塊是大的 所有頂上沒有東西的積木塊都是藍色的 所有木制積木塊是藍色的 以具有單文字后項的蘊涵式的集合表示這些語句 繪出能求解 哪個積木塊是 在綠積木塊上 這個問題的一致解圖 用 B 規(guī)則 解 知識的謂詞表示 x y BIG x BLUE x ON x y GREEN y x HEAVY x WOODEN x BIG x x CLEAR x BLUE x x WOODEN x BLUE x 目標 x y GREEN y ON x y 對規(guī)則 Skolem 化 對目標用對偶形式 Skolem 化后 整理得 事實 ONTABLE A CLEAR E ONTABLE C CLEAR D ON D C HEAVY D ON B A WOODEN B HEAVY B ON E B 規(guī)則 r1 BIG x1 BLUE x1 ON x1 f x1 r2 BIG x2 BLUE x2 GREEN f x2 r3 HEAVY x3 WOODEN x3 BIG x3 r4 CLEAR x4 BLUE x4 r5 WOODEN x5 BLUE x5 目標 GREEN y ON x y 7 容易驗證 只有一個解圖是一致的 其合一復(fù)合為 B x f B y 帶入目標公式 得到解答 GREEN f B ON B f B 其含義是 積木 B 在綠色積木上邊 這里的 f B 可以理解為 B 下面那個積木 10 某問題由下列公式描述 1 s P s 2 s P g s 3 x s y P s Q b x s H y 4 x s Q b x s Q b x g s 5 x s y P s Q b x y 求證 x H x 請用基于規(guī)則的逆向演繹系統(tǒng)求解 x H x 成立 要求給出一 個求得的一致解圖 并說明為什么它是一致的 給出目標的解答 答 對事實和規(guī)則進行 skolem 化 1 s P a 2 s P g s P g s 3 x s y P s Q b x s H y P s Q b c s H f s 4 x s Q b x s Q b x g s Q b x s Q b x g s 5 x s y P s Q b x y 8 P s Q b x h x s 經(jīng)變量換名后 有事實和規(guī)則如下 P a P g s1 r1 P s2 Q b c s2 H f s2 r2 Q b x3 s3 Q b x3 g s3 r3 P s4 Q b x4 h x4 s4 用對偶形式對目標 skolem 化 x H x H x 演繹圖如下圖 這里只給出了一個一致解圖 由置換集構(gòu)造 U1 和 U2 U1 x s2 x3 s2 x4 s3 s4 U2 f s2 g s1 c g s3 c h x4 s4 a 由于 U1 和 U2 是可合一的 因此該解圖是一致解圖 合一復(fù)合為 f g h c a x g h c a s2 c x3 h c a s3 c x4 h c a s1 a s4 將該合一復(fù)合帶入目標中 得到解答 x f g h c a 9 第四章 不確定性推理 1 什么是不確定性推理 為什么要采用不確定性推理 P122 2 不確定性推理中要解決哪些基本問題 P123 P124 3 已知 規(guī)則 R1 E1 H CF H E1 0 9 R2 E2 H CF H E2 0 6 R3 E3 H CF H E3 0 5 R4 E4 E5 E6 E1 CF E1 E4 E5 E6 0 9 初始數(shù)據(jù) CF E2 0 8 CF E3 0 6 CF E4 0 5 CF E5 0 6 CF E6 0 8 CF H 0 求 CF H 解 CF E1 0 8 max 0 CF E4 AND E5 OR E6 0 8 max 0 min CF E4 CF E5 OR E6 0 8 max 0 min 0 5 max CF E5 CF E6 0 8 max 0 min 0 5 0 8 0 8 max 0 0 5 0 8 0 5 0 4 CF1 H CF H E1 max 0 CF E1 0 9 0 4 0 36 CF2 H CF H E2 max 0 CF E2 0 6 0 8 0 48 CF3 H CF H E3 max 0 CF E3 0 5 0 6 0 3 CF12 H CF1 H CF2 H CF1 H CF2 H 0 36 0 48 0 36 0 48 0 67 CF123 H CF12 H CF3 H 1 min CF12 H CF3 H 0 67 0 3 1 0 3 0 53 4 當證據(jù) E1 E2 E3 E4 必然發(fā)生后 看 H 的概率變化 已知 H 的先驗概率為 0 03 而規(guī)則 R1 E1 H LS 20 LN 1 R2 E2 H LS 300 LN 1 R3 E3 H LS 75 LN 1 R4 E4 H LS 4 LN 1 解 1 由 P H 0 03 得 O H P H 1 P H 0 03 1 0 03 0 030927 2 根據(jù) R1 得 O H E1 LS O H 20 0 030927 0 61854 P H E1 O H 1 O H 0 382 3 根據(jù) R2 得 3 根據(jù) R2 得 O H E1 E2 O H E1 O H O H E2 O H O H LS O H E1 300 0 61854 185 562 P H E1 E2 O H E1 E2 1 O H E1 E2 0 99464 4 根據(jù) R3 得 10 O H E1 E2 E3 LS O H E1 E2 13917 15 P H E1 E2 E3 0 99993 5 根據(jù) R3 得 O H E1 E2 E3 E4 LS O H E1 E2 E3 55668 6 P H E1 E2 E3 E4 0 99998 5 例 3 當證據(jù) E 必然發(fā)生 已知 H1 的先驗概率為 0 03 而規(guī)則 R1 E H1 LS 20 LN 1 R2 H1 H2 LS 300 LN 0 0001 又知 P H2 的先驗概率為 0 01 時 計算 P H2 E 解 1 根據(jù) R1 及已知 P H1 0 03 得 P H1 E LS P H1 LS 1 P H1 1 20 0 03 20 1 0 03 1 0 382 2 由于 H1 是不確定的 所以要用插值法 因為 P H1 E P H1 當 P H1 E P H1 時 有 P H2 E P H2 0 01 當 P H1 E 1 時 有 P H2 E P H2 H1 LS P H2 LS 1 P H2 1 0 75188 3 P H2 E 0 01 0 75188 0 01 1 0 03 0 382 0 03 0 2792 第五章 搜索策略 1 對量水問題給出問題描述即狀態(tài)和操作定義 并畫出狀態(tài)空間圖 有兩個無刻度標志的水壺 分別可裝 5 升和 2 升的水 設(shè)另有一水缸 可用來向水壺灌 水或倒出水 兩個水壺之間 水也可以相互傾灌 已知 5 升壺為滿壺 2 升壺為空壺 問如何通過倒水或灌水操作 使能在 2 升的壺中量出一升的水來 解 a 定義兩元組 L5 L2 其中 0 L5 5 表示容量為 5 升的壺的當前水量 0 L2 2 表示容量為 2 升的壺的當前水量 b 操作規(guī)則集 r1 IF L5 L2 THEN 5 L2 將 L5 灌滿水 r2 IF L5 L2 THEN L5 2 將 L2 灌滿水 r3 IF L5 L2 THEN 0 L2 將 L5 水到光 r4 IF L5 L2 THEN L5 0 將 L2 水到光 r5 IF L5 L2 and L5 L25 THEN 5 L5 L2 5 L2 到入 L5 中 r7 IF L5 L2 and L5 L25 THEN L5 L2 2 2 L5 到入 L2 中 c 初始狀態(tài) 5 0 d 結(jié)束條件 x 1 其中 x 表示不定 當然結(jié)束條件也可以寫成 0 1 2 對三枚錢幣問題給出產(chǎn)生式系統(tǒng)描述及狀態(tài)空間圖 設(shè)有三枚錢幣 其排列處在 正 正 反 狀態(tài) 現(xiàn)允許每次可翻動其中任意 11 一個錢幣 問只許操作三次的情況下 如何翻動錢幣使其變成 正 正 正 或 反 反 反 狀態(tài) 答 1 定義四元組 x y z n 其中 x y x 0 1 1 表示錢幣為正面 0 表示錢幣為方面 n 0 1 2 3 表示當前狀態(tài)是 經(jīng)過 n 次翻錢幣得到的 2 規(guī)則庫 r1 IF x y z n THEN x y z n 1 r2 IF x y z n THEN x y z n 1 r3 IF x y z n THEN x y z n 1 其中 x 表示對 x 取反 3 初始狀態(tài) 1 1 0 0 4 結(jié)束狀態(tài) 1 1 1 3 或者 0 0 0 3 3 有一農(nóng)夫帶一條狼 一只羊和一筐菜欲從河的左岸乘船到右岸 但受下列條 件限制 a 船太小 農(nóng)夫每次只能帶一樣?xùn)|西過河 b 如果沒有農(nóng)夫看管 則狼要吃羊 羊要吃菜 請設(shè)計一個過河方案 使得農(nóng)夫 狼 羊和菜都能不受損失的過河 畫出相 應(yīng)的狀態(tài)空間圖 4 圖 1 2 是 5 個城市的交通圖 城市之間的連線旁邊的數(shù)字是城市之間路程的 費用 要求從 A 城出發(fā) 經(jīng)過其他各城一次且僅一次 最后回到 A 城 請給 出搜索樹 找出一條最優(yōu)線路 P200 圖 5 33 5 請找出圖 1 3 的與或樹所包含的解樹 P200 圖 5 34 6 圖 1 4 是一個五子棋棋盤 A B 兩人輪流走步 誰先布成五子一線 橫線 豎線 對角線均可 誰就獲勝 請定義估價函數(shù) 并站在 A 的立場上 找 出當前的最佳走步 P200 5 36 7 某問題的狀態(tài)空間圖如下圖所示 其中括號內(nèi)標明的是各節(jié)點的 h 值 弧線 邊的數(shù)字是該弧線的代價 試用 A 算法求解從初始節(jié)點 S 到目標節(jié)點 T 的路 徑 要求給出搜索圖 標明各節(jié)點的 f 值 及各節(jié)點的擴展次序 并給出求 得的解路徑 12 答 搜索圖如圖所示 其中括號內(nèi)標出的是節(jié)點的 f 值 圓圈內(nèi)的數(shù)字是擴展的次序 F 16 得到的解路徑為 S B F J T 8 有四人過河 只有一條船 最多可乘坐兩人