人工智能實驗知識表示法

1、<p>　　實驗二 知識表示方法</p><p><b>　　1．實驗?zāi)康?lt;/b></p><p>　?。?）了解知識表示相關(guān)技術(shù)；</p><p>　?。?）掌握問題規(guī)約法或者狀態(tài)空間法的分析方法。</p><p>　　2．實驗內(nèi)容（2個實驗內(nèi)容可以選擇1個實現(xiàn)）</p><p>　

2、　（1）梵塔問題實驗。熟悉和掌握問題規(guī)約法的原理、實質(zhì)和規(guī)約過程；理解規(guī)約圖的表示方法；</p><p>　?。?）狀態(tài)空間法實驗。從前有一條河，河的左岸有m個傳教士、m個野人和一艘最多可乘n人的小船。約定左岸，右岸和船上或者沒有傳教士，或者野人數(shù)量少于傳教士，否則野人會把傳教士吃掉。搜索一條可使所有的野人和傳教士安全渡到右岸的方案。</p><p><b>　　3．實驗報告要求

3、</b></p><p>　　（1）簡述實驗原理及方法，并請給出程序設(shè)計流程圖。</p><p>　　本次試驗選擇傳教士過河問題，以狀態(tài)空間法實現(xiàn)。</p><p><b>　　解答步驟如下：</b></p><p>　　設(shè)置狀態(tài)變量并確定值域</p><p>　　M為傳教士人數(shù)，C

4、為野人人數(shù)，B為船數(shù)，要求M>=C且M+C <= 3，L表示左岸，R表示右岸。</p><p>　　初始狀態(tài)目標狀態(tài)</p><p>　　LRLR</p><p>　　M30M03</p><p>　　C30C03</p><p>

5、　　B10B01</p><p>　　確定狀態(tài)組，分別列出初始狀態(tài)集和目標狀態(tài)集</p><p>　　用三元組來表示：（ML , CL , BL）（均為左岸狀態(tài)）</p><p>　　其中,BL ∈{ 0 , 1}</p><p>　?。?3 , 3 , 1) ： (0 , 0 , 0)</p>

6、<p>　　初始狀態(tài)表示全部成員在河的的左岸；</p><p>　　目標狀態(tài)表示全部成員從河的左岸全部渡河完畢。</p><p><b>　　定義并確定規(guī)則集合</b></p><p>　　仍然以河的左岸為基點來考慮，把船從左岸劃向右岸定義為Pij操作。其中，第一下標i表示船載的傳教士數(shù)，第二下標j表示船載的食人者數(shù)；同理，從右岸

7、將船劃回左岸稱之為Qij操作，下標的定義同前。則共有10種操作，操作集為</p><p>　　F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}</p><p>　　P10if ( ML ,CL , BL=1 ) then ( ML–1 , CL , BL –1 ) </p><p>　　P01if ( ML ,CL ,

8、BL=1 ) then ( ML , CL–1 , BL –1 ) </p><p>　　P11if ( ML ,CL , BL=1 ) then ( ML–1 , CL–1 , BL –1 ) </p><p>　　P20if ( ML ,CL , BL=1 ) then ( ML–2 , CL , BL –1 ) </p><p>　　P02i

9、f ( ML ,CL , BL=1 ) then ( ML , CL–2 , BL –1 ) </p><p>　　Q10 if ( ML ,CL , BL=0 ) then ( ML+1 , CL , BL+1 ) </p><p>　　Q01if ( ML ,CL , BL=0 ) then ( ML , CL+1 , BL +1 ) </p><p

10、>　　Q11if ( ML ,CL , BL=0 ) then ( ML+1 , CL +1, BL +1 ) </p><p>　　Q20if ( ML ,CL , BL=0 ) then ( ML+2 , CL +2, BL +1 ) </p><p>　　Q02if ( ML ,CL , BL=0 ) then ( ML , CL +2, BL +1 ) &l

11、t;/p><p>　　當(dāng)狀態(tài)數(shù)量不是很大時，畫出合理的狀態(tài)空間圖</p><p><b>　　圖1 狀態(tài)空間圖</b></p><p>　　箭頭旁邊所標的數(shù)字表示了Ｐ或Ｑ操作的下標，即分別表示船載的傳教士數(shù)和食人者數(shù)。</p><p>　　接下來進行樹的遍歷，根據(jù)規(guī)則由根（初始狀態(tài)）擴展出整顆樹，檢測每個結(jié)點的“可擴展標記”

12、，為“-1”的即目標結(jié)點。由目標結(jié)點上溯出路徑。</p><p><b>　?。?）源程序清單：</b></p><p><b>　　//關(guān)鍵代碼</b></p><p>　　#include <iostream></p><p>　　#include <vector><

13、;/p><p>　　#include <list></p><p>　　using namespace std;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　int m;//表示傳教士</p><p>

