基于回溯推理的小型专家系统

《基于回溯推理的小型专家系统》实验报告2011年5月1日目录一、实验题目............................................ 错误！未定义书签。

二、实验目的 (3)三、实验要求 (6)四、实验步骤 (6)基本设计思路 (8)流程框图 (10)数据测试 (12)五、实验方案设计实现 (16)六、实验程序使用说明 (8)八、实验心得体会 (15)九、源程序清单 (22)一、实验要求利用产生式规则构建一个简单的专家系统a)题目自拟（手机选择、电脑选择、玉石选择……）b)要求：1、确定推理方法（正向还是反向），并根据问题设计实现一个简单的不通用推理机（匹配、冲突消解）2、规则库要求至少包含15条规则3、初始事实可以任意给定，输入初始事实后能够得到推理结果4、设计人机界面，解释模块提供查询规则的功能5、可以不考虑知识库管理模块6、提交实验报告，实验名称为：基于回溯推理的小型专家系统7、报告中要有推理树二、实验目的通过编写设计专家推理系统，加深对产生式表示的理解。

三、实验步骤基本设计思路步1 将初始事实置入动态数据库；步2 用动态数据库中的事实，匹配目标条件，若目标条件满足，则推理成功，结束。

步3 用待测试规则集中各规则的前件匹配动态数据库中的事实，将匹配成功的规则组成冲突集；步4 若冲突集为空，则运行失败，退出。

步5 对冲突集做冲突消解，对选择执行的各规则，将其结论加入动态数据库，或执行其动作，转步2。

流程框图数据测试//Unicode编码_测试数据_规则集.txt它种子的胚有两个子叶∨它的叶脉为网状=它是双子叶植物它种子的胚有一个子叶=它是单子叶植物它的叶脉平行=它是单子叶植物(它是双子叶植物∧它的花托呈杯形)∨(它是双子叶植物∧它的花为两性∧它的花瓣有5枚)=它是蔷薇科植物它是蔷薇科植物∧它的果实为核果=它是李亚科植物它是蔷薇科植物∧它的果实为梨果=它是苹果亚科植物它是李亚科植物∧它的果皮有毛=它是桃它是李亚科植物∧它的果皮光滑=它是李它的果实为扁圆形∧它的果实外有纵沟=它是桃它是苹果亚科植物∧它的果实里无石细胞=它是苹果它是苹果亚科植物∧它的果实里有石细胞=它是梨它的果肉为乳黄色∧它的果肉质脆=它是苹果// Unicode编码_测试数据_初始事实.txt它种子的胚有两个子叶它的果肉为乳黄色它的果实里无石细胞它的果实为梨果它的果实无毛它的花托呈杯形四、实验方案设计实现由于规则集和初始事实集可能非常大，所以这里采用读入文件的方法。

为了支持中文，这里采用了Unicode编码，文本文件保存时，必须选择以Unicode的形式保存，否则会出现乱码。

对文本进行解剖的过程比较麻烦，主要是因为Unicode文本中含有很多不可视的控制字符，两个字符串，看上去一模一样，但进行比对操作后并不相等，就是因为这些不可视的控制字符导致的。

所以对文本进行解剖的过程中，必须多加注意对不可视控制字符的过滤。

为了让用户能看清整个推理过程，设了一个“推理下一步”的按钮，让用户一步步执行。

