人工智能_實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)一：知識表示方法一、實(shí)驗(yàn)?zāi)康臓顟B(tài)空間表示法是人工智能領(lǐng)域最基本的知識表示方法之一， 也是進(jìn)一步學(xué)習(xí)狀態(tài)空間搜索策略的基礎(chǔ)， 本實(shí)驗(yàn)通過牧師與野人渡河的問題， 強(qiáng)化學(xué)生對知識表示的了解和應(yīng)用，為人工智能后續(xù)環(huán)節(jié)的課程奠定基礎(chǔ)。二、問題描述有 n 個(gè)牧師和 n 個(gè)野人準(zhǔn)備渡河， 但只有一條能容納 c 個(gè)人的小船， 為了防止野人侵犯牧師，要求無論在何處，牧師的人數(shù)不得少于野人的人數(shù) (除非牧師人數(shù)為 0)，且假定野人與牧師都會劃船， 試設(shè)計(jì)一個(gè)算法， 確定他們能否渡過河去，若能，則給出小船來回次數(shù)最少的最佳方案。三、基本要求輸入：牧師人數(shù) (即野人人數(shù) )： n；小船一次最多載人量： c。輸出：

2、若問題無解，則顯示 Failed，否則，顯示 Successed輸出一組最佳方案。用三元組 (X1 , X2, X3 )表示渡河過程中的狀態(tài)。并用箭頭連接相鄰狀態(tài)以表示遷移過程：初始狀態(tài) ->中間狀態(tài) ->目標(biāo)狀態(tài)。例：當(dāng)輸入 n=2，c=2 時(shí)，輸出： 221->110->211->010->021->000其中： X 1 表示起始岸上的牧師人數(shù)； X2 表示起始岸上的野人人數(shù)； X 3 表示小船現(xiàn)在位置 (1 表示起始岸， 0 表示目的岸 )。要求：寫出算法的設(shè)計(jì)思想和源程序，并以圖形用戶界面實(shí)現(xiàn)人機(jī)交互，進(jìn)行輸入和輸出結(jié)果，如：Please in

3、put n: 2Please input c: 2Successed or Failed?: SuccessedOptimal Procedure: 221->110->211->010->021->000四、實(shí)驗(yàn)組織運(yùn)行要求本實(shí)驗(yàn)采用集中授課形式，每個(gè)同學(xué)獨(dú)立完成上述實(shí)驗(yàn)要求。五、實(shí)驗(yàn)條件每人一臺計(jì)算機(jī)獨(dú)立完成實(shí)驗(yàn)。六、實(shí)驗(yàn)代碼Main.cpp#include<iostream>#include"RiverCrossing.h"usingnamespace std;/ 主函數(shù)voidmain()RiverCrossing:Show

4、Info();intn, c;cout<< "Please input n: "cin>>n;cout<< "Please input c: "cin>>c;RiverCrossingriverCrossing(n, c);riverCrossing.solve();system("pause");RiverCrossing.h#pragma once#include<list>/ 船classBoatpublic:staticintc;intpastor;/ 牧師intsa

5、vage;/ 野人Boat( intpastor,intsavage);/ 河岸狀態(tài)classStatepublic:staticintn;intiPastor;/ 牧師數(shù)量intiSavage;/ 野人數(shù)量intiBoatAtSide;/ 船所在河岸State*pPrevious;/ 前一個(gè)狀態(tài)State(intpastor,intsavage,intboatAtSide);intgetTotalCount();/ 獲得此岸總?cè)藬?shù)bool check();/ 檢查人數(shù)是否符合實(shí)際bool isSafe();/ 檢查是否安全Stateoperator + (Boat&boat);Sta

6、teoperator - (Boat&boat);booloperator = (State&state);/ 過河問題classRiverCrossingprivate:std:list<State *> openList, closeList;StateendState;bool move( State*nowState,Boat *boat);/ 進(jìn)行一次決策State * findInList(std:list<State *> &listToCheck,State&state);/ 檢查某狀態(tài)節(jié)點(diǎn)是否在列表中void print

7、(State *endState);public:staticvoidShowInfo();RiverCrossing(intn,intc);bool solve();/ 求解問題/ 打印結(jié)果;RiverCrossing.cpp#include"RiverCrossing.h"#include<iostream>#include<stack>#include<algorithm>usingnamespace std;/ 類靜態(tài)變量定義intState :n = 0;intBoat :c = 0;/*=Methods for class &

