人工智能试验知识表示法

1、实验二知识表示方法1 .实验目的(1)了解知识表示相关技术；(2)掌握问题规约法或者状态空间法的分析方法。2 .实验内容(2个实验内容可以选择1个实现)(1)梵塔问题实验。熟悉和掌握问题规约法的原理、实质和规约过程；理解规约图的表示方法；(2)状态空间法实验。从前有一条河，河的左岸有m个传教士、m个野人和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。搜索一条可使所有的野人和传教士安全渡到右岸的方案。3.实验报告要求(1)简述实验原理及方法，并请给出程序设计流程图。本次试验选择传教士过河问题，以状态空间法实现。解答步骤如下：(1)设置

2、状态变量并确定值域M为传教士人数，C为野人人数，B为船数，要求M=C1M+C=3,L表示左岸，R表示右岸。目标状态初始状态(2)确定状态组，分别列出初始状态集和目标状态集用三元组来表示Sf：(ML,CL,BL)(均为左岸状态)其中0WML3,0CL3,BL0,1初始状态表示全部成员在河的的左岸；目标状态表示全部成员从河的左岸全部渡河完毕。(3)定义并确定规则集合仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij操作。其中，第一下标i表示船载的传教士数，第二下标j表示船载的食人者数；同理，从右岸将船划回左岸称之为Qij操作，下标的定义同前。则共有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)当状态数量不是很大时，画出合理的状态空间图Jf=2Q0i1)*f=4Pza(L30)(231)CO,2，U)lrf=3Qoi01)图1状态空间图箭头旁边所标的数字表示了P或Q操作的下标,即分别表示船载的传教士数和食人者数。接下来进行树的遍历，根据规则由根（初始状态）扩展出整颗树，检测每个结点的“可扩展标记”，为“-1”的即目标结点。由目标结点上溯出路径。(2)源程序清单：/关键代码#include#include#include

5、usingnamespacestd;typedefstructintm;/表示传教士intc;/表示野人intb;/船状态MCNode;listfringe;/相当于队列vectorclosed;/closed表/判断是否是目标结点boolIsGoal(MCNodetNode)if(tNode.m=0&tNode.c=0&tNode.b=0)returntrue;elsereturnfalse;/判断是否是合法状态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)/重载运算符，判断两结构体是否相等(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;/应用5条规则集生成新结点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);/队列后进先出，深度优先搜索，最后得到一条最小解序列/fringe.push_bac

9、k(nodei);/队列后进后出，广度优先搜索，最后得到最小解序列状态空间图)voidmain()(MCNodeInitNode,unode;InitNode.m=3;InitNode.c=3;InitNode.b=1;fringe.push_back(InitNode);/将初始状态空间加入到队列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