人工智能原理实验.

1、人工智能实验计算机科学与技术必修实验一 产生式系统实验一、实验目的：复习产生式系统相关内容，熟悉和掌握产生式系统的运行机制，掌握基于规则推理的基本方法，能够应用产生式系统解决简单问题的方法。二、实验原理产生式系统用来描述若干个不同的以一个基本概念为基础的系统，这个基本概念就是产生式规则或产生式条件和操作对。在产生式系统中，论域的知识分为两部分：用事实表示静态知识；用产生式规则表示推理过程和行为。三、实验条件：1、PC机2、Windows操作系统平台3、VC集成开发环境四、实验内容：1、问题描述：设有N(本次设计控制在1-9之间，下同)个传教士和N个野人同在河的左岸，他们都要到对岸去；河里只有一

2、条船，他们都会划船，但每次渡船至多只能乘N人；如果在任何一边河岸上，野人的数量超过传教士，野人就要吃掉传教士，问怎样才能用船将N个传教士和N个野人从左岸都渡到右岸，又不会发生传教士被吃的事件呢？2.建造产生式系统（包括规则库和事实库），然后进行推理，即可以自己输入任何的规则和事实，并基于这种规则和事实进行推理。五、实验步骤：1.数学模型描述：设计该问题的状态。使用三元组表示某一时刻传教士，野人，渡船情况，(左岸牧师数，左岸野人数，船的位置)。其中：左岸牧师数、左岸野人数取值范围为19之间；船的位置取值范围为0-1，0代表左岸，1代表右岸。2.定义初始状态和目标状态。根据数学模型描述，初始状态为

3、（N，N，1），目标状态为（0，0，0）。3.定义产生式规则库。根据系统设计的规则要求列出所有合法的状态转变过程。基本思想：树的按层次遍历算法。由初始状态开始按层次逐个生成符合规则的产生式规则。4.控制策略应用深度优先搜索方式在规则库中查找答案。控制策略用于整个的推理过程实现，本次设计的搜索算法为图搜索策略中的深度优先搜索方式。 实验结论：包括做实验的目的、方法、过程等，具体要写成实验报告，如下图所示。姓名李进东年级13Y3057专业计算机日期2014.6.3实验目的复习产生式系统相关内容，熟悉和掌握产生式系统的运行机制，掌握基于规则推理的基本方法，能够应用产生式系统解决简单问题的方法。推理方

4、法 正向推理 反向推理建立规则库建立事实库P10if ( M ,C , B=1 )then ( M1 , C , B 1 ) P01if ( M ,C , B=1 )then ( M , C1 , B 1 ) P11if ( M ,C , B=1 )then ( M1 , C1 , B 1 ) P20if ( M ,C , B=1 )then ( M2 , C , B 1 ) P02if ( M ,C , B=1 )then ( M , C2 , B 1 ) Q10 if ( M ,C , B=0 )then ( M+1 , C , B+1 ) Q01if ( M ,C , B=0 )then

5、 ( M , C+1 , B +1 ) Q11if ( M ,C , B=0 )then ( M+1 , C +1, B +1 ) Q20if ( M ,C , B=0 )then ( M+2 , C +2, B +1 ) Q02if ( M ,C , B=0 )then ( M , C +2, B +1 ) 预测结果 顺利通过实验过程及结果(注意观测规则的匹配过程和方法)第1次：左岸到右岸，传教士过去1人，野人过去1人第2次：右岸到左岸，传教士过去1人，野人过去0人第3次：左岸到右岸，传教士过去0人，野人过去2人第4次：右岸到左岸，传教士过去0人，野人过去1人第5次：左岸到右岸，传教士过去2

6、人，野人过去0人第6次：右岸到左岸，传教士过去1人，野人过去1人第7次：左岸到右岸，传教士过去2人，野人过去0人第8次：右岸到左岸，传教士过去0人，野人过去1人第9次：左岸到右岸，传教士过去0人，野人过去2人第10次：右岸到左岸，传教士过去0人，野人过去1人第11次：左岸到右岸，传教士过去0人，野人过去2人 结论 传教士和野人能够顺利过河备注(原因等)成绩及评语 实验二 谓词公式合一一、实验目的：理解代换、合一的概念，掌握对文字进行代换的方法；能够判断文字L1和L2经过执行某个代换s是否可合一。二、实验原理合一算法：文字L1和L2如果经过执行某个代换s，满足L1s=L2s，则称L1与L2可合一