8、quot;Boat"=*/Boat :Boat(intpastor ,intsavage )this ->pastor =pastor ;this ->savage =savage ;/*=Methods for class "State"=*/ 構(gòu)造函數(shù)State :State(intpastor ,intsavage ,intboatAtSide)this ->iPastor =pastor ;this ->iSavage =savage ;this ->iBoatAtSide =boatAtSide;this ->pPre

9、vious =NULL;/ 獲取此岸總?cè)藬?shù)intState :getTotalCount()returniPastor + iSavage;/ 檢查人數(shù)是否在 0到 n之間boolState :check()return(iPastor >=0 && iPastor <= n && iSavage >= 0 && iSavage <=n);/ 按照規(guī)則檢查牧師得否安全boolState :isSafe()/ 此岸的安全： x1 = 0 | x1 >= x2/ 彼岸的安全： (n-x1) = 0 | (n-x1) &g

10、t;= (n-x2)/ 將上述條件聯(lián)立后得到如下條件return(iPastor = 0 | iPastor = n | iPastor = iSavage);/ 重載 +符號，表示船開到此岸StateState :operator+(Boat & boat )Stateret(iPastor +ret.pPrevious =returnret;boat .pastor, iSavage + this ;boat .savage, iBoatAtSide + 1);/ 重載 - 符號，表示船從此岸開走StateState :operator-(Boat & boat )Stat

11、eret(iPastor -ret.pPrevious =returnret;boat .pastor, iSavage - this ;boat .savage, iBoatAtSide - 1);/ 重載 =符號，比較兩個(gè)節(jié)點(diǎn)是否是相同的狀態(tài)boolState :operator=(State& state )return( this ->iPastor =state .iPastor &&this ->iSavage =state .iSavage &&this->iBoatAtSide =state.iBoatAtSide);/

