产生式系统实验报告张昆.docx

产生式系统实验报告姓名:张昆 学号:E201102044一、 产生式系统的组成一个产生式系统由三大部分组成。1、一组称为产生式的规则。每一规则分左右两部，左部确定该规则的可用性，右部描述应用该规则时采用的行动。这些行动主要是修改数据库的内容。2、一个或多个数据库，它们含有适合于该特定任务的信息，数据库中有些部分可以使永久性的，有些则是仅与求解当前问题有关，可按任何适当的方法构造数据库中的信息；3、一个执行问题求解过程的规则解释程序。产生式系统是通过一系列“识别作用”周期来执行求解过程。简单的“识别作用”执行模式是这样：相对于当前数据库的内容，每条产生式的左部被求值，确定哪些产生式是被满足的，二这些被满足的产生式构成冲突集。从冲突集中选择一个产生式，执行该产生式的右部，即改变数据库中的内容。相对于新的数据库内容，这种“识别作用”过程重复进行。“识别作用”周期停止的条件是：（1）冲突集为空域；（2）所期望的数据库内容出现，即求得问题的解。从冲突集总选择一个产生式的过程称为冲突解决。二、 动物识别系统1、 动物识别系统规则库设计 数据结构： typedef struct int rslt;int codNum;/记载前提的个数int cod10;/记载前提的序号int used;/记载是否已匹配成功Nrule;方便起见，前提和结论对应为数字，如图1；规则库存储于文件中，如图2图1 图22、 回溯策略2.1 如图3，纵向递归推理，横向选择推理分支 ；两个回溯点：状态不合法、冲突集为空 ；结束：找到目标状态、尝试所有路径没有解答 图32.2 递归算法：PS_BACKTRACK(db)(1) 若db指示了目标状态，则输出（显示）db作为解答,算法成功结束；(2) 若db指示了失败状态，则返回真值F；(3) rs :=RULE_ACTIVATE(db)，并用启发式知识对rs中的规则按从优到劣的次序排列；(4) 若rs为空，则返回真值F；(5) r:=MOVE_FIRST(rs)；(6) PS_BACKTRACK(TRANSFORM(db,r)；(7) 返回语句（4）。 其中db为数据库内容，RULE_ACTIVATE()为匹配函数，MOVE_FIRST()功能为获取最优触发规则，TRANSFORM()将结论加入数据库3、 相关策略3.1 冲突解决策略：按详细程度排序，即优先选择前提部分描述最详细的规则 3.2 动物识别系统的推理策略：正向推理 三、 实验代码#include#include#include#include#define MAXNUM 50typedef structint xuh;char valu50;Node;typedef structint stat;/0：还未访问 1：至少用过一次 2：没用过但不冲突int xuh;NFact;typedef structint snum;/开始时的事实数int curnum;/目前的事实数int notEnoughFlag;/当最后若所有未用过的条件支持一个结论，但条件不足时，置1NFact codMAXNUM;Fact;typedef structint rslt;int codNum;/记载前提的个数int cod10;/记载前提的序号int used;/记载是否已匹配成功Nrule;typedef structint codXuh;int stat;double weight;int rslt;/int codNum;bQueueNode;typedef structint head;int tail;bQueueNode bNodeMAXNUM;bQueue;typedef structint canReachTime;int havReached;Reach;typedef structint lastCodXuhInQueue;int myXuh;/int mycodNum;int myRslt;doublemyweight;CloseNode;typedef structint head;int tail;CloseNode nodeMAXNUM; Close;int codnum=28;int goalnum=7;int rulenum=0;Node goal20;Node cod50;Nrule rule50;Fact inpCod;bQueue bqueue;Reach recReachMAXNUM;Close close;void readGoal()FILE *fp;int i;if(fp=fopen(goal.txt,r)=NULL)printf(cannot open goaln);exit(0);i=0;while(fscanf(fp,%d %s,&goali.xuh,&goali+.valu)!=EOF);fclose(fp);/readGoalvoid readRule()FILE *fp;int i;int tempxuh,tempcodn;char ch;if(fp=fopen(rules.txt,r)=NULL)printf(cannot open datan);exit(0);i=0;rulei.codNum=0;while(ch=fgetc(fp)!=EOF)if(i=14)i=i;tempcodn=0;while(ch!=n&ch!=EOF)/每一条规则tempxuh=0;while(ch=0)tempxuh=tempxuh*10+ch-0;ch=fgetc(fp);rulei.codtempcodn+=tempxuh;tempxuh=0;if(ch=-)/下一个是结论ch=fgetc(fp);ch=fgetc(fp);while(ch=0)tempxuh=tempxuh*10+ch-0;ch=fgetc(fp);rulei.rslt=tempxuh;/ifelse if(ch=*)ch=fgetc(fp);rulei.codNum+;i+;rulenum=i;fclose(fp);/readCodvoid readCod()FILE *fp;int i;if(fp=fopen(data.txt,r)=NULL)printf(cannot open datan);exit(0);i=0;while(fscanf(fp,%d %s,&codi.xuh,&codi+.valu)!=EOF);fclose(fp);/readCodvoid readFiles()/char fname100;readGoal();readCod();readRule();/reaFilesint inputCod()int retflag=1;int temp;int i;i=0;doscanf(%d,&temp);inpCod.codi+.xuh=temp;if(temp=codnum)printf(特征序号不能大于%d,请重新输入:n,codnum-1);fflush(stdin);retflag=0;while(temp!=-1&tempcodnum);inpCod.snum=i-1;inpCod.curnum=inpCod.snum;/*inpCod.snum=5;inpCod.curnum=inpCod.snum;inpCod.cod0.xuh=1;inpCod.cod1.xuh=5;inpCod.cod2.xuh=10;inpCod.cod3.xuh=15;inpCod.cod4.xuh=16;*/return retflag;/inputCod()int onlyExtra(int inpCodXuh,int rslt)int i,j;int fa50;int head;int tail;int retflag;int tempstate50;/若放入队列中，则记录为1fa0=rslt;tempstaterslt=1;head=0;tail=1;retflag=0;while(head!=tail&retflag!=1)for(j=0;jrulenum;j+)if(rulej.rslt=fahead)for(i=0;irulej.codNum;i+)if(inpCod.codinpCodXuh.xuh=rulej.codi)/if(inpCodXuh=rulej.codi)retflag=1;elseif(tempstaterulej.codi!=1)fatail+=rulej.codi;tempstaterulej.codi=1;head+;return retflag;/onlyExtraint isContradict(int rslt)int i;int flag;flag=0;for(i=0;i=codnum)/已推理出一个动物*doneflag=1;if(isContradict(rslt)printf(条件有冲突，没有这样的动物。n);elseprintf(它是%s。n,goalrslt-codnum.valu);/isAim()void addFact(int ruleXuh,int *doneflag)int i;int flagHave;flagHave=0;/标志此次推出的结论是否已在inpCod.cod中for(i=0;iinpCod.curnum;i+)if(inpCod.codi.xuh=ruleruleXuh.rslt)flagHave=1;if(flagHave=0)inpCod.codinpCod.curnum.xuh=ruleruleXuh.rslt;inpCod.curnum+;isAim(ruleruleXuh.rslt,doneflag);/addFact()void fitOneRule(int ruleXuh,int *doneflag)int i,k;for(i=0;iruleruleXuh.codNum;i+)/作inpCod的访问标记for(k=0;kinpCod.curnum;k+)if(ruleruleXuh.codi=inpCod.codk.xuh)inpCod.codk.stat=1;/forruleruleXuh.used=1;addFact(ruleXuh,doneflag);/fitOneRule()void countNoUseF(int *recNoUseF,int *recNoUseFNum)int i;int tempstate50;/若已经在recNoUseF中记录过，就记为1for(i=0;i27)result=goal;resultXuh-=28;if(tempflag=0)printf(条件不完全,但它有%s,resultresultXuh.valu);elseprintf(和%s,resultresultXuh.valu);/printLikeClouse()void maybeAnimal()int i,j,k;/int countMaybe;int countLikeCurRule;int recNoUseF50,recNoUseFNum;int printRec50;/若前面已推出这个可能结论，就置为1int tempflag;recNoUseFNum=0;countNoUseF(recNoUseF,&recNoUseFNum);/countMaybe=0;tempflag=0;for(i=0;irulenum;i+)countLikeCurRule=0;for(j=0;jrulei.codNum;j+)for(k=0;k=rulei.codNum&printRecrulei.rslt!=1)printLikeClouse(tempflag,i,printRec);tempflag=1;if(tempflag=0)printf(条件不足，不能推出它是什么动物);elseprintf(的部分特征);printf(。n);/maybeAnimal()void forwardFinger()int flag;/1：工作已完成 0：还未完成int flagFit;int flagCNew;/记录本次循环有没有推出新事实int fitPart;/1:有部分符合条件int i,j,k;flag=0;flagCNew=1;while(!flag&flagCNew=1)flagCNew=0;for(j=0;jrulenum&rulej.used!=1&flag=0;j+)/一条规则if(rulej.codNum=inpCod.curnum)/事实数不小于当前规则所要求的条件数flagFit=1;for(i=0;irulej.codNum&flagFit=1;i+)fitPart=0;for(k=0;kinpCod.curnum;k+)if(rulej.codi=inpCod.codk.xuh)fitPart=1;flagFit=fitPart;if(flagFit=1)flagCNew=1;fitOneRule(j,&flag);/有事实匹配时，就处理把结论加入事实库等事情flagFit=0;/whileif(flagCNew=0)maybeAnimal();/当没有推出任何动物时，看是否极有可能得出一些结论/if(flag=0)/finger()void printChoice()int i,j;j=0;for(i=0;icodnum;i+)/for(j=0;j4;j+)printf(%-2d %-14s,codi.xuh,codi.valu);j+;if(j%4=0)printf(n);printf(n);/printChoice() void init()int i;for(i=0;iMAXNUM;i+)rulei.used=0;inpCod.notEnoughFlag=0;inpCod.codi.stat=0;/init()void findCod()int i;for(i=0;iinpCod.curnum;i+)/for(j=bqueue.head;jbqueue.tail;j+)/if(inpCod.codi.xuh=bqueue.bNodebqueue.head.codXuh)bqueue.bNodebqueue.head.stat=1;inpCod.codi.stat=1;/return;/findCod()void recMarkdCod(bQueueNode *markdCod,int *markdCodNum)/int i;int j;int flagRecd;/for(i=bqueue.head;ibqueue.tail;i+)/flagRecd=0;if(bqueue.bNodebqueue.head.stat=1)for(j=0;j*markdCodNum;j+)if(markdCodj.codXuh=bqueue.bNodebqueue.head.codXuh&markdCodj.rslt=bqueue.bNodebqueue.head.rslt)flagRecd=1;markdCodj.weight=bqueue.bNodebqueue.head.weight;if(flagRecd=0)markdCod*markdCodNum.codXuh=bqueue.bNodebqueue.head.codXuh;markdCod*markdCodNum.weight=bqueue.bNodebqueue.head.weight;markdCod*markdCodNum.rslt=bqueue.bNodebqueue.head.rslt;(*markdCodNum)+;/return;/recMarkdCod()void countReachTime()int i;for(i=0;irulenum;i+)+(recReachrulei.rslt.canReachTime);/countReachTime()void addNodeToQueue()int i,j;int flagReachTime,flagReach;flagReachTime=0;flagReach=0;for(i=0;irulenum&flagReach=0;i+)if(rulei.rslt=bqueue.bNodebqueue.head.codXuh)if(recReachrulei.rslt.havReached=flagReachTime)flagReach=1;+(recReachrulei.rslt.havReached);for(j=0;jrecReachxuh.havReached)close.nodeclose.tail.myXuh=xuh;close.nodeclose.tail.lastCodXuhInQueue=lastCodXuhInQueue;close.nodeclose.tail.myweight=bqueue.bNodebqueue.head.weight;close.nodeclose.tail.myRslt=bqueue.bNodebqueue.head.rslt;/findMycodNum();/close.nodeclose.tail.mycodNum=bqueue.bNodexuh.codNum;+close.tail;return;/takeTOClose()void takeTobqueue(int xuh)bqueue.bNodebqueue.tail.codXuh=close.nodexuh.myXuh;bqueue.bNodebqueue.tail.stat=0;bqueue.bNodebqueue.tail.weight=close.nodexuh.myweight;bqueue.bNodebqueue.tail.rslt=close.nodexuh.myRslt;+bqueue.tail;/+(recReachclose.nodexuh.myXuh.havReached);/*if(recReachclose.nodexuh.myXuh.havReached=recReachclose.nodexuh.myXuh.canReachTime)close.head+;*/close.head+;/takeTobqueue()double workFitDegree(bQueueNode *markdCod,int markdCodNum)int i;double fitDegree=0;for(i=0;imarkdCodNum;i+)fitDegree+=markdCodi.weight;return fitDegree;/workFitDegree()void initBack(double *fitDegree,int *markdCodNum,int testGoalXuh)int i;for(i=0;iMAXNUM;i+)recReachi.havReached=0;bqueue.bNodei.stat=0;bqueue.bNodei.weight=0;bqueue.bNodei.codXuh=0;bqueue.bNodei.rslt=-1;inpCod.codi.stat=0;bqueue.bNode0.codXuh=codnum+testGoalXuh;bqueue.bNode0.weight=1;bqueue.bNode0.rslt=-1;bqueue.head=0;bqueue.tail=1;close.head=0;close.tail=0;*markdCodNum=0;*fitDegree=0;/initBack()void bDisplayResult(double fitDegree,int Ncontradict,int goalXuh,int *flagFitAll)/double absFitDegree;/absFitDegree=abs(1.0-fitDegree);if(Ncontradict=0)printf(条件有冲突，它不是%s。n,goalgoalXuh.valu);else if(1.0-fitDegree)=0.5)printf(它有%s的部分特征。n,goalgoalXuh.valu);elseprintf(它有一点点%s的特征。n,goalgoalXuh.valu);/bDisplayResult()int StillCodNoUseAndContradict(int rslt)int i;int retflag=0;for(i=0;iinpCod.curnum;i+)if(inpCod.codi.stat=0&onlyExtra(i,rslt)=0)retflag=1;return retflag;/StillCodNoUseAndContradict()void backFi