比较棘手的是前提是否成立的验证过程，运算符有∧)∨(，还要考虑运算符优先级问题。

这里模仿了利用栈进行四则运算的过程。

使用两个栈，一个保存运算符，一个保存操作数。

在表达式最后面加一个”#”作为结束符，不断提取前提中的下一个元素，当为操作数时，进操作数栈。

当为运算符时，对比它和运算符栈里最后一个运算符的优先级，如果栈中的那个优先级低，直接进栈。

否则要以栈中那个运算符为运算符，操作数栈最后两个为操作数，进行一次运算。

结果为真时，用字符串”@true”表示，结果为假时，用”@false”表示。

当匹配成功，把结论增加到事实集中，把该规则从“待测试规则”转移到“匹配规则集”列表中。

为了画面简洁，这里用规则号表示规则，用户如果要查看详细规则的说明，点击“查看规则”，就会弹出一个新的对话框。

在MFC中，我们用一个类对表示这个对话框，当用户点击按钮时，我们将其实例化，并调用ShowWindows。

为了从父对话框更新子对话框的控件，子对话框的类中，设计了专门的接口。

enum MATCH_RESULT{MATCH_RESULT_SUCCESSED,MATCH_RESULT_FAILED,};enum OPERATOR_CMP_RESULT{OPERATOR_CMP_LESS,OPERATOR_CMP_EQUAL,OPERATOR_CMP_GREATER,};CString OpenAndReadFile(CString &str);void PrintStr(vector<CString> &vec,HWND wnd,INT itemId);void PrintInt(vector<int> &vec,HWND wnd,INT itemId);void SeperateRule(const CString &rule,CString &left,CString &right);MATCH_RESULT Match(CString pre,vector<CString> &truths);OPERATOR_CMP_RESULT OperatorCmp(CString a,CString b);CString Calcute(CString a,CString oper,CString b,vector<CString> &truths);void NextElement(CString &res,CString &str);bool IsOperator(WCHAR oper);bool Find(vector<CString> &vec,CString v);void NextLine(CString &res,CString &str);bool IsEmptyWChar(WCHAR ch);void init();void UpdateAllLists();afx_msg void OnBnClickedChooseRule();afx_msg void OnBnClickedCheckRule();afx_msg void OnBnClickedChooseTruth();afx_msg void OnBnClickedStart();void UpdateTotalRules(vector<CString> vec);五、实验程序使用说明启动程序选择规则集规则集载入成功选择初始事实集初始事实集载入成功查看规则集详细描述不断按“推理下一步”，得到最后结果六、实验心得体会通过这次实验，加深了对正向推理的理解。

正向推理又称为正向链接推理，其推理基础是逻辑演绎的推理链，它从一组表示事实的谓词或命题出发，使用一组推理规则，来证明目标谓词公式或命题是否成立。

实现正向推理的一般策略是：先提供一批数据(事实)到总数据库中，系统利用这些事实与规则的前提匹配，触发匹配成功的规则(即启用规则)，把其结论作为新的事实添加到总数据库中。

继续上述过程，用更新过的总数据库中的所有事实再与规则库中另一条规则匹配，用其结论再修改总数据库的内容，直到没有可匹配的新规则，不再有新的事实加到总数据库为止。

同时加强了对MFC和Unicode的实践。

七、源程序清单enum MATCH_RESULT{MATCH_RESULT_SUCCESSED,MATCH_RESULT_FAILED,};enum OPERATOR_CMP_RESULT{OPERATOR_CMP_LESS,OPERATOR_CMP_EQUAL,OPERATOR_CMP_GREATER,};//打开文件，并返回其内容CString OpenAndReadFile(CString &str){CFileDialog fd(TRUE,NULL,NULL,NULL,L"所有文件(*.*)|*.*");;if(fd.DoModal()==IDOK){CFile f;f.Open(fd.GetPathName(),CFile::modeRead |CFile::modeNoTruncate);int len=f.GetLength()/sizeof(TCHAR);TCHAR *buf=new TCHAR[len+5];f.Read(buf,f.GetLength());buf[len]=L'\0';str=CString(buf);delete []buf;}return fd.GetPathName();}//把CString列表打印到对应的控件上void PrintStr(vector<CString> &vec,HWND wnd,INT itemId){CString str;for(int i=0;i<vec.size();i++)str=str+vec[i]+L"\r\n";SetDlgItemText(wnd,itemId,str);}//把Int列表打印到对应的控件上void PrintInt(vector<int> &vec,HWND wnd,INT itemId){CString str;for(int i=0;i<vec.size();i++){CString tmp;tmp.Format(L"%d\r\n",vec[i]);str=str+tmp;}SetDlgItemText(wnd,itemId,str);}//把规则根据等号分成左右两部分void SeperateRule(const CString &rule,CString &left,CString &right) {int p=rule.Find(L'=');left=rule.Mid(0,p);right=rule.Mid(p+1,rule.GetLength());}//通过两个栈来实验运算，看规则前提是否成立MATCH_RESULT Match(CString pre,vector<CString> &truths){pre=pre+L"#";stack<CString> operatorStack;stack<CString> operandStack;operatorStack.push(L"#");CString next;NextElement(next,pre);while(next!=L"#" || operatorStack.top()!=L"#"){if(!IsOperator(next[0])){operandStack.push(next);NextElement(next,pre);}elseswitch(OperatorCmp(operatorStack.top(),next)) {case OPERATOR_CMP_LESS:operatorStack.push(next);NextElement(next,pre);break;case OPERATOR_CMP_EQUAL:operatorStack.pop();NextElement(next,pre);break;case OPERATOR_CMP_GREATER:{CString b=operandStack.top();operandStack.pop();CString a=operandStack.top();operandStack.pop();CString oper=operatorStack.top();operatorStack.pop();operandStack.push(Calcute(a,oper,b,truths));break;}default:break;}}if(operandStack.top()==L"@true")return MATCH_RESULT_SUCCESSED;elsereturn MATCH_RESULT_FAILED;}//对比运算符的优先级别OPERATOR_CMP_RESULT OperatorCmp(CString a,CString b){if( (a==L"∨"||a==L"∧")&&(b==L"∨"||b==L"∧"||b==L"#"||b==L")")) return OPERATOR_CMP_GREATER;else if(a==L"("&&b==L")" || a==L"#"&&b==L"#" )return OPERATOR_CMP_EQUAL;elsereturn OPERATOR_CMP_LESS;}//进行逻辑运算CString Calcute(CString a,CString oper,CString b,vector<CString> &truths) {if(oper==L"∧")return ((a==L"@true" || Find(truths,a)) &&(b==L"@true" || Find(truths,b)))?L"@true":L"@false";else if(oper==L"∨")return ((a==L"@true" || Find(truths,a)) ||(b==L"@true" || Find(truths,b)))?L"@true":L"@false";}//在前提中提取下一个元素void NextElement(CString &res,CString &str){int i=0;while(!IsOperator(str[i]))i++;if(i==0){res=str.Mid(0,1);str=str.Mid(1);}else{res=str.Mid(0,i);str=str.Mid(i);}}//检测这字符是否为运算符bool IsOperator(WCHAR oper){return oper==L'('||oper==L')'||oper==L'∧'||oper==L'∨'||oper==L'='||oper==L'#';}//在vector<CString>中查找v是否存在bool Find(vector<CString> &vec,CString v){for(int i=0;i<vec.size();i++){int t1=vec[i].GetLength();int t2=v.GetLength();if(vec[i].Compare(v)==0)return true;}return false;}//检测字符是否为不可见字符bool IsEmptyWChar(WCHAR ch){return ch==L'\r' || ch==L'\n' || ch==L'\0' || ch==0xEF || ch==0xBB || ch==0xBF ||ch==65279;}//在res中提取下一行void NextLine(CString &res,CString &str){int t=str.GetLength();int a=0;while(IsEmptyWChar(str[a]))a++;int b=a+1;while(!IsEmptyWChar(str[b]))b++;res=str.Mid(a,b-a);str=str.Mid(b+1);//初始化void CReasoningDlg::init(){mTotalRules.clear();mCurRules.clear();mTruths.clear();mConficts.clear();}//选择规则集void CReasoningDlg::OnBnClickedChooseRule(){init();CString str,path,line;path=OpenAndReadFile(str);SetDlgItemText(IDC_RULE_PATH,path);while(true){if(str.GetLength()<3)break;NextLine(line,str);mTotalRules.push_back(line);mCurRules.push_back(mTotalRules.size()-1);}PrintInt(mCurRules,m_hWnd,IDC_RULE_LIST);}//查看规则集void CReasoningDlg::OnBnClickedCheckRule(){CCheckDialog *dlg=new CCheckDialog();dlg->Create(MAKEINTRESOURCE(IDD_CHECK_DIALOG));dlg->UpdateTotalRules(mTotalRules);dlg->ShowWindow(SW_NORMAL);}//选择事实集void CReasoningDlg::OnBnClickedChooseTruth(){mTruths.clear();CString str,path,line;path=OpenAndReadFile(str);SetDlgItemText(IDC_TRUTH_PATH,path);while(true){if(str.GetLength()<3)break;NextLine(line,str);mTruths.push_back(line);}PrintStr(mTruths,m_hWnd,IDC_TRUTH_LIST);}//下一步推理void CReasoningDlg::OnBnClickedStart(){for(vector<int>::iteratoriter=mCurRules.begin();iter!=mCurRules.end();iter++) {CString left,right;SeperateRule(mTotalRules[*iter],left,right);int result=Match(left,mTruths);switch(result){case MATCH_RESULT_SUCCESSED:mConficts.push_back(*iter);mTruths.push_back(right);mCurRules.erase(iter);break;case MATCH_RESULT_FAILED:break;default:break;}if(result==MATCH_RESULT_SUCCESSED)break;}UpdateAllLists();}//更新所有列表void CReasoningDlg::UpdateAllLists(){PrintInt(mCurRules,m_hWnd,IDC_RULE_LIST);PrintStr(mTruths,m_hWnd,IDC_TRUTH_LIST);PrintInt(mConficts,m_hWnd,IDC_CONFICT_LIST);}//子对话框更新接口void CCheckDialog::UpdateTotalRules(vector<CString> vec) {CString num;for(int i=0;i<vec.size();i++){num.Format(L"R%d:",i);vec[i]=num+vec[i];}PrintStr(vec,m_hWnd,IDC_TOTAL_RULE);}。