人工智能試驗(yàn)知識(shí)表示法

1、實(shí)驗(yàn)二知識(shí)表示方法1 .實(shí)驗(yàn)?zāi)康?1)了解知識(shí)表示相關(guān)技術(shù)；(2)掌握問(wèn)題規(guī)約法或者狀態(tài)空間法的分析方法。2 .實(shí)驗(yàn)內(nèi)容(2個(gè)實(shí)驗(yàn)內(nèi)容可以選擇1個(gè)實(shí)現(xiàn))(1)梵塔問(wèn)題實(shí)驗(yàn)。熟悉和掌握問(wèn)題規(guī)約法的原理、實(shí)質(zhì)和規(guī)約過(guò)程；理解規(guī)約圖的表示方法；(2)狀態(tài)空間法實(shí)驗(yàn)。從前有一條河，河的左岸有m個(gè)傳教士、m個(gè)野人和一艘最多可乘n人的小船。約定左岸，右岸和船上或者沒有傳教士，或者野人數(shù)量少于傳教士，否則野人會(huì)把傳教士吃掉。搜索一條可使所有的野人和傳教士安全渡到右岸的方案。3.實(shí)驗(yàn)報(bào)告要求(1)簡(jiǎn)述實(shí)驗(yàn)原理及方法，并請(qǐng)給出程序設(shè)計(jì)流程圖。本次試驗(yàn)選擇傳教士過(guò)河問(wèn)題，以狀態(tài)空間法實(shí)現(xiàn)。解答步驟如下：(1)設(shè)置

2、狀態(tài)變量并確定值域M為傳教士人數(shù)，C為野人人數(shù)，B為船數(shù)，要求M=C1M+C=3,L表示左岸，R表示右岸。目標(biāo)狀態(tài)初始狀態(tài)(2)確定狀態(tài)組，分別列出初始狀態(tài)集和目標(biāo)狀態(tài)集用三元組來(lái)表示Sf：(ML,CL,BL)(均為左岸狀態(tài))其中0WML3,0CL3,BL0,1初始狀態(tài)表示全部成員在河的的左岸；目標(biāo)狀態(tài)表示全部成員從河的左岸全部渡河完畢。(3)定義并確定規(guī)則集合仍然以河的左岸為基點(diǎn)來(lái)考慮，把船從左岸劃向右岸定義為Pij操作。其中，第一下標(biāo)i表示船載的傳教士數(shù)，第二下標(biāo)j表示船載的食人者數(shù)；同理，從右岸將船劃回左岸稱之為Qij操作，下標(biāo)的定義同前。則共有10種操作，操作集為F=P01,P10,P

3、11,P02,P20,Q01,Q10,Q11,Q02,Q20P10if(ML,CL,BL=1)then(ML-1,CL,BL-1)P01if(ML,CL,BL=1)then(ML,CL-1,BL-1)P11if(ML,CL,BL=1)then(ML-1,CL-1,BL-1)P20if(ML,CL,BL=1)then(ML-2,CL,BL-1)P02if(ML,CL,BL=1)then(ML,CL-2,BL-1)Q0if(ML,CL,BL=0)then(ML+1,CL,BL+1)Q1if(ML,CL,BL=0)then(ML,CL+1,BL+1)Q1if(ML,CL,BL=0)then(ML+1

4、,CL+1,BL+1)Q0if(ML,CL,BL=0)then(ML+2,CL+2,BL+1)Q2if(ML,CL,BL=0)then(ML,CL+2,BL+1)(4)當(dāng)狀態(tài)數(shù)量不是很大時(shí)，畫出合理的狀態(tài)空間圖Jf=2Q0i1)*f=4Pza(L30)(231)CO,2，U)lrf=3Qoi01)圖1狀態(tài)空間圖箭頭旁邊所標(biāo)的數(shù)字表示了P或Q操作的下標(biāo),即分別表示船載的傳教士數(shù)和食人者數(shù)。接下來(lái)進(jìn)行樹的遍歷，根據(jù)規(guī)則由根（初始狀態(tài)）擴(kuò)展出整顆樹，檢測(cè)每個(gè)結(jié)點(diǎn)的“可擴(kuò)展標(biāo)記”，為“-1”的即目標(biāo)結(jié)點(diǎn)。由目標(biāo)結(jié)點(diǎn)上溯出路徑。(2)源程序清單：/關(guān)鍵代碼#include#include#include

5、usingnamespacestd;typedefstructintm;/表示傳教士intc;/表示野人intb;/船狀態(tài)MCNode;listfringe;/相當(dāng)于隊(duì)列vectorclosed;/closed表/判斷是否是目標(biāo)結(jié)點(diǎn)boolIsGoal(MCNodetNode)if(tNode.m=0&tNode.c=0&tNode.b=0)returntrue;elsereturnfalse;/判斷是否是合法狀態(tài)boolIsLegal(MCNodetNode)if(tNode.m=0&tNode.m=0&tNode.c=3)if(tNode.m=tNode.c)|(tNode.m=3)|(t

6、Node.m=0)returntrue;elsereturnfalse;elsereturnfalse;)booloperator=(MCNodem1,MCNodem2)/重載運(yùn)算符，判斷兩結(jié)構(gòu)體是否相等(if(m1.m=m2.m&m1.c=m2.c&m1.b=m2.b)returntrue;elsereturnfalse;)boolIsClosed(MCNodetNode)/判斷是否已在closed表中(inti;for(i=0;i!=closed.size();i+)(if(tNode=closedi)returntrue;)if(i=closed.size()returnfalse;)v

7、oidExpandNode(MCNodetNode,intb,list&fringe)(MCNodenode5;/應(yīng)用5條規(guī)則集生成新結(jié)點(diǎn)if(b=1)(for(inti=0;i5;i+)nodei.b=0;node0.m=tNode.m-1;node0.c=tNode.c;node1.m=tNode.m;node1.c=tNode.c-1;node2.m=tNode.m-1;node2.c=tNode.c-1;node3.m=tNode.m-2;node3.c=tNode.c;node4.m=tNode.m;node4.c=tNode.c-2;)else(for(inti=0;i5;i+)n

8、odei.b=1;node0.m=tNode.m+1;node0.c=tNode.c;node1.m=tNode.m;node1.c=tNode.c+1;node2.m=tNode.m+1;node2.c=tNode.c+1;node3.m=tNode.m+2;node3.c=tNode.c;node4.m=tNode.m;node4.c=tNode.c+2;)for(inti=0;i5;i+)if(IsLegal(nodei)&!IsClosed(nodei)fringe.push_front(nodei);/隊(duì)列后進(jìn)先出，深度優(yōu)先搜索，最后得到一條最小解序列/fringe.push_bac

9、k(nodei);/隊(duì)列后進(jìn)后出，廣度優(yōu)先搜索，最后得到最小解序列狀態(tài)空間圖)voidmain()(MCNodeInitNode,unode;InitNode.m=3;InitNode.c=3;InitNode.b=1;fringe.push_back(InitNode);/將初始狀態(tài)空間加入到隊(duì)列while(!fringe.empty()(unode=fringe.front();fringe.pop_front();if(IsGoal(unode)(closed.push_back(unode);for(inti=0;i!=closed.size();i+)coutclosedi.m,clos