12、*=Methods for class "RiverCrossing"=*/ 顯示信息voidRiverCrossing:ShowInfo()cout<< "*"cout<< "牧師與野人過河問題求解cout<< "by 1040501211陳嘉生cout<< "*"""<<endl;<<endl;<<endl;<<endl;/ 構(gòu)造函數(shù)RiverCrossing:RiverCrossing(intn

13、,intc):endState(0, 0, 0)State :n =Boat :c =n;c ;/ 解決問題boolRiverCrossing:solve()openList.push_back(new State ( State :n,State :n, 1);while (!openList.empty() / 獲取一個(gè)狀態(tài)為當(dāng)前狀態(tài)State*nowState = openList.front();openList.pop_front();closeList.push_back(nowState);/ 從當(dāng)前狀態(tài)開始決策if(nowState->iBoatAtSide = 1) /

14、 船在此岸/ 過河的人越多越好，且野人優(yōu)先intcount = nowState->getTotalCount();count = (Boat :c >= count ? count :Boat :c);for( intcapticy = count; capticy >= 1; -capticy) for ( inti = 0; i <= capticy; +i) Boat boat(i, capticy - i);if(move(nowState, &boat)returntrue ;elseif(nowState->iBoatAtSide = 0)

15、/ 船在彼岸/ 把船開回來的人要最少，且牧師優(yōu)先for( intcapticy = 1; capticy <=Boat :c; +capticy) for ( inti = 0; i <= capticy; +i) Boat boat(capticy - i, i);if(move(nowState, &boat)returntrue ;print(NULL);returnfalse ;/ 實(shí)施一步?jīng)Q策，將得到的新狀態(tài)添加到列表，返回是否達(dá)到目標(biāo)狀態(tài)boolRiverCrossing:move( State* nowState ,Boat * boat )/ 獲得下一個(gè)狀態(tài)

16、State*destState;if( nowState ->iBoatAtSide = 1) destState =new State (* nowStateelseif( nowState ->iBoatAtSide = 0) destState =new State (* nowState- *boat ); / 船離開此岸+ * boat ); / 船開到此岸if(destState->check() / 檢查人數(shù)if(*destState = endState) / 是否達(dá)到目標(biāo)狀態(tài)closeList.push_back(destState);print(destS

17、tate);returntrue ; / 找到結(jié)果elseif(destState->isSafe() / 檢查是否安全if(!findInList(openList, *destState) && !findInList(closeList,*destState) / 檢查是否在表中/ 添加沒出現(xiàn)過的狀態(tài)節(jié)點(diǎn)到open表openList.push_back(destState);returnfalse;deletedestState;returnfalse ;/ 檢查給定狀態(tài)是否存在于列表中State * RiverCrossing:findInList(list<

18、;State *> & listToCheck,State& state)for( list<State *>:iteratorite =listToCheck.begin(); ite !=listToCheck.end();+ite) if(*ite = returnstate *ite;)returnNULL;/ 根據(jù)達(dá)到的目標(biāo)狀態(tài)，回溯打印出求解過程voidRiverCrossing:print(State * endState )cout<< "="<<endl;if(!endState ) cout<

19、;< "Search failed!"<<endl;else cout<< "Search successed!"<<endl;cout<< "Optimal Procedure: "<<endl;State*pState =endState ;stack<State *> st;/ 用棧將鏈表逆序，以便輸出while(pState) st.push(pState);pState = pState->pPrevious;intcount = 0;whi

20、le(!st.empty() pState = st.top();st.pop();cout<<pState->iPastor<<"," <<pState->iSavage<<"," <<pState->iBoatAtSide;ifif(st.size() > 0)cout<< " -> "(+count % 5 = 0)cout<<endl;/ 每五個(gè)步驟換行cout<<endl;cout<< &

21、quot;Total move: "<<count - 1<<endl;cout<< "="<<endl;七、實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)二：九宮重排一、實(shí)驗(yàn)?zāi)康腁* 算法是人工智能領(lǐng)域最重要的啟發(fā)式搜索算法之一，本實(shí)驗(yàn)通過九宮重排問題，強(qiáng)化學(xué)生對 A* 算法的理解與應(yīng)用，為人工智能后續(xù)環(huán)節(jié)的課程奠定基礎(chǔ)。二、問題描述給定九宮格的初始狀態(tài)， 要求在有限步的操作內(nèi)， 使其轉(zhuǎn)化為目標(biāo)狀態(tài)， 且所得到的解是代價(jià)最小解 (即移動的步數(shù)最少 )。如：三、基本要求輸入：九宮格的初始狀態(tài)和目標(biāo)狀態(tài)輸出：重排的過程，即途徑的狀態(tài)四、實(shí)驗(yàn)組織運(yùn)行要求

22、本實(shí)驗(yàn)采用集中授課形式，每個(gè)同學(xué)獨(dú)立完成上述實(shí)驗(yàn)要求。五、實(shí)驗(yàn)條件每人一臺計(jì)算機(jī)獨(dú)立完成實(shí)驗(yàn)。六、實(shí)驗(yàn)代碼Main.cpp#include<iostream>#include"NineGrid.h"usingnamespace std;/ 主函數(shù)voidmain()NineGrid:ShowInfo();stringstart, end;cout<< "Please input the initial state: (ex:134706582)"<<endl;cin>>start;cout<<

23、"Please input the target state: (ex:123804765)"<<endl;cin>>end;NineGridnineGrid(start, end);nineGrid.solve();system("pause");NineGrid.h#pragmaonce#include<vector>#include<string>#include<time.h>usingnamespace std;#define#defineSPACE '0'AT(s,

24、x, y) (s)(x) * 3 + (y)enum Move UP = 0,DOWN= 1,LEFT = 2,RIGHT = 3;/ 九宮格狀態(tài)public:staticState*pEndState;/ 指向目標(biāo)狀態(tài)，用于評價(jià)h的值stringintx, y;grid;/ 用字符串保存當(dāng)前棋盤狀態(tài)/ 空格所在位置intmoves;/ 到此狀態(tài)的移動次數(shù)intvalue;/ 價(jià)值State*pPrevious;/ 前一個(gè)狀態(tài)State(string&grid,State*pPrevious =intgetReversedCount();/ 獲取逆序數(shù)voidevaluate();/

25、評價(jià)函數(shù)boolcheck(Move move);/ 檢查是否可以移動NULL);StatetakeMove(Move move);/ 實(shí)施移動，生成子狀態(tài)/ 重載 =運(yùn)算符，判斷兩個(gè)狀態(tài)是否相等inlinebooloperator = (State& state) returngrid =state.grid; ;/ 九宮重排問題classNineGridprivate:vector<State*> openList, closeList;StatestartState, endState;clock_tstartTime;boolcompareReversed();/

26、比較逆序數(shù)奇偶性是否相同booltakeMove(State*nowState,Move move);/ 進(jìn)行一次決策State* findInList(vector< State*> &listToCheck,State&State);/ 檢查某狀態(tài)節(jié)點(diǎn)是否在列表中voidprint(State*endState);/打印結(jié)果/ 用于排序staticboolgreater_than(public:staticvoidShowInfo();constState/ 顯示信息*state1,constState*state2);NineGrid(string&s

27、tart,string&dest);boolsolve();/求解問題;NineGrid.cpp#include"NineGrid.h"#include<iostream>#include<stack>#include<algorithm>usingnamespace std;State*State:pEndState =NULL;/*=Methods for class "State"=*/ 構(gòu)造函數(shù)State:State(string& grid,State* pPrevious)this->

28、grid =grid;this->pPrevious =pPrevious;if( this->pPrevious)this->moves =pPrevious->moves + 1;elsethis->moves = 0;this->value = 0;evaluate();for( inti = 0; i < 3; +i) for ( intj = 0; j < 3; +j) if( AT( grid, i, j) =x = i;y = j;return;SPACE) boolState:check(Move move)switch( mov

29、e) caseUP:if(x - 1 < 0)returnfalse;break ;caseDOWN:if(x + 1 >= 3)returnfalse;break ;caseLEFT:if(y - 1 < 0)returnfalse;break ;caseRIGHT:if(y + 1 >= 3)returnfalse;break ;returntrue;StateState:takeMove(Move move)intdestX, destY;switch( move) caseUP:destX = x - 1;destY = y;break ;caseDOWN:de

30、stX = x + 1;destY = y;break ;caseLEFT:destX = x;destY = y - 1;break ;caseRIGHT:destX = x;destY = y + 1;break ;stringtGrid = grid;chart =AT(tGrid, destX, destY);AT(tGrid, destX, destY) =AT(tGrid, x, y) = t;returnState(tGrid,this);AT(tGrid, x, y);voidState:evaluate()if(!pEndState)return;intg = moves,

31、h = 0;for( inti = 0; i < 3; +i) for( intj = 0; j < 3; +j) /if (AT(grid, i, j) != AT(pEndState->grid, i, j)/+h;if( AT(grid, i, j) =continue;SPACE)for( intii = 0; ii < 3; +ii) for( intjj = 0; jj < 3; +jj) if( AT(grid, i, j) =h += abs(i - ii) + abs(j - jj);AT(pEndState->grid, ii, jj)

32、this->value = g + h;/ 求該狀態(tài)的逆序數(shù)/ 逆序數(shù)定義為：/ 不計(jì)空格，將棋盤按順序排列，/對于 gridi，存在 j<i，使 gridj>gridi，即為逆序。/ 所有棋子的逆序總數(shù)為逆序數(shù)。intState:getReversedCount()intcount = 0;for( inti = 0; i < 9; +i) if (gridi =SPACE)continue;for( intj = 0; j < i; +j) if(gridj =SPACE)continue;if(gridi > gridj)+count;returnco

33、unt;/*=Methods for class "NineGrid"=*/ 顯示信息voidNineGrid:ShowInfo()cout<< "*"cout<< "九宮重排問題求解cout<< "by 1040501211陳嘉生cout<< "*"""<<endl;<<endl;<<endl;<<endl;/ 構(gòu)造函數(shù)NineGrid:NineGrid(: startState(string &a

34、mp; start start ), endState(, string dest )& dest )State:pEndState = &endState;endState.evaluate();/ 當(dāng)初始狀態(tài)和目標(biāo)狀態(tài)的逆序數(shù)的奇偶性相同時(shí)，問題才有解boolNineGrid:compareReversed()returnstartState.getReversedCount() % 2 = endState.getReversedCount() %2;/ 解決問題boolNineGrid:solve()cout<< "="<<e

35、ndl;if(!compareReversed() cout<< " 初始狀態(tài)和目標(biāo)狀態(tài)的逆序數(shù)的奇偶性不同，問題無解！" <<endl;elsecout<< "Start searching."<<endl;startTime = clock();/ 取得開始搜索的時(shí)間openList.push_back(new State(startState);while(!openList.empty() / 獲取一個(gè)狀態(tài)為當(dāng)前狀態(tài)State*nowState = openList.back();openList.

36、pop_back();closeList.push_back(nowState);/ 從當(dāng)前狀態(tài)開始決策for( inti = 0; i < 4; +i) Move move = (Move)i;if(nowState->check(move) if(takeMove(nowState, move)returntrue;print(NULL);returnfalse;/ 實(shí)施一步?jīng)Q策，將得到的新狀態(tài)添加到列表，返回是否達(dá)到目標(biāo)狀態(tài)boolNineGrid:takeMove(State* nowState,Move move)/ 獲得下一個(gè)狀態(tài)State*destState =new

37、 State( nowState->takeMove(move);if(*destState = endState) / 是否達(dá)到目標(biāo)狀態(tài)closeList.push_back(destState);print(destState);returntrue; / 找到結(jié)果elseif(!findInList(openList, *destState) && !findInList(closeList,*destState) / 添加沒出現(xiàn)過的狀態(tài)節(jié)點(diǎn)到open 表openList.push_back(destState);sort(openList.begin(), ope

38、nList.end(), greater_than);returnfalse;deletereturndestState;false;/ 檢查給定狀態(tài)是否存在于列表中State*NineGrid:findInList(vector<State*> & listToCheck,State& state)for( vector<State*>:iteratorite =listToCheck.begin(); ite !=listToCheck.end(); +ite) if(*ite =state)return*ite;returnNULL;/ 根據(jù)達(dá)到的

39、目標(biāo)狀態(tài)，回溯打印出求解過程voidNineGrid:print(State* endState)if(!endState) cout<< "Search failed!"elsefloatelapsed= ( float<<endl;)clock()- startTime)/CLOCKS_PER_SEC* 1000; /取得搜索花費(fèi)時(shí)間cout<< "Search successed!"cout<< "Elapsed time: "<<endl;<<elapse

40、d<<"(ms)"<<endl;cout<< "Total move: "<<endState->moves<<endl;cout<< "Optimal Procedure: "<<endl;State*pState =endState;stack<State*> st;/ 用棧將鏈表逆序，以便輸出while(pState) st.push(pState);pState = pState->pPrevious;/3 行一起輸出，

41、更直觀一點(diǎn)stringout3;intcount = 0;while(!st.empty() pState = st.top();st.pop();for( inti = 0; i < 3; +i) for ( intj = 0; j < 3; +j) if( AT(pState->grid, i, j) =outi +=' 'SPACE)elseouti +=AT(pState->grid, i, j);outi +=' 'if(st.size() != 0) out0 +=out1 +=out2 +="""

42、;-> """if(+count % 5 = 0 | st.size() = 0) for( inti = 0; i < 3; +i) cout<<outi<<endl;outi ="" ;cout<<endl;cout<< "="<<endl;/ 定義的排列函數(shù)boolNineGrid:greater_than(constState* state1,constState* state2)returnstate1->value >state2

43、->value;七、實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)三：專家系統(tǒng)一、實(shí)驗(yàn)?zāi)康膶＜蚁到y(tǒng)是人工智能的重要研究內(nèi)容和組成部分之一， 本實(shí)驗(yàn)通過設(shè)計(jì)一個(gè)簡單的專家系統(tǒng)， 加深學(xué)生對專家系統(tǒng)的組成結(jié)構(gòu)和構(gòu)造原理的理解， 并能轉(zhuǎn)化為具體的應(yīng)用。二問題描述設(shè)計(jì)一個(gè)簡單的專家系統(tǒng)，可根據(jù)屬性的輸入值自動識別事物的具體類別，內(nèi)容自擬。如一個(gè)動物專家系統(tǒng)可由以下 11 個(gè)屬性組成，根據(jù)屬性的對應(yīng)值 (Y 或 N) ，可判斷動物的具體種類，運(yùn)行結(jié)果如下圖所示：三、實(shí)驗(yàn)組織運(yùn)行要求本實(shí)驗(yàn)采用開放授課形式，每個(gè)同學(xué)獨(dú)立完成上述實(shí)驗(yàn)要求。四、實(shí)驗(yàn)條件每人一臺計(jì)算機(jī)獨(dú)立完成實(shí)驗(yàn)。五、實(shí)驗(yàn)代碼Main.cpp#include"Expert.h"#include<iostream>usingnamespace std;voidmai