7、，s称为其合一元。三、实验条件：1. 合一演示程序。2.IE5.0以上，可以上Internet。 四、实验内容：理解合一原理，熟悉对可合一文字进行合一的方法。五、实验步骤：1.对测试用例进行试验。进入演示程序，点击“合一测试”，得到合一结果。2.自定义待合一文字。点击“合一测试”验证合一概念。3.语法检查。点击“语法检查”检查输入谓词公式的语法错误。如无错误，则依次点击步骤按钮进行消解。4.重复运行2、3步，熟悉消解原理和消解过程。六、实验报告：谓词公式合一实验目的理解代换、合一的概念，掌握对文字进行代换的方法；能够判断文字L1和L2经过执行某个代换s是否可合一。实验步骤1.对测试用例进行试验

8、。进入演示程序，点击“合一测试”，得到合一结果。2.自定义待合一文字。点击“合一测试”验证合一概念。3.语法检查。点击“语法检查”检查输入谓词公式的语法错误。如无错误，则依次点击步骤按钮进行消解。4.重复运行2、3步，熟悉消解原理和消解过程。实验结果以该测试用例为例：L1=p(u,y,g(y)；L2=p(x,f(u),z)；设存在一个最一般合一=u/x，f(u)/y,g(f(u)/z对任意合一=a/x,f(a)/y,g(f(a)/z,a/u存在一个替换=a/u使得=实验三 子句归结与合一一、实验目的：理解含有变量的子句如何使用消解规则，掌握子句消解的原理和规则，能熟练进行任意两个子句的消解，了

9、解消解推理的某些常用规则。二、实验原理：对子句集进行消解推理，得到相应的结论。为了对含有变量的子句使用消解规则，我们必须找到一个置换，作用于父辈子句使其含有互补文字。消解两个子句时，可能有一个以上的消解式，不过，在任何情况下最多有有限个消解式。三、实验条件子句归结与合一演示程序。四、实验内容：1.运行并观察演示实例。2.输入新的子句，检查消解结果。3.根据消解过程理解消解原理和常用规则。五、实验步骤：1. 默认示例演示。进入演示实例，点击“演示实例1”，然后点击“开始消解”，得到消解结果。2.分别运行“演示实例2”和“演示实例 3”，观察消解结果，理解常用消解规则的应用。3.自定义消解子句。点

10、击“系统重置”按钮，再通过键盘与两个按钮“”与“”输入合法的子句，点击“加入子句集”加入子句集，点击“开始消解”，观察消解结果。4.重复步骤3，多次输入不同子句进行消解，熟悉消解过程。六、实验结论：1.熟悉消解过程，理解子句消解规则。2. 给出自己输入的待消解子句、消解结果和详细过程。子句归结与合一实验目的理解含有变量的子句如何使用消解规则，掌握子句消解的原理和规则，能熟练进行任意两个子句的消解，了解消解推理的某些常用规则。实验步骤1. 默认示例演示。进入演示实例，点击“演示实例1”，然后点击“开始消解”，得到消解结果。2.分别运行“演示实例2”和“演示实例 3”，观察消解结果，理解常用消解规

11、则的应用。3.自定义消解子句。点击“系统重置”按钮，再通过键盘与两个按钮“”与“”输入合法的子句，点击“加入子句集”加入子句集，点击“开始消解”，观察消解结果。4.重复步骤3，多次输入不同子句进行消解，熟悉消解过程。实验结果条件子句：P(x,y)Q(y,z)P(A,w)目标子句：Q(B,C)归结过程：C1: (C0,C0) P(x,y) Q(y,z)C2: (C0,C0) P(A,w)T1: (T0,T0) Q(B,C)T2: (C1,C2) Q(w,z) A/x,w/yT3 :(T2,T1) B/w,C/z有效推理路径：C2: (C0,C0) P(A,w)C1: (C0,C0) P(x,y)

12、 Q(y,z)T1: (T0,T0) Q(B,C)T2: (C1,C2) Q(w,z)T3: (T2,T1) 实验四 搜索算法的实现一、实验目的：熟悉和掌握广度优先、深度优先及启发式搜索的定义、估价函数涵义及作用，掌握算法实现方法，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。二、实验原理：A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。三、实验条件：1.N数码难

13、题演示程序。2.IE5.0以上，可以上Internet。三、实验内容：1.分别以8数码和15数码为例实际求解A*算法。2.画出A*算法求解框图。3.分析估价函数对搜索算法的影响。4.分析A*算法的特点。四、实验步骤：1.开始演示。进入N数码难题演示程序，可选8数码或者15数码，点击“选择数码”按钮确定。第一次启动后，点击两次“缺省”或者“随机”按钮，才会出现图片。2.点击“缺省棋局”，会产生一个固定的初始节点。点击“随机生成”，会产生任意排列的初始节点。3.算法执行。点击“连续执行”则程序自动搜索求解，并演示每一步结果；点击“单步运行”则每次执行一步求解流程。“运行速度”可自由调节。4.观察运

14、行过程和搜索顺序，理解启发式搜索的原理。在下拉框中选择演示“15数码难题”，点击“选择数码”确定选择；运行15数码难题演示实例。5.算法流程的任一时刻的相关状态，以算法流程高亮、open表、close表、节点静态图、当前扩展节点移动图等5种形式在按钮上方同步显示，便于深入学习理解A*算法。6.根据程序运行过程画出A*算法框图。五、实验报告要求：1.A*算法流程图和算法框图。2.试分析估价函数的值对搜索算法速度的影响。3.根据A*算法分析启发式搜索的特点。搜索算法的实现实验目的熟悉和掌握广度优先、深度优先及启发式搜索的定义、估价函数涵义及作用，掌握算法实现方法，并利用A*算法求解N数码难题，理解

15、求解流程和搜索顺序。实验步骤1.开始演示。进入N数码难题演示程序，可选8数码或者15数码，点击“选择数码”按钮确定。第一次启动后，点击两次“缺省”或者“随机”按钮，才会出现图片。2.点击“缺省棋局”，会产生一个固定的初始节点。点击“随机生成”，会产生任意排列的初始节点。3.算法执行。点击“连续执行”则程序自动搜索求解，并演示每一步结果；点击“单步运行”则每次执行一步求解流程。“运行速度”可自由调节。4.观察运行过程和搜索顺序，理解启发式搜索的原理。在下拉框中选择演示“15数码难题”，点击“选择数码”确定选择；运行15数码难题演示实例。5.算法流程的任一时刻的相关状态，以算法流程高亮、open表

16、、close表、节点静态图、当前扩展节点移动图等5种形式在按钮上方同步显示，便于深入学习理解A*算法。6.根据程序运行过程画出A*算法框图。实验结果分析估价函数对搜索算法的影响：估价函数就是评价函数，它用来评价子结点的好坏，因为准确评价是不可能的，所以称为估值。这就是我们所谓的有信息搜索。如果估值函数只考虑结点的某种性能上的价值，而不考虑深度，比较有名的就是有序搜索（Ordered-Search），它着重看好能否找出解，而不看解离起始结点的距离（深度）。如果估值函数考虑了深度，或者是带权距离（从起始结点到目标结点的距离加权和），那就是A*如果不考虑深度，就是说不要求最少步数，移动一步就相当于向

17、后多展开一层结点，深度多算一层，如果要求最少步数，那就需要用A*。简单的来说A*就是将估值函数分成两个部分，一个部分是路径价值，另一个部分是一般性启发价值，合在一起算估整个结点的价值，考虑到八数码问题的特点，在本实验中使用A*算法求解。分析A*算法的特点：A*搜索是一种效的搜索算法，它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价：f(n)=g(n)+h(n)。当h(n)是可采纳时，使用Tree-Search的A*算法将是最优的。实验五 博弈树的启发式搜索一、实验目的：内容为极大极小搜索和剪枝技术。极大极小搜索方法表示：对博弈树中的“或”节点，选其子节点中一个

18、最大的得分作为父节点的得分，即选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，即立足于最坏的情况。由于极大极小搜效率较低，因此引入剪枝技术以减少扩展结点的数目。“一字棋”游戏和一个给定结构的博弈树为媒介来展示搜索策略的。二、实验原理：重点掌握剪枝技术，其原理是：(1) 为剪枝：对于一个与节点，若能估计出其倒推值的上确界，并且这个值不大于其父节点(一定是或节点)的估计倒推值的下确界，即，则就不必再扩展该节点的其余子节点。这一过程称。(2) 剪枝：对于一个或节点，若能估计出其倒推值的下确界，并且这个值不小于其父节点(一定是与节点)的估计倒推值的上确界，即，则就不

19、必再扩展该节点的其余子节点。三、实验条件：1.“一字棋”演示程序。2.IE5.0以上，可以上Internet。三、实验内容：1.运用极大极小搜索策略，选择不同的搜索的层次进行博弈树问题的求解。2.运用剪枝策略，选择不同的搜索的层次进行博弈树问题的求解。3.分析比较剪枝对搜索过程的影响。4.分析剪枝算法何时最为高效。四、实验步骤：1.在菜单Choice中选择Game，进入一字棋游戏；选择Demo，进入剪枝演示；选择Exit，退出该程序。2.在一字棋游戏状态下，选择菜单Game下的Play Game，切换到游戏界面；在游戏界面中，左边的棋盘上进行游戏，单击下子；点击右边的Search按钮以当前棋盘

20、状态为初始状态进行搜索，右面的小棋盘显示搜索结果，红色点为建议下子的位置。可选择搜索的层次和搜索的策略（极大极小搜索和剪枝搜索）3.选择菜单Game下的Search Tree，进入搜索树界面，如上图所示。此时棋盘缩小到屏幕左上角。在左边区域每单击一次可显示搜索树的一个结点（注意：一定要确保已经点击了下方的Search进行过搜索，该搜索树以最近产生的搜索树为依据）；叶节点左上角的数字为该节点所代表棋局的静态估计函数值：非叶节点左上角的数字为经过搜索之后该节点的子节点中最佳的估计函数值。棋盘大小选择框设置搜索树中棋盘节点的大小，选择完毕后需点击Search按钮后才有效。在棋局的任何时刻可搜索当前方

21、的最佳走步。五、实验报告要求：1.博弈树搜索问题求解算法框图。2.剪枝技术对搜索算法效率的影响。博弈树的启发式搜索实验目的内容为极大极小搜索和剪枝技术。极大极小搜索方法表示：对博弈树中的“或”节点，选其子节点中一个最大的得分作为父节点的得分，即选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，即立足于最坏的情况。由于极大极小搜效率较低，因此引入剪枝技术以减少扩展结点的数目。实验步骤1.在菜单Choice中选择Game，进入一字棋游戏；选择Demo，进入剪枝演示；选择Exit，退出该程序。2.在一字棋游戏状态下，选择菜单Game下的Play Game，切换到游戏

22、界面；在游戏界面中，左边的棋盘上进行游戏，单击下子；点击右边的Search按钮以当前棋盘状态为初始状态进行搜索，右面的小棋盘显示搜索结果，红色点为建议下子的位置。可选择搜索的层次和搜索的策略（极大极小搜索和剪枝搜索）3.选择菜单Game下的Search Tree，进入搜索树界面，如上图所示。此时棋盘缩小到屏幕左上角。在左边区域每单击一次可显示搜索树的一个结点（注意：一定要确保已经点击了下方的Search进行过搜索，该搜索树以最近产生的搜索树为依据）；叶节点左上角的数字为该节点所代表棋局的静态估计函数值：非叶节点左上角的数字为经过搜索之后该节点的子节点中最佳的估计函数值。棋盘大小选择框设置搜索树

23、中棋盘节点的大小，选择完毕后需点击Search按钮后才有效。在棋局的任何时刻可搜索当前方的最佳走步。实验结果-剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：(1)对于一个与节点MIN，若能估计出其倒推值的上确界，并且这个值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界，即，则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为剪枝。 (2)对于一个或节

24、点MAX，若能估计出其倒推值的下确界，并且这个值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界，即，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。这一过程称为剪枝。从算法中看到：(1)MAX节点(包括起始节点)的值永不减少； (2)MIN节点(包括起始节点)的值永不增加。在搜索期间，和值的计算如下： (1)一个MAX节点的值等于其后继节点当前最大的最终倒推值。 (2)一个MIN节点的值等于其后继节点当前最小的最终倒推值。实验六 基于可信度的不确定性推理系统一、实验目的：理解和掌握基于可信度的不确定知识表示方法和推理过程，能够用Pr

25、olog建立一个简单的不确定性推理系统。二、实验原理可信度方法是E.H.Shortliffe等人在确定性理论(Theory of Confirmation)基础上，结合概率方法等提出的一种不确定性推理方法，其中C-F模型是基于可信度表示的不确定性推理的基本方法。1、知识不确定性的表示C-F模型中，知识用产生式规则表示，其一般形式是：IF E THEN H ( CF(H, E) )其中：E是前提，它既可以是简单条件，也可以是复合条件（AND、OR）；H是结论，它可以是一个单一的结论，也可以是多个结论；CF(H, E)是该条知识的可信度，称为可信度因子(Certainty Factor)或规则强度

26、，为静态强度。CF(H, E)在1, 1上取值，它指出当前提E所对应的证据为真时，它对结论H的支持程度，CF(H, E)的越大，就越支持结论H为真。2、证据不确定性的表示在该模型中，证据的不确定性也是用可信度因子CF(E)表示的。3、组合证据不确定性的表示当组合证据是多个单一证据的合取时，即E = E1 AND E2 AND ( AND En则：CF(E) = minCF(E1)，CF(E2) ,(，CF(En)当组合证据是多个单一证据的析取时，即E = E1 OR E2 OR ( OR En则：CF(E) = maxCF(E1)，CF(E2) ,(，CF(En)4、不确定性的传递算法结论H的可信度计算公式：5、结论不确定性的合成算法设有如下知识：IF E1 THEN H ( CF(H, E1) )IF E2 THEN H ( CF(H, E2) )则结论H的综合可信度可按如下步骤算出：（1）首先