人工智能技術(shù)實(shí)驗(yàn)指導(dǎo)書

實(shí)用文檔人工智能技術(shù)實(shí)驗(yàn)指導(dǎo)書目錄前言………………………….1實(shí)驗(yàn)一刺激響應(yīng)Agent實(shí)驗(yàn)…………….2實(shí)驗(yàn)二能計(jì)劃的Agent實(shí)驗(yàn)（一）………4實(shí)驗(yàn)三能計(jì)劃的Agent實(shí)驗(yàn)（二）………6實(shí)驗(yàn)四雙Agent博弈實(shí)驗(yàn)（一）…………7實(shí)驗(yàn)五雙Agent博弈實(shí)驗(yàn)（二）…………9實(shí)驗(yàn)六謂詞邏輯與歸結(jié)原理實(shí)驗(yàn)（一）…………………11實(shí)驗(yàn)七謂詞邏輯與歸結(jié)原理實(shí)驗(yàn)（二）…………………13實(shí)驗(yàn)八學(xué)習(xí)Agent實(shí)驗(yàn)…………………15前言人工智能技術(shù)實(shí)驗(yàn)是為了結(jié)合研究生人工智能理論課程的學(xué)習(xí)而開設(shè)的一門實(shí)踐教學(xué)課程，要求學(xué)生通過本課程的學(xué)習(xí)鞏固并進(jìn)一步深入理解理論學(xué)習(xí)所介紹的人工智能的基本原理與方法，掌握人工智能一些主要技術(shù)的實(shí)現(xiàn)方法，提高人工智能程序的設(shè)計(jì)和使用程序設(shè)計(jì)語言實(shí)際編程的能力。學(xué)習(xí)本課程要求學(xué)生掌握程序設(shè)計(jì)基本知識和至少一種程序設(shè)計(jì)語言，學(xué)過人工智能原理。 本實(shí)驗(yàn)指導(dǎo)書中共有八個(gè)實(shí)驗(yàn)，涵蓋了人工智能的一些基本技術(shù)，包括能對周圍環(huán)境進(jìn)行探測并做出響應(yīng)的刺激響應(yīng)Agent實(shí)驗(yàn)；能在解空間中進(jìn)行搜索，尋找問題求解方法的能計(jì)劃的Agent實(shí)驗(yàn)；能夠在游戲中與對手較量的雙Agent博弈實(shí)驗(yàn)；能夠進(jìn)行邏輯推理的謂詞邏輯與歸結(jié)原理實(shí)驗(yàn)；能夠進(jìn)行學(xué)習(xí)和優(yōu)化的學(xué)習(xí)Agent實(shí)驗(yàn)等。其中，實(shí)驗(yàn)三、實(shí)驗(yàn)五、實(shí)驗(yàn)七相對于實(shí)驗(yàn)二、實(shí)驗(yàn)四、實(shí)驗(yàn)六要復(fù)雜一些，可供學(xué)生根據(jù)自己的基礎(chǔ)和程序設(shè)計(jì)能力選做。實(shí)驗(yàn)指導(dǎo)書對每個(gè)實(shí)驗(yàn)首先提出了實(shí)驗(yàn)?zāi)康暮鸵?，主要指出通過實(shí)驗(yàn)所要掌握的人工智能的基本技術(shù)；然后簡單介紹與該實(shí)驗(yàn)相關(guān)的人工智能技術(shù)的基本知識，以便讀者回憶和復(fù)習(xí)人工智能原理的有關(guān)內(nèi)容，為完成實(shí)驗(yàn)做好準(zhǔn)備；最后給出了實(shí)驗(yàn)內(nèi)容和進(jìn)行方式，具體給出實(shí)際的應(yīng)用環(huán)境和要解決的問題以及對程序功能的要求。實(shí)驗(yàn)一刺激響應(yīng)Agent實(shí)驗(yàn)實(shí)驗(yàn)?zāi)康呐c要求目的：掌握產(chǎn)生式系統(tǒng)的結(jié)構(gòu)和設(shè)計(jì)方法，了解刺激響應(yīng)Agent的工作原理。要求：設(shè)計(jì)生活在一個(gè)二維網(wǎng)格世界中的“人工螞蟻”的模擬程序?；局R刺激響應(yīng)（stimulus-response）Agent指的是沒有內(nèi)部狀態(tài)而只是對所感知到的環(huán)境刺激給出簡單反應(yīng)的機(jī)器。刺激響應(yīng)Agent是具有傳感器和效應(yīng)器、處于某一環(huán)境中的實(shí)體。它通過傳感器感知環(huán)境，通過效應(yīng)器作用于環(huán)境。這種Agent能夠?qū)Νh(huán)境主動(dòng)進(jìn)行監(jiān)視，并能做出必要的反應(yīng)。刺激響應(yīng)Agent最典型的應(yīng)用是機(jī)器人，特別是Brookes類型的機(jī)器昆蟲。實(shí)驗(yàn)內(nèi)容與進(jìn)行方式“人工螞蟻”生活在一個(gè)二維網(wǎng)格世界中，它能沿已作標(biāo)記的單元所組成的連續(xù)“信息素蹤跡”(寬為一個(gè)單元)的運(yùn)動(dòng)。這個(gè)螞蟻占一個(gè)單元，它可以面向東、南、西、北。它能做五個(gè)動(dòng)作：前移一個(gè)單元(m)；在同一單元中向左轉(zhuǎn)(l)；在同一單元中向右轉(zhuǎn)(r)；設(shè)置狀態(tài)位元“開”(on)；設(shè)置狀態(tài)位元“關(guān)”(off)。螞蟻感知它的正前方(即其面朝的方向)是否有信息素蹤跡且其狀態(tài)位元是否為“開”，若狀態(tài)位元為“開”表示該單元已經(jīng)走過（設(shè)狀態(tài)位元起初為“關(guān)”）。如圖一中黑色的單元組成了信息素蹤跡，紅色的圓形表示人工螞蟻。描述可以控制這樣一個(gè)跟蹤以上路線的螞蟻的一個(gè)產(chǎn)生式系統(tǒng)。設(shè)這個(gè)螞蟻?zhàn)畛跷挥谝粋€(gè)可感知的信息素蹤跡單元中，面向東方（請記住，產(chǎn)生式系統(tǒng)由一個(gè)有序的條件—?jiǎng)幼饕?guī)則集合組成；所執(zhí)行的動(dòng)作與首先滿足的那個(gè)條件相應(yīng)。每個(gè)規(guī)則的動(dòng)作部分可以有一個(gè)以上的動(dòng)作）。確保螞蟻不會(huì)折反自己走過的路線。寫一個(gè)模擬人工螞蟻行為的算法，并編制程序，分別對圖中的三只螞蟻，給出運(yùn)行的結(jié)果。北?圖一人工螞蟻的網(wǎng)格世界附：蟻群算法簡介20世紀(jì)90年代初意大利學(xué)者Dorigo，Maniezzo提出的第一個(gè)“蟻群算法（antcolonyalgorithm）”是依照螞蟻覓食原理，設(shè)計(jì)的一個(gè)群體智能的算法。其原理如下。據(jù)研究當(dāng)螞蟻找到食物并將它搬回來時(shí)，就會(huì)在其經(jīng)過的路徑上留下一種“外激素”，其他螞蟻嗅到這個(gè)激素的“味道”，就沿該路奮勇向前，覓食而去。不但如此而且還會(huì)沿著最短的路徑奔向食物。下面我們分析一下螞蟻是如何找到通向食物的最短路徑的呢？設(shè)一群螞蟻（隨機(jī)地）從蟻巢O向四面八方去覓食，當(dāng)某只螞蟻在A點(diǎn)覓到食物時(shí)，一般就沿原路回巢，同時(shí)在歸途上留下外激素，外激素隨著向四周散發(fā)其濃度會(huì)不斷下降。若有兩只螞蟻分別沿路徑OBA和路徑OA找到食物，且沿原路返回（見圖一）設(shè)OA比OBA短，當(dāng)?shù)谝恢晃浵伝氐絆點(diǎn)時(shí)，第二只螞蟻（沿OBA的螞蟻）才回到C點(diǎn)。于是OA路上有兩次外激素的遺留物（去一次、回來一次），而在OC路是只有去一次的外激素遺留物，故OA的外激素濃度比OC上大。據(jù)研究螞蟻一般會(huì)沿外激素濃度大的路徑上前BCOA圖二螞蟻覓食路徑示意圖行，于是后面的螞蟻會(huì)漸漸地沿由O到A的最短程到達(dá)A點(diǎn)（指所有已求到的路徑中的最短者）。以上就是螞蟻能以最短路徑找到食物的原因。根據(jù)這個(gè)原理可以設(shè)計(jì)出求最短路徑的蟻群算法。下面以求通過n個(gè)城市的最短回路為例。設(shè)有n個(gè)城市，在t時(shí)刻在第i個(gè)城市上有螞蟻ai(t)個(gè)，共有m個(gè)螞蟻。設(shè)在t時(shí)刻在連接第i,j兩城市間的道路留下的外激素量為bij(t)。規(guī)定每個(gè)螞蟻在未完成一個(gè)回路時(shí),不重復(fù)走已走過的城市。則第k個(gè)螞蟻從i城市到j(luò)城市的概率Pijk=bPijk=l允許到達(dá)的城市bil(t)其中外激素量bij(t)有許多不同的定義,如可定義為：b(t)=e-ct，c>0；或定義為：bij(t+1)=dbij(t)+dij(t)，其中dij(t)=k=1..m(e/Lk)ijk(t)，d、e為正常量，Lk是第k個(gè)螞蟻求得的回路長度，若第t輪第k只螞蟻經(jīng)過邊(i,j)則ijk(t)=1，否則ijk(t)=0。這樣每只螞蟻經(jīng)過n次遷移后就得到一條回路,其長度記為Lk.若滿足要求,則停止。不然，利用(1)式重新計(jì)算各邊的外激素濃度,進(jìn)行第二輪的搜索。借助螞蟻的啟迪，不但可以開發(fā)出求最短程的算法，還可以開發(fā)出其它的算法，下面再舉一、二。據(jù)說螞蟻很愛衛(wèi)生，對其窩內(nèi)經(jīng)常進(jìn)行大掃除，將垃圾堆在一起，然后拉到窩外。根據(jù)螞蟻的上述行為，人們以螞蟻為師設(shè)計(jì)分類算法：一群螞蟻隨機(jī)出發(fā)，遇到垃圾，就將其拉走（拉的方向也是隨機(jī)的），拉垃圾時(shí)，若遇到某一堆垃圾時(shí)，就放下。放下垃圾后，再次進(jìn)行拉垃圾行為。當(dāng)然還要加了一些限制，才能達(dá)到人們所希望的結(jié)果。另外，螞蟻同心協(xié)進(jìn)行搬運(yùn)食物，是我們見得最多的螞蟻行為，有人以此為藍(lán)本設(shè)計(jì)出幾個(gè)機(jī)器人共同推盒子的算法。借助螞蟻分工合作的特點(diǎn)（蟻皇管生男育女、工蟻管干活、兵蟻管保衛(wèi)）的啟迪，人們設(shè)計(jì)了求解任務(wù)分配問題的螞蟻算法，并應(yīng)用于工廠中汽車噴漆問題。工人分成小組，各組只噴一種顏色，只有當(dāng)某小組任務(wù)特別緊張時(shí)，才分配另一小組前去幫助。通過這種設(shè)計(jì)后工廠各車間改變顏色的次數(shù)更少，從而提高了整體的生產(chǎn)率。實(shí)驗(yàn)二能計(jì)劃的Agent實(shí)驗(yàn)（一）實(shí)驗(yàn)?zāi)康呐c要求目的：熟悉狀態(tài)空間的基本搜索方法，比較盲目搜索算法、A算法和A*算法。要求：編制一個(gè)15數(shù)碼難題解題程序。基本知識狀態(tài)圖實(shí)際上是一類問題的抽象表示。事實(shí)上，有許多智力問題(如梵塔問題、旅行商問題、八皇后問題、農(nóng)夫過河問題等)和實(shí)際問題（如路徑規(guī)劃、定理證明、演繹推理、機(jī)器人行動(dòng)規(guī)劃等）都可以歸結(jié)為在某一狀態(tài)圖中尋找目標(biāo)或路徑的問題。因此，研究狀態(tài)圖搜索具有普遍意義。狀態(tài)圖中的狀態(tài)是表示問題求解過程中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)，包括由問題已知的前提、初始條件的原始描述所構(gòu)成的初始狀態(tài)，問題解決時(shí)應(yīng)該到達(dá)的目標(biāo)狀態(tài)以及問題求解過程中由初始狀態(tài)可能到達(dá)的中間狀態(tài)。狀態(tài)圖中的邊為操作，操作是把一種狀態(tài)變成另一種狀態(tài)的運(yùn)算。在狀態(tài)空間中進(jìn)行搜索，以找到一條從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)的（最佳）路徑的方法稱為狀態(tài)空間法。產(chǎn)生式系統(tǒng)由三部分組成：產(chǎn)生式規(guī)則庫、推理機(jī)和動(dòng)態(tài)數(shù)據(jù)庫。產(chǎn)生式規(guī)則庫亦稱產(chǎn)生式規(guī)則集，由領(lǐng)域規(guī)則組成，在機(jī)器中以某種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)進(jìn)行組織。推理機(jī)亦稱控制執(zhí)行機(jī)構(gòu)，它是一個(gè)程序模塊，負(fù)責(zé)產(chǎn)生式規(guī)則的前提條件測試或匹配，規(guī)則的調(diào)度與選取，規(guī)則體的解釋和執(zhí)行。即推理機(jī)實(shí)施推理，并對推理進(jìn)行控制，它也就是規(guī)則的解釋程序。產(chǎn)生式系統(tǒng)運(yùn)行時(shí)，除了需要規(guī)則庫以外，還需要有初始事實(shí)(或數(shù)據(jù))和目標(biāo)條件。目標(biāo)條件是系統(tǒng)正常結(jié)束的條件，也是系統(tǒng)的求解目標(biāo)。產(chǎn)生式系統(tǒng)啟動(dòng)后，推理機(jī)就開始推理，按所給的目標(biāo)進(jìn)行問題求解。一個(gè)實(shí)際的產(chǎn)生式系統(tǒng)，其目標(biāo)條件一般不會(huì)只經(jīng)一步推理就可滿足，往往要經(jīng)過多步推理才能滿足或者證明問題無解?？梢钥闯觯瑘D搜索與產(chǎn)生式系統(tǒng)實(shí)際是一回事。要說差別的話，圖搜索技術(shù)描述了問題求解的方法，而產(chǎn)生式系統(tǒng)則給出了實(shí)施這種方法的一種計(jì)算機(jī)程序系統(tǒng)的結(jié)構(gòu)模式。這樣，問題求解、圖搜索和產(chǎn)生式系統(tǒng)三者的關(guān)系是：問題求解是目的，圖搜索是方法，產(chǎn)生式系統(tǒng)是形式。對于狀態(tài)圖搜索，已經(jīng)提出了許多策略，它們大體可分為盲目搜索和啟發(fā)式（heuristic）搜索兩大類。盲目搜索按搜索樹生成方式可分為廣度優(yōu)先和深度優(yōu)先兩種搜索方式。這兩種方式也是最基本的樹式搜索策略，其他搜索策略都是建立在它們的基礎(chǔ)之上的。廣度優(yōu)先搜索就是始終先在同一級節(jié)點(diǎn)中考查，只有當(dāng)同一級節(jié)點(diǎn)考查完之后，才考查下一級節(jié)點(diǎn)。或者說，是以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，向下逐級擴(kuò)展搜索樹。所以，廣度優(yōu)先策略的搜索樹是自頂向下一層一層逐漸生成的。深度優(yōu)先搜索就是在搜索樹的每一層始終先只擴(kuò)展一個(gè)子節(jié)點(diǎn)，不斷地向縱深前進(jìn)，直到不能再前進(jìn)(到達(dá)葉子節(jié)點(diǎn)或受到深度限制)時(shí)，才從當(dāng)前節(jié)點(diǎn)返回到上一級節(jié)點(diǎn)，沿另一方向又繼續(xù)前進(jìn)。這種方法的搜索樹是從樹根開始一枝一枝逐漸形成的。啟發(fā)式搜索就是利用啟發(fā)性信息進(jìn)行制導(dǎo)的搜索。窮舉搜索法從理論上講，似乎可以解決任何狀態(tài)空間的搜索問題，但實(shí)踐表明，窮舉搜索只能解決一些狀態(tài)空間很小的簡單問題，而對于那些大狀態(tài)空間問題，窮舉搜索就不能勝任了。因?yàn)榇罂臻g問題，往往會(huì)導(dǎo)致“組合爆炸”。啟發(fā)性信息就是有利于盡快找到問題之解的信息。按其用途劃分，啟發(fā)性信息一般可以(1)用于擴(kuò)展節(jié)點(diǎn)的選擇，即用于決定應(yīng)先擴(kuò)展哪一個(gè)節(jié)點(diǎn)，以免盲目擴(kuò)展。(2)用于生成節(jié)點(diǎn)的選擇，即用于決定應(yīng)生成哪些后續(xù)節(jié)點(diǎn)，以免盲目地生成過多無用節(jié)點(diǎn)。(3)用于刪除節(jié)點(diǎn)的選擇，即用于決定應(yīng)刪除哪些無用節(jié)點(diǎn)，以免造成進(jìn)一步的時(shí)空浪費(fèi)。在啟發(fā)式搜索中，通常用所謂啟發(fā)函數(shù)來表示啟發(fā)性信息。啟發(fā)函數(shù)是用來估計(jì)搜索樹上節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)接近程度的一種函數(shù)，通常記為h(x)。啟發(fā)函數(shù)并無固定的模式，需要具體問題具體分析。通?？梢詤⒖嫉乃悸酚校阂粋€(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的某種距離或差異的度量；一個(gè)節(jié)點(diǎn)處在最佳路徑上的概率；或者根據(jù)經(jīng)驗(yàn)的主觀打分等等。啟發(fā)式搜索要用啟發(fā)函數(shù)來導(dǎo)航，其搜索算法就要在狀態(tài)圖一般搜索算法基礎(chǔ)上再增加啟發(fā)函數(shù)值的計(jì)算與傳播過程，并且由啟發(fā)函數(shù)值來確定節(jié)點(diǎn)的擴(kuò)展順序。下面介紹兩種典型的啟發(fā)式圖搜索的A算法和A*算法。利用啟發(fā)函數(shù)h(x)制導(dǎo)的啟發(fā)式搜索，實(shí)際是一種深度優(yōu)先的搜索策略。雖然它是很高效的，但也可能誤入歧途。所以，為了更穩(wěn)妥一些，人們把啟發(fā)函數(shù)擴(kuò)充為估價(jià)函數(shù)。估價(jià)函數(shù)的一般形式為f(x)＝g(x)＋h(x)其中g(shù)(x)為從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x已經(jīng)付出的代價(jià)，h(x)是啟發(fā)函數(shù)。即估價(jià)函數(shù)f(x)是從初始節(jié)點(diǎn)S0到達(dá)節(jié)點(diǎn)x處已付出的代價(jià)與節(jié)點(diǎn)x到達(dá)目標(biāo)節(jié)點(diǎn)Sg的接近程度估計(jì)值之總和。A算法是基于估價(jià)函數(shù)f(x)的一種加權(quán)狀態(tài)圖啟發(fā)式搜索算法。如果對上述A算法再限制其估價(jià)函數(shù)中的啟發(fā)函數(shù)h(x)滿足：對所有的節(jié)點(diǎn)x均有h(x)≤h*(x)其中h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià)(若有多個(gè)目標(biāo)節(jié)點(diǎn)則為其中最小的一個(gè))，則它就稱為A*算法。實(shí)驗(yàn)內(nèi)容與進(jìn)行方式數(shù)碼問題常被用來演示如何在狀態(tài)空間中生成動(dòng)作序列。一個(gè)典型的例子是15數(shù)碼問題，它由放在一個(gè)4×4的棋盤中的15個(gè)數(shù)碼構(gòu)成，棋盤中的一個(gè)單元是空的，它的周邊單元中的數(shù)碼可以移到該單元中。此問題的任務(wù)是找到一個(gè)數(shù)碼移動(dòng)序列使初始的無序數(shù)碼轉(zhuǎn)變?yōu)橐恍┨厥獾呐帕小?數(shù)碼問題是一個(gè)簡化版本，在一個(gè)3×3的棋盤中有8個(gè)數(shù)碼。假定該問題的目標(biāo)是把數(shù)碼從開始狀態(tài)移動(dòng)到目標(biāo)狀態(tài)，如圖8-1所示。在這個(gè)問題中，一個(gè)明顯的問題狀態(tài)描述是一個(gè)3×3的方陣，方陣的每個(gè)單元中包含1～8之間的數(shù)字或一個(gè)代表空格的符號。目標(biāo)狀態(tài)是圖8-1中右邊的方陣。狀態(tài)間的轉(zhuǎn)變就是把一個(gè)數(shù)碼移到空的單元中。一般地講，在構(gòu)造一個(gè)問題的狀態(tài)空間時(shí)我們有一些代表性的選擇。在8數(shù)碼問題中，我們可以想像有8×4個(gè)不同的移動(dòng)，它們是：1上移、1下移、1左移、1右移、2上移、...，等等（當(dāng)然在一個(gè)給定的狀態(tài)中，并不是所有的這些移動(dòng)都是可能的）。一個(gè)更精練的選擇只有4個(gè)移動(dòng)，即：空格左移、空格上移、空格右移和空格下移。一個(gè)給定的開始狀態(tài)和一組可能的移動(dòng)隱式地定義了從開始狀態(tài)可到達(dá)的狀態(tài)空間圖。在8數(shù)碼表示的狀態(tài)空間中節(jié)點(diǎn)數(shù)是9！=362880個(gè)（8數(shù)碼狀態(tài)空間剛好可以分成兩個(gè)獨(dú)立的圖；一個(gè)圖中的狀態(tài)不能從另一個(gè)圖中的狀態(tài)到達(dá)）。圖三8數(shù)碼問題的開始和目標(biāo)狀態(tài) 請分別給出用盲目搜索算法、A算法和A*算法解決15數(shù)碼難題的算法，并編制程序?qū)τ谌我廨斎氲某跏计寰趾湍繕?biāo)棋局，求出解決的步驟。并通過具體的例子比較三種算法的性能。注意：給的例子是8數(shù)碼難題，要求解決的是15數(shù)碼難題。實(shí)驗(yàn)三能計(jì)劃的Agent實(shí)驗(yàn)（二）實(shí)驗(yàn)?zāi)康呐c要求目的：進(jìn)一步掌握啟發(fā)式搜索的方法，學(xué)習(xí)分析問題獲得啟發(fā)信息的方法。要求：完成Caesar密碼破解程序?；局R啟發(fā)式搜索就是利用啟發(fā)性信息進(jìn)行制導(dǎo)的搜索。窮舉搜索法從理論上講，似乎可以解決任何狀態(tài)空間的搜索問題，但實(shí)踐表明，窮舉搜索只能解決一些狀態(tài)空間很小的簡單問題，而對于那些大狀態(tài)空間問題，窮舉搜索就不能勝任了。因?yàn)榇罂臻g問題，往往會(huì)導(dǎo)致“組合爆炸”。啟發(fā)性信息就是有利于盡快找到問題之解的信息。正確地選擇啟發(fā)函數(shù)對搜索結(jié)果起著決定的作用：使用不能識別某些節(jié)點(diǎn)真實(shí)價(jià)值的啟發(fā)函數(shù)會(huì)得到非最佳解，而使用一個(gè)過多地估計(jì)了全部節(jié)點(diǎn)希望的啟發(fā)函數(shù)又會(huì)擴(kuò)展過多的節(jié)點(diǎn)。如用f(x)=g(x)，就得到寬度優(yōu)先的搜索過程。好的啟發(fā)函數(shù)依賴于對問題本身的認(rèn)識——知識。因?yàn)閱l(fā)信息與要求解的實(shí)際問題相關(guān)，啟發(fā)函數(shù)要根據(jù)對問題的了解和相關(guān)知識來設(shè)計(jì)，使得搜索過程可以在啟發(fā)信息制導(dǎo)下向著求解目標(biāo)進(jìn)行，大大提高搜索效率。實(shí)驗(yàn)內(nèi)容與進(jìn)行方式Caesar密碼是一種簡單的基于字母表循環(huán)置換的加密方案，即字母表中的第i個(gè)字母用字母表中的第（i+n）個(gè)字母替換，其中n為偏移量。例如，在偏移量為4的Caesar密碼系統(tǒng)中，“Caesar”會(huì)被加密為“Geiwev”。要求給出一種用于破解Caesar密碼的啟發(fā)函數(shù)，并設(shè)計(jì)出破解程序完成破解Caesar密碼的實(shí)驗(yàn)。另一種在Caesar密碼基礎(chǔ)上加以改進(jìn)的簡單的置換加密方案是每一個(gè)字母以某種任意的一對一映射方式用另外一個(gè)字母替換。請給出用于破解這種密碼的一個(gè)啟發(fā)函數(shù)，設(shè)計(jì)出破解程序。說明：此實(shí)驗(yàn)中搜索的目標(biāo)節(jié)點(diǎn)不是顯式的，需要設(shè)置一定的判別條件。實(shí)驗(yàn)四雙Agent博弈實(shí)驗(yàn)（一）實(shí)驗(yàn)?zāi)康呐c要求目的：掌握敵對搜索的基本方法。要求：完成二維網(wǎng)格中的機(jī)器人“追捕”程序?；局R諸如下棋、打牌、競技、戰(zhàn)爭等一類競爭性智能活動(dòng)稱為博弈。其中最簡單的一種稱為“二人零和、全信息、非偶然”博弈。所謂“二人零和、全信息、非偶然”博弈是指：(1)對壘的A，B雙方輪流采取行動(dòng)，博弈的結(jié)果只有三種情況：A方勝，B方?。籅方勝，A方??；雙方戰(zhàn)成平局。(2)在對壘過程中，任何一方都了解當(dāng)前的格局及過去的歷史。(3)任何一方在采取行動(dòng)前都要根據(jù)當(dāng)前的實(shí)際情況，進(jìn)行得失分析，選取對自己最為有利而對對方最為不利的對策，不存在“碰運(yùn)氣”的偶然因素。即雙方都是很理智地決定自己的行動(dòng)。在博弈過程中，任何一方都希望自己取得勝利。因此，當(dāng)某一方當(dāng)前有多個(gè)行動(dòng)方案可供選擇時(shí)，他總是挑選對自己最為有利而對對方最為不利的那個(gè)行動(dòng)方案。這樣，如果站在某一方（如A方，即在A要取勝的意義下），把上述博弈過程用圖表示出來，則得到的是一棵“與或樹”。描述博弈過程的與或樹稱為博弈樹，它有如下特點(diǎn)：(1)博弈的初始格局是初始節(jié)點(diǎn)。(2)在博弈樹中，“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)是逐層交替出現(xiàn)的。自己一方擴(kuò)展的節(jié)點(diǎn)之間是“或”關(guān)系，對方擴(kuò)展的節(jié)點(diǎn)之間是“與”關(guān)系。雙方輪流地?cái)U(kuò)展節(jié)點(diǎn)。(3)所有自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對方獲勝的終局都是不可解節(jié)點(diǎn)。在二人博弈問題中，為了從眾多可供選擇的行動(dòng)方案中選出一個(gè)對自己最為有利的行動(dòng)方案，就需要對當(dāng)前的情況以及將要發(fā)生的情況進(jìn)行分析，從中選出最優(yōu)的走步。最常使用的分析方法是極小極大分析法。其基本思想是：(1)設(shè)博弈的雙方中一方為A，另一方為B。然后為其中的一方(例如A)尋找一個(gè)最優(yōu)行動(dòng)方案。(2)為了找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對各個(gè)可能的方案所產(chǎn)生的后果進(jìn)行比較。(3)為計(jì)算得分，需要根據(jù)問題的特性信息定義一個(gè)估價(jià)函數(shù)，用來估算當(dāng)前博弈樹端節(jié)點(diǎn)的得分。(4)當(dāng)端節(jié)點(diǎn)的估值計(jì)算出來后，再推算出父節(jié)點(diǎn)的得分，推算的方法是：對“或”（MAX）節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最大的得分作為父節(jié)點(diǎn)的得分，這是為了使自己在可供選擇的方案中選一個(gè)對自己最有利的方案；對“與”（MIN）節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最小的得分作為父節(jié)點(diǎn)的得分，這是為了立足于最壞的情況。(5)如果一個(gè)行動(dòng)方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動(dòng)方案。圖4—18給出了計(jì)算倒推值的示例。上述的極小極大分析法，實(shí)際是先生成一棵博弈樹，然后再計(jì)算其倒推值。這樣做的缺點(diǎn)是效率較低。于是,人們又在極小極大分析法的基礎(chǔ)上,提出了α—β剪枝技術(shù)。具體的剪枝方法如下：(1)對于一個(gè)與節(jié)點(diǎn)MIN，若能估計(jì)出其倒推值的上確界β，并且這個(gè)β值不大于MIN的父節(jié)點(diǎn)(一定是或節(jié)點(diǎn))的估計(jì)倒推值的下確界α，即α≥β,則就不必再擴(kuò)展該MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對MIN父節(jié)點(diǎn)的倒推值已無任何影響了)。這一過程稱為α剪枝。(2)對于一個(gè)“或”節(jié)點(diǎn)MAX，若能估計(jì)出其倒推值的下確界α,并且這個(gè)α值不小于MAX的父節(jié)點(diǎn)(一定是與節(jié)點(diǎn))的估計(jì)倒推值的上確界β,即α≥β,則就不必再擴(kuò)展該MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對MAX父節(jié)點(diǎn)的倒推值已無任何影響了)。這一過程稱為β剪枝。實(shí)驗(yàn)內(nèi)容與進(jìn)行方式以圖三中的網(wǎng)格為例，兩個(gè)機(jī)器人，分別命名為“black”和“white”。它們可以向其所在的行或列中的相鄰一格交替地移動(dòng)（比如說，white先移動(dòng)），而且輪到其中一個(gè)時(shí)，它必須移動(dòng)。假設(shè)white的目標(biāo)是與black在同一格，而black的目標(biāo)是避免發(fā)生這種情況。white就可建立一棵搜索樹，在交替的級別上，black可能的行動(dòng)也被考慮進(jìn)去。請為white編寫一個(gè)追捕black的程序，試試用鍵盤控制black時(shí)，white移動(dòng)的情況。再為black編寫一個(gè)逃避white追捕的程序，看看在某種初始局面下，計(jì)算機(jī)自動(dòng)運(yùn)行追捕過程的情況。對每個(gè)程序，給出算法描述，并給出能說明兩個(gè)機(jī)器人移動(dòng)過程的運(yùn)行結(jié)果。圖四在網(wǎng)格環(huán)境中的兩個(gè)機(jī)器人實(shí)驗(yàn)五雙Agent博弈實(shí)驗(yàn)（二）實(shí)驗(yàn)?zāi)康呐c要求目的：掌握帶有機(jī)會(huì)因素的博弈搜索方法。要求：編寫西洋雙陸棋博弈程序?；局R在實(shí)際生活中存在許多不可預(yù)測的外部事件迫使我們陷入未預(yù)見到的情境中。一些游戲含有某種隨機(jī)的因素如擲骰子來反映這種不可預(yù)測性。這樣使我們更接近實(shí)際，因此值得研究這種不可預(yù)測性是如何影響決策過程的。西洋雙陸棋是典型的機(jī)會(huì)與技巧相結(jié)合的游戲。輪到的一方游戲者首先擲骰子來決定他可以采用的合法的走步集合。在下圖所示的西洋雙陸棋棋局中，白方擲了6-5，所以有5種可能的走步：(5-10,5-11),(5-11,19-24),(5-10,10-16),(5-11,11-16),(5-10,19-25)。012345678910111225242322212019181716151413圖五一個(gè)典型的西洋雙陸棋棋局盡管白方知道自己的合法走步，但他并不知道黑方擲骰子將會(huì)擲出什么樣的結(jié)果來，從而也不知道什么將是黑方的合法走步。這意味著白方不可能構(gòu)造完整的博弈樹。西洋雙陸棋的博弈樹除了極大極小節(jié)點(diǎn)還必須包括機(jī)會(huì)節(jié)點(diǎn)。在圖六中，圓形的節(jié)點(diǎn)為機(jī)會(huì)節(jié)點(diǎn)。從每個(gè)機(jī)會(huì)節(jié)點(diǎn)引出的分支表示擲骰子的可能性，每個(gè)分支上標(biāo)明擲出的點(diǎn)數(shù)和其出現(xiàn)的概率。擲兩個(gè)骰子共有36種結(jié)果，每種結(jié)果都有相同的可能性；但是，因?yàn)?-5和5-6的效果是一樣的，所以實(shí)際上只有21種不同的結(jié)果。兩個(gè)骰子點(diǎn)數(shù)相同的情況有6種(1-1至6-6)，每種出現(xiàn)的機(jī)會(huì)為1/36，其他15種不同的組合出現(xiàn)的機(jī)會(huì)各為1/18。下一步是分析怎樣做出正確的決策。顯然，我們希望選擇導(dǎo)致最好棋局的走步。但是，每一個(gè)可能的棋局不再具有確定的極小極大值（在確定性博弈中該值是最好下法所到達(dá)的葉節(jié)點(diǎn)的估價(jià)值）。取而代之，我們只能計(jì)算一個(gè)平均值或期望值，這里平均值是在可能出現(xiàn)的所有擲骰子的結(jié)果上計(jì)算得到的。MAXBBDICE1/366,61/186,51/181,21/366,61/186,51/181,21/361,1MINCCDICE1/366,61/186,51/181/366,61/186,51/181,21/361,1MAXTERMINAL2-11-11圖六西洋雙陸棋的博弈樹計(jì)算節(jié)點(diǎn)的期望值是簡單的。對于端節(jié)點(diǎn)，像確定性博弈一樣我們使用估價(jià)函數(shù)計(jì)算。在搜索樹向上一層，我們遇到一個(gè)機(jī)會(huì)節(jié)點(diǎn)。在圖六中機(jī)會(huì)節(jié)點(diǎn)是圓圈；我們看一下標(biāo)記為C的節(jié)點(diǎn)。設(shè)di是一種可能的擲骰子的點(diǎn)數(shù)，P(di)是擲得該點(diǎn)數(shù)的機(jī)會(huì)或概率。對每一次投擲，我們計(jì)算MIN最好走步的棋局估價(jià)值，然后求所有估價(jià)值的加權(quán)和，每個(gè)估價(jià)值的權(quán)為擲得該點(diǎn)數(shù)的概率。如果用S(C,di)表示在棋局C下擲得概率為p(di)的點(diǎn)數(shù)di其中，utility(s)為棋局s的估價(jià)值。這就給出了在棋局C下采取最好的走步所得到棋局的期望估價(jià)值。再向上一層為MIN節(jié)點(diǎn)（圖中為倒三角形），因?yàn)槲覀円呀?jīng)計(jì)算了所有機(jī)會(huì)節(jié)點(diǎn)的估價(jià)值，現(xiàn)在可用極小極大值公式得到MIN節(jié)點(diǎn)的估計(jì)值。進(jìn)一步我們向上移動(dòng)到機(jī)會(huì)節(jié)點(diǎn)B，在此可以采用與期望最大值類似的公式計(jì)算其期望極小值。 這一過程可以沿著博弈樹向上反復(fù)應(yīng)用，除了已經(jīng)知道擲得點(diǎn)數(shù)的最頂層。所以，為了計(jì)算最好的走步，我們只要把確定的博弈樹中的極小極大值換成期望極小極大值就行了。實(shí)驗(yàn)內(nèi)容與進(jìn)行方式 西洋雙陸棋類似于飛行棋。開始時(shí)雙方各自的15枚棋分別從棋盤外（相當(dāng)于圖五中標(biāo)示的0和25的位置）進(jìn)入棋盤，游戲的目標(biāo)是將自己所有的棋通過棋盤走一遍再移出棋盤。白棋從0開始順時(shí)針方向移向25，黑棋從25逆時(shí)針方向移向0。每次可移動(dòng)兩個(gè)棋，移動(dòng)的步數(shù)由擲兩枚骰子決定。如果一個(gè)位置上已經(jīng)有對方的兩個(gè)或更多的棋，則本方的棋不能移到該位置。如果自己的棋移動(dòng)到的位置恰好有對方的一個(gè)棋，則可將對方的棋吃掉，被吃掉的棋要從頭開始走。在圖五所示的棋局，白方擲了6和5，可以選擇將兩個(gè)在第5格的白棋分別走5步和6步，即走到第10格和第11格，記作(5-10,5-11)。另外4種合法的走步是(5-11,19-24),(5-10,10-16),(5-11,11-16),(5-10,19-25)。根據(jù)上面的介紹，設(shè)計(jì)一種對西洋雙陸棋棋局的估價(jià)函數(shù)，并實(shí)現(xiàn)相應(yīng)的人機(jī)對弈的下棋程序。其中擲骰子的結(jié)果可用隨機(jī)數(shù)產(chǎn)生，棋盤可以畫得簡單一些。實(shí)驗(yàn)六謂詞邏輯與歸結(jié)原理實(shí)驗(yàn)（一）實(shí)驗(yàn)?zāi)康呐c要求目的：掌握基于一階邏輯的知識表達(dá)方法，熟悉消解原理在問題求解中的應(yīng)用。要求：編寫邏輯電路功能診斷與推理程序。基本知識設(shè)a1,a2,…,an表示個(gè)體對象，A表示它們的屬性、狀態(tài)或關(guān)系，則表達(dá)式A(a1,a2,…,an)在謂詞邏輯中就表示一個(gè)(原子)命題。例如，(1)素?cái)?shù)(2)，就表示命題“2是個(gè)素?cái)?shù)”。(2)好朋友（張三，李四），就表示命題“張三和李四是好朋友”。一般地，表達(dá)式P(x1,x2,…,xn)在謂詞邏輯中稱為n元謂詞。其中P是謂詞符號，也稱謂詞，代表一個(gè)確定的特征或關(guān)系(名)。x1,x2,…,xn稱為謂詞的參量或者項(xiàng)，一般表示個(gè)體。個(gè)體變元的變化范圍稱為個(gè)體域（或論述域），包攬一切事物的集合稱為全總個(gè)體域。為了表達(dá)個(gè)體之間的對應(yīng)關(guān)系，我們引入通常數(shù)學(xué)中函數(shù)的概念和記法。例如我們用father(x)表示x的父親，用sum(x,y)表示數(shù)x和y之和。一般地，我們用f(x1,x2,…,xn)表示個(gè)體變元x1,x2,…,xn所對應(yīng)的個(gè)體y，并稱之為n元個(gè)體函數(shù)，簡稱函數(shù)（或函詞、函詞命名式）。其中f是函數(shù)符號，有了函數(shù)的概念和記法，謂詞的表達(dá)能力就更強(qiáng)了。例如，我們用Doctor(father(Li))表示“小李的父親是醫(yī)生”，用E(sq(x),y))表示“x的平方等于y”。約定用大寫英文字母作為謂詞符號，用小寫字母f,g,h等表示函數(shù)符號，用小寫字母x,y,z等作為個(gè)體變元符號，用小寫字母a,b,c等作為個(gè)體常元符號。我們把“所有”、“一切”、“任一”、“全體”、“凡是”等詞統(tǒng)稱為全稱量詞，記為x;把“存在”、“有些”、“至少有一個(gè)”、“有的”等詞統(tǒng)稱為存在量詞，記為x。引入量詞后，謂詞的表達(dá)能力就大大擴(kuò)充了，例如命題“凡是人都有名字”，就可以表示為"x(M(x)→N(x))，其中M(x)表示“x是人”，N(x)表示“x有名字”，該式可讀作“對于任意的x，如果x是人，則x有名字”。這里的個(gè)體域取為全總個(gè)體域。如果把個(gè)體域取為人類集合，則該命題就可以表示為"xN(x)。同理，我們可以把命題“存在不是偶數(shù)的整數(shù)”表示為$x(G(x)∧E(x))，其中G(x)表示“x是整數(shù)”，E(x)表示“x是偶數(shù)”。此式可讀作“存在x，x是整數(shù)并且x不是偶數(shù)”。不同的個(gè)體變元，可能有不同的個(gè)體域。為了方便和統(tǒng)一起見，我們用謂詞表示命題時(shí)，一般總?cè)∪倐€(gè)體域，然后再采取使用限定謂詞的辦法來指出每個(gè)個(gè)體變元的個(gè)體域。具體來講，有下面兩條：(1)對全稱量詞，把限定謂詞作為蘊(yùn)含式之前件加入，即"x(P(x)→…)。(2)對存在量詞，把限定量詞作為一個(gè)合取項(xiàng)加入，即$x(P(x)∧…)。這里的P(x)就是限定謂詞。再舉幾個(gè)例子：1、不存在最大的整數(shù)，我們可以把它翻譯為$x(G(x)∧"y(G(y)→D(x,y))或"x(G(x)→$y(G(y)∧D(y,x))。2、對于所有的自然數(shù)均有x+y>x，"x"y(N(x)∧N(y)→S(x,y,x))。3、某些人對某些食物過敏，$x$y(M(x)∧F(y)∧G(x,y))。謂詞公式：(1)個(gè)體常元和個(gè)體變元都是項(xiàng)。(2)設(shè)f是n元函數(shù)符號，若t1,t2,…,tn是項(xiàng)，則f(t1,t2,…,tn)是項(xiàng)。(3)只有有限次使用(1)，(2)得到的符號串才是項(xiàng)。(4)設(shè)P為n元謂詞符號，t1,t2,…,tn為項(xiàng)，則P(t1,t2,…,tn)稱為原子謂詞公式，簡稱原子公式或者原子。(5)原子公式是謂詞公式。(6)若A,B是謂詞公式，則A,A∧B,A∨B,A→B,AB,$xA,"xA也是謂詞公式。(7)只有有限步應(yīng)用(5)，(6)生成的公式才是謂詞公式。由項(xiàng)的定義，當(dāng)t1,t2,…,tn全為個(gè)體常元時(shí)，所得的原子謂詞公式就是原子命題公式（命題符號）。所以，全體命題公式也都是謂詞公式。謂詞公式亦稱為謂詞邏輯中的合適（式）公式，記為Wff。子句集：原子謂詞公式及其否定稱為文字，若干個(gè)文字的一個(gè)析取式稱為一個(gè)子句，由r個(gè)文字組成的子句叫r—文字子句，1—文字子句叫單元子句，不含任何文字的子句稱為空子句，記為或NIL。例如P∨Q∨R，P(x,y)∨Q(x)都是子句對一個(gè)謂詞公式G，通過以下步驟所得的子句集合S，稱為G的子句集。(1)消去蘊(yùn)含詞→和等值詞?？墒褂眠壿嫷葍r(jià)式:①A→BA∨B②AB(A∨B)∧(B∨A)(2)縮小否定詞的作用范圍，直到其僅作用于原子公式?？墒褂眠壿嫷葍r(jià)式:①(A)A②(A∧B)A∨B③(A∨B)A∧B④"xP(x)?$xP(x)⑤$xP(x)?"xP(x)(3)適當(dāng)改名，使量詞間不含同名指導(dǎo)變元和約束變元。(4)消去存在量詞。消去存在量詞時(shí)，同時(shí)還要進(jìn)行變元替換。變元替換分兩種情況：①若該存在量詞在某些全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變元的一個(gè)函數(shù)代替該存在量詞轄域中的相應(yīng)約束變元，這樣的函數(shù)稱為Skolem函數(shù)；②若該存在量詞不在任何全稱量詞的轄域內(nèi)，則用一個(gè)常量符號代替該存在量詞轄域中的相應(yīng)約束變元，這樣的常量符號稱為Skolem常量。(5)消去所有全稱量詞。(6)化公式為合取范式?？墒褂眠壿嫷葍r(jià)式:①A∨(B∧C)?(A∨B)∧(A∨C)②(A∧B)∨C?(A∨C)∧(B∨C)(7)適當(dāng)改名，使子句間無同名變元。(8)消去合取詞∧，以子句為元素組成一個(gè)集合S。例：求下面謂詞公式的子句集"x{"yP(x,y)→"y［Q(x,y)→R(x,y)］}解由步(1)得"x{"yP(x,y)∨"y［?Q(x,y)∨R(x,y)］}由步(2)得"x{$y?P(x,y)∨"y［?Q(x,y)∧R(x,y)］}由步(3)得"x{$y?P(x,y)∨"z［?Q(x,z)∧R(x,z)］}由步(4)得"x{?P(x,f(x))∨［?Q(x,g(x))∧R(x,g(x))］}由步(5)得P(x,f(x))∨［?Q(x,g(x))∧R(x,g(x))］由步(6)得［P(x,f(x))∨?Q(x,g(x))］∧［P(x,f(x))∨R(x,g(x))］由步(7)得［P(x,f(x))∨Q(x,g(x))］∧［P(y,f(y))∨R(y,g(y))］由步(8)得{P(x,f(x))∨Q(x,g(x)),P(y,f(y))∨R(y,g(y))}或P(x,f(x))∨Q(x,g(x))P(y,f(y))∨R(y,g(y))為原謂詞公式的子句集。命題邏輯中的歸結(jié)原理（亦稱為消解原理）設(shè)L為一個(gè)文字，則稱L與?L為互補(bǔ)文字。設(shè)C1,C2是命題邏輯中的兩個(gè)子句，C1中有文字L1，C2中有文字L2，且L1與L2互補(bǔ)，從C1,C2中分別刪除L1,L2，再將剩余部分析取起來，記構(gòu)成的新子句為C12，則稱C12為C1,C2的歸結(jié)式(或消解式)，C1,C2稱為其歸結(jié)式的親本子句，L1,L2稱為消解基。歸結(jié)式是其親本子句的邏輯結(jié)果。例：設(shè)C1=?P∨Q∨R,C2=?Q∨S,于是C1,C2的歸結(jié)式為?P∨R∨S若先把諸前提條件化為子句形式，再把結(jié)論R的非也化為子句，由所有子句得到子句集S，然后對該子句集施行歸結(jié)，若最后推出了空子句，所以子句集S不可滿足，從而R是題設(shè)前提的邏輯結(jié)果。實(shí)驗(yàn)內(nèi)容與進(jìn)行方式下面的邏輯電路有4條線，W1，W2，W3和W4。它有一個(gè)“與門”A和一個(gè)“反相器”B。輸入線W1和W2或者是“on”或者不是“on”。若與門A運(yùn)行“OK”，則當(dāng)且僅當(dāng)W1和W2都是“on”時(shí)W3才是“on”。如果反相器B運(yùn)行“OK”，則當(dāng)且僅當(dāng)W3不是“on”時(shí)W4才是“on”。1)使用形如OK(A)、ON(W1)的表達(dá)式描述所定義的電路功能。2)使用描述電路功能的公式，假定所有的元件都是運(yùn)行正確的，并且W1和W2是“on”，用歸結(jié)法證明W4不是“on”。3)再次使用描述電路功能的公式，給定W1和W2是“on”，且W4也是“on”，用歸結(jié)法證明或者與門或者反相器不是運(yùn)行正確的。 試描述一個(gè)算法并編制程序完成對上述邏輯電路故障的診斷。實(shí)驗(yàn)七謂詞邏輯與歸結(jié)原理實(shí)驗(yàn)（二）實(shí)驗(yàn)?zāi)康呐c要求目的：掌握從歸結(jié)過程中提取答案的問題求解方法。要求：編寫個(gè)人理財(cái)顧問程序?；局R由上一個(gè)實(shí)驗(yàn)可知，若先把諸前提條件化為子句形式，再把結(jié)論R的非也化為子句，由所有子句得到子句集S，然后對該子句集施行歸結(jié)，若最后推出了空子句，則子句集S不可滿足，從而R是題設(shè)前提的邏輯結(jié)果。在很多問題中，我們不僅要證明存在滿足某個(gè)謂詞的對象，還要推出究竟是哪個(gè)對象滿足該謂詞，這樣能推出具體滿足所說結(jié)論的對象的證明稱為推定證明。而在歸結(jié)反演過程中，我們可以跟蹤變量替換過程，當(dāng)證明結(jié)論成立時(shí)，即歸結(jié)得到空子句時(shí)，替代表示結(jié)論的謂詞中的變量的對象即是我們想要得到的滿足結(jié)論的具體對象，這樣就可以從歸結(jié)反演中提取問題的具體答案。實(shí)驗(yàn)內(nèi)容與進(jìn)行方式個(gè)人理財(cái)顧問的作用是幫助客戶決定是將資金存入銀行儲蓄賬戶還是投資到股票市場。有些投資者可能希望將他們的資金分別投放在這兩個(gè)方面。根據(jù)個(gè)人的收入和當(dāng)前已經(jīng)存儲的金額，理財(cái)顧問按照以下準(zhǔn)則向個(gè)人投資者提出投資建議：1、儲蓄不夠的個(gè)人不論他們的收入多少總是應(yīng)將增加儲蓄額放在優(yōu)先的地位。2、已有足夠儲蓄并且有足夠收入的人應(yīng)考慮股票市場具有一定風(fēng)險(xiǎn)但收益較大的投資。3、已經(jīng)有足夠儲蓄而收入較低的人可考慮將他們多余的收入分開投放在儲蓄和股票兩方面，以增加儲蓄的保障同時(shí)力圖通過股票增加收入。儲蓄和收入是否足夠由個(gè)人要供養(yǎng)的人數(shù)來決定。我們的規(guī)則是對每個(gè)要供養(yǎng)的人至少要有銀行存款5000元。而足夠的收入必須是每年至少15000元以及對每個(gè)要供養(yǎng)的人附加額外的4000元的穩(wěn)定收入。為自動(dòng)實(shí)現(xiàn)上述機(jī)制，我們將其用謂詞演算公式表示。首要任務(wù)是確定必須考慮的主要因素，即足夠的儲蓄和收入。我們分別用謂詞Savings_account和Income。它們兩者都是一元謂詞，其參數(shù)可以是Adequate或Inadequate。于是它們的值可能是Savings_account(Adequate).Savings_account(Inadequate).Income(Adequate).Income(Inadequate).結(jié)論用一元謂詞Investment表示，其參數(shù)可能的值為Stocks，Savings或Combination（表示將資金分開投放）。采用以上謂詞，不同的投資方案可用蘊(yùn)含式表示。第一條規(guī)則，具有不充分儲蓄的人應(yīng)當(dāng)將增加儲蓄放在第一位，被表示為Savings_account(Inadequate)→Investment(Savings).類似地，其余兩種可能的投資方案表示為Savings_account(Adequate)∧Income(Adequate)→Investment(Stocks).Savings_account(Adequate)∧Income(Inadequate)→Investment(Combination).下面顧問必須確定儲蓄和收入是否充足。這也可用蘊(yùn)含式來實(shí)現(xiàn)。需要用函數(shù)完成算術(shù)運(yùn)算。定義函數(shù)minsavings來確定最小的充足的儲蓄量。minsavings有一個(gè)參數(shù)即所供養(yǎng)的人數(shù)，返回5000與人數(shù)的乘積。利用minsavings，儲蓄的充足性由規(guī)則"xAmount_saved(x)∧$y(Dependents(y)∧Greater(x,minsavings(y)))→Savings_account(Adequate)"xAmount_saved(x)∧$y(Dependents(y)∧Greater(x,minsavings(y)))→Savings_account(Inadequate)決定。其中minsavings(x)=5000×x。在此定義中，Amount_saved(x)和Dependents(y)表示投資者當(dāng)前儲蓄量和他所供養(yǎng)的人數(shù)；Greater(x,y)是一個(gè)數(shù)是否大于另一個(gè)數(shù)的標(biāo)準(zhǔn)的算術(shù)檢測，在此沒有進(jìn)一步定義。類似地，函數(shù)minincome定義為minincome(x)=15000+(4000×x)，它被用來在給定供養(yǎng)人數(shù)時(shí)計(jì)算足夠收入最低值。投資者當(dāng)前的收入用謂詞Earnings表示。因?yàn)樽銐虻氖杖氡仨毤确€(wěn)定又超過最低值，Earnings有兩個(gè)參數(shù)：第一個(gè)參數(shù)是收入數(shù)，第二個(gè)為Steady或Unsteady。對于理財(cái)顧問所需要的其他規(guī)則為"xEarnings(x,Steady)∧$y(Dependents(y)∧Greater(x,minincome(y)))→Income(Adequate)"xEarnings(x,Steady)∧$y(Dependents(y)∧Greater(x,minincome(y)))→Income(Inadequate)"xEarnings(x,Unsteady)→Income(Inadequate)在理財(cái)顧問咨詢時(shí)，目標(biāo)是發(fā)現(xiàn)一種投資方式，這可以用謂詞表達(dá)式$xInvestment(x)來表示，其中目標(biāo)變量x是我們要發(fā)現(xiàn)的投資方式。從目標(biāo)出發(fā)，有三條規(guī)則可以推出投資方式。在使用歸結(jié)法推理時(shí)，即可將目標(biāo)取反化成子句與三條規(guī)則化成的子句分別進(jìn)行歸結(jié)，若最后能得到空子句，則推出結(jié)論是成立的結(jié)論。但是要知道最后是根據(jù)哪條規(guī)則推出結(jié)論，才能確定投資方式x的值，所以要跟蹤歸結(jié)時(shí)變量替換的過程。這也就是從歸結(jié)反演提取答案的過程。要求根據(jù)上面的描述，編制一個(gè)程序，首先讓用戶輸入年收入數(shù)、是否穩(wěn)定，所供養(yǎng)的人數(shù)以及已有的儲蓄。然后給出投資方式的建議。實(shí)驗(yàn)八學(xué)習(xí)Agent實(shí)驗(yàn)實(shí)驗(yàn)?zāi)康呐c要求目的：掌握遺傳算法的基本原理，學(xué)習(xí)根據(jù)實(shí)際問題確定染色體編碼方法及設(shè)計(jì)適應(yīng)度函數(shù)，從而實(shí)現(xiàn)用遺傳算法求解優(yōu)化問題。要求：編寫用遺傳算法求解背包問題的程序?；局R遺傳算法(GeneticAlgorithm)是一種優(yōu)化算法。它是人們從生物的有性繁殖、遺傳變異和按優(yōu)勝劣汰法則進(jìn)化的自然現(xiàn)象中得到啟發(fā)，而設(shè)計(jì)出來的，因此稱為遺傳算法。我們知道，自然選擇的原則是優(yōu)勝劣汰、適者生存，有性繁殖則可以使基因不斷地進(jìn)行混合和重組。遺傳算法以生物細(xì)胞中的染色體作為生物個(gè)體，并設(shè)置了三個(gè)作用于染色體的操作：復(fù)制、交叉（亦稱交換或雜交）和變異（亦稱突變），它們被稱為遺傳操作或遺傳算子。此外，還要定義染色體的適應(yīng)度，即對環(huán)境的適應(yīng)程度。適應(yīng)度也就是表征一個(gè)染色體優(yōu)劣的測度。在此基礎(chǔ)上，遺傳算法的步驟就是對一個(gè)染色體集合中的染色體，重復(fù)做：①三種遺傳操作；②計(jì)算適應(yīng)度；③按適應(yīng)度大小進(jìn)行取舍，直至達(dá)到預(yù)定目標(biāo)。三種遺傳操作：1、復(fù)制：產(chǎn)生一個(gè)與字符串S相同的字符串；2、交叉：取字符串S1和S2，互相交換其中的某些字符，得到兩個(gè)新的字符串S’1和S’2；3、變異：改變字符串S中的某一個(gè)字符，得到一個(gè)新的字符串S′。例如，設(shè)字符串S1=10101001，S2=10010011，那么，(1)對S1進(jìn)行復(fù)制操作，得新串10101001；(2)對S1和S2進(jìn)行交叉操作，如交換兩個(gè)字符串的后4位，則得S’1=10100011，S’2=10011001；(3)對S1進(jìn)行變異操作，如把第三位的1改為0，則得新串10001001?；具z傳算法：1、隨機(jī)產(chǎn)生一個(gè)個(gè)體集合A={S1,S2,:,Sn}，將A作為一個(gè)初始種群，并在其上定義一個(gè)適應(yīng)度函數(shù)f(x)；2、計(jì)算A中每個(gè)個(gè)體的適應(yīng)度函數(shù)值；3、若滿足停止條件，取A中適應(yīng)度最大的個(gè)體作為所求結(jié)果，算法結(jié)束。4、以一定的概率選擇A中若干適應(yīng)度高的個(gè)體S1,S2,…,Sk(k<n)，進(jìn)行復(fù)制操作，并刪去A中適應(yīng)度低的個(gè)體，這樣得到集合A’(注：被復(fù)制個(gè)體和復(fù)制個(gè)體同時(shí)存在于A’中)；5、以一定的概率選取A’中的若干個(gè)體對，進(jìn)行交叉操作，得到集合A″；6、以一定的概率選取A″中的若干個(gè)體，進(jìn)行變異操作，得到集合Anew；7、將Anew作為新一代種群，用Anew代替A，轉(zhuǎn)步2。遺傳算法利用簡單的編碼技術(shù)和繁殖機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象，解決困難的問題。遺傳算法的適應(yīng)性強(qiáng)，除需知適應(yīng)度函數(shù)外，幾乎不需要其它的先驗(yàn)知識。遺傳算法長于全局搜索，它不受搜索空間的限制性假設(shè)的約束，不要求連續(xù)性，能以很大的概率從離散的、多極值的、含有噪聲的高維問題中找到全局最優(yōu)解。實(shí)驗(yàn)內(nèi)容與進(jìn)行方式編制用遺傳算法求解下面的背包問題的程序：有十件物品，其重量與價(jià)值如下