14、;　　int c;// 表示野人</p><p>　　int b;//船狀態(tài)</p><p><b>　　}MCNode;</b></p><p>　　list<MCNode> fringe;//相當(dāng)于隊列</p><p>　　vector<MCNode> closed;//closed表<

15、/p><p>　　//判斷是否是目標結(jié)點</p><p>　　bool IsGoal(MCNode tNode)</p><p><b>　　{</b></p><p>　　if(tNode.m==0&&tNode.c==0&&tNode.b==0)</p><p>　

16、　return true;</p><p><b>　　else</b></p><p>　　return false;</p><p><b>　　}</b></p><p>　　//判斷是否是合法狀態(tài)</p><p>　　bool IsLegal(MCNode tNode

17、)</p><p><b>　　{</b></p><p>　　if(tNode.m>=0&&tNode.m<=3&&tNode.c>=0&&tNode.c<=3)</p><p><b>　　{</b></p><p>　　i

18、f((tNode.m==tNode.c)||(tNode.m==3)||(tNode.m==0))</p><p>　　return true;</p><p><b>　　else</b></p><p>　　return false;</p><p><b>　　}</b></p>

19、<p><b>　　else</b></p><p>　　return false;</p><p><b>　　}</b></p><p>　　bool operator==(MCNode m1,MCNode m2) //重載運算符，判斷兩結(jié)構(gòu)體是否相等</p><p><b&g

20、t;　　{</b></p><p>　　if(m1.m==m2.m&&m1.c==m2.c&&m1.b==m2.b)</p><p>　　return true;</p><p><b>　　else</b></p><p>　　return false;</p>

21、<p><b>　　}</b></p><p>　　bool IsClosed(MCNode tNode) //判斷是否已在closed表中</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for(i=0

22、;i!=closed.size();i++)</p><p><b>　　{</b></p><p>　　if(tNode==closed[i])</p><p>　　return true;</p><p><b>　　}</b></p><p>　　if(i==close

23、d.size())</p><p>　　return false;</p><p><b>　　}</b></p><p>　　void ExpandNode(MCNode tNode,int b,list<MCNode> &fringe)</p><p><b>　　{</b>

24、</p><p>　　MCNode node[5];//應(yīng)用5條規(guī)則集生成新結(jié)點</p><p><b>　　if(b==1)</b></p><p><b>　　{</b></p><p>　　for(int i=0;i<5;i++)</p><p>　　node[i

25、].b=0;</p><p>　　node[0].m=tNode.m-1;</p><p>　　node[0].c=tNode.c;</p><p>　　node[1].m=tNode.m;</p><p>　　node[1].c=tNode.c-1;</p><p>　　node[2].m=tNode.m-1;<

26、;/p><p>　　node[2].c=tNode.c-1;</p><p>　　node[3].m=tNode.m-2;</p><p>　　node[3].c=tNode.c;</p><p>　　node[4].m=tNode.m;</p><p>　　node[4].c=tNode.c-2;</p>

27、<p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　for(int i=0;i<5;i++)</p><p>　　node[i].b=1;</p><p&g

28、t;　　node[0].m=tNode.m+1;</p><p>　　node[0].c=tNode.c;</p><p>　　node[1].m=tNode.m;</p><p>　　node[1].c=tNode.c+1;</p><p>　　node[2].m=tNode.m+1;</p><p>　　node[

29、2].c=tNode.c+1;</p><p>　　node[3].m=tNode.m+2;</p><p>　　node[3].c=tNode.c;</p><p>　　node[4].m=tNode.m;</p><p>　　node[4].c=tNode.c+2;</p><p><b>　　}<

30、/b></p><p>　　for(int i=0;i<5;i++)</p><p>　　if(IsLegal(node[i])&&!IsClosed(node[i]))</p><p>　　fringe.push_front(node[i]);//隊列后進先出，深度優(yōu)先搜索，最后得到一條最小解序列</p><p>

31、;　　//fringe.push_back(node[i]);//隊列后進后出，廣度優(yōu)先搜索，最后得到最小解序列狀態(tài)空間圖</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　MCNode InitNo

32、de,unode;</p><p>　　InitNode.m=3;</p><p>　　InitNode.c=3;</p><p>　　InitNode.b=1;</p><p>　　fringe.push_back(InitNode);//將初始狀態(tài)空間加入到隊列</p><p>　　while(!fringe.em

33、pty())</p><p><b>　　{</b></p><p>　　unode=fringe.front();</p><p>　　fringe.pop_front();</p><p>　　if(IsGoal(unode))</p><p><b>　　{</b>&l

34、t;/p><p>　　closed.push_back(unode);</p><p>　　for(int i=0;i!=closed.size();i++)</p><p>　　cout<<closed[i].m<<","<<closed[i].c<<","<<clos

35、ed[i].b<<endl;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　if(!IsClosed(unode))</p><p><b>　　{</b></p><p>　　

36、closed.push_back(unode);</p><p>　　ExpandNode(unode,unode.b,fringe);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p>