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

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