搜索
人工智能实验计算机科学与技术必修实验一产生式系统实验一、实验目的：复习产生式系统相关内容，熟悉和掌握产生式系统的运行机制，掌握基于规则推理的基本方法，能够应用产生式系统解决简单问题的方法。二、实验原理产生式系统用来描述若干个不同的以一个基本概念为基础的系统，这个基本概念就是产生式规则或产生式条件和操作对。在产生式系统中，论域的知识分为两部分：用事实表示静态知识；用产生式规则表示推理过程和行为。三、实验条件：1、PC机2、Windows操作系统平台3、VC集成开发环境四、实验内容：1、问题描述：设有N(本次设计控制在1-9之间，下同)个传教士和N个野人同在河的左岸，他们都要到对岸去；河里只有一条船，他们都会划船，但每次渡船至多只能乘N人；如果在任何一边河岸上，野人的数量超过传教士，野人就要吃掉传教士，问怎样才能用船将N个传教士和N个野人从左岸都渡到右岸，又不会发生传教士被吃的事件呢？2.建造产生式系统（包括规则库和事实库），然后进行推理，即可以自己输入任何的规则和事实，并基于这种规则和事实进行推理。五、实验步骤：1.数学模型描述：设计该问题的状态。使用三元组表示某一时刻传教士，野人，渡船情况，(左岸牧师数，左岸野人数，船的位置)。其中：左岸牧师数、左岸野人数取值范围为1－9之间；船的位置取值范围为0-1，0代表左岸，1代表右岸。2.定义初始状态和目标状态。根据数学模型描述，初始状态为（N，N，1），目标状态为（0，0，0）。3.定义产生式规则库。根据系统设计的规则要求列出所有合法的状态转变过程。基本思想：树的按层次遍历算法。由初始状态开始按层次逐个生成符合规则的产生式规则。4.控制策略应用深度优先搜索方式在规则库中查找答案。控制策略用于整个的推理过程实现，本次设计的搜索算法为图搜索策略中的深度优先搜索方式。实验结论：包括做实验的目的、方法、过程等，具体要写成实验报告，如下图所示。姓名李进东年级13Y3057专业计算机日期2014.6.3实验目的复习产生式系统相关内容，熟悉和掌握产生式系统的运行机制，掌握基于规则推理的基本方法，能够应用产生式系统解决简单问题的方法。推理方法□√正向推理□反向推理建立规则库建立事实库P10if(M,C,B=1)then(M–1,C,B–1)P01if(M,C,B=1)then(M,C–1,B–1)P11if(M,C,B=1)then(M–1,C–1,B–1)P20if(M,C,B=1)then(M–2,C,B–1)P02if(M,C,B=1)then(M,C–2,B–1)Q10if(M,C,B=0)then(M+1,C,B+1)Q01if(M,C,B=0)then(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人，野人过去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可合一，s称为其合一元。三、实验条件：1.合一演示程序。2.IE5.0以上，可以上Internet。四、实验内容：理解合一原理，熟悉对可合一文字进行合一的方法。五、实验步骤：1.对测试用例进行试验。进入演示程序，点击“合一测试”，得到合一结果。2.自定义待合一文字。点击“合一测试”验证合一概念。3.语法检查。点击“语法检查”检查输入谓词公式的语法错误。如无错误，则依次点击步骤按钮进行消解。4.重复运行2、3步，熟悉消解原理和消解过程。六、实验报告：谓词公式合一实验目的理解代换、合一的概念，掌握对文字进行代换的方法；能够判断文字L1和L2经过执行某个代换s是否可合一。实验步骤1.对测试用例进行试验。进入演示程序，点击“合一测试”，得到合一结果。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｝使得θ=σ·λ实验三子句归结与合一一、实验目的：理解含有变量的子句如何使用消解规则，掌握子句消解的原理和规则，能熟练进行任意两个子句的消解，了解消解推理的某些常用规则。二、实验原理：对子句集进行消解推理，得到相应的结论。为了对含有变量的子句使用消解规则，我们必须找到一个置换，作用于父辈子句使其含有互补文字。消解两个子句时，可能有一个以上的消解式，不过，在任何情况下最多有有限个消解式。三、实验条件子句归结与合一演示程序。四、实验内容：1.运行并观察演示实例。2.输入新的子句，检查消解结果。3.根据消解过程理解消解原理和常用规则。五、实验步骤：1.默认示例演示。进入演示实例，点击“演示实例1”，然后点击“开始消解”，得到消解结果。2.分别运行“演示实例2”和“演示实例3”，观察消解结果，理解常用消解规则的应用。3.自定义消解子句。点击“系统重置”按钮，再通过键盘与两个按钮“～”与“∨”输入合法的子句，点击“加入子句集”加入子句集，点击“开始消解”，观察消解结果。4.重复步骤3，多次输入不同子句进行消解，熟悉消解过程。六、实验结论：1.熟悉消解过程，理解子句消解规则。2.给出自己输入的待消解子句、消解结果和详细过程。子句归结与合一实验目的理解含有变量的子句如何使用消解规则，掌握子句消解的原理和规则，能熟练进行任意两个子句的消解，了解消解推理的某些常用规则。实验步骤1.默认示例演示。进入演示实例，点击“演示实例1”，然后点击“开始消解”，得到消解结果。2.分别运行“演示实例2”和“演示实例3”，观察消解结果，理解常用消解规则的应用。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/y}T3:(T2,T1)□{B/w,C/z}有效推理路径：C2:(C0,C0)P(A,w)C1:(C0,C0)～P(x,y)∨～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数码难题演示程序。2.IE5.0以上，可以上Internet。三、实验内容：1.分别以8数码和15数码为例实际求解A*算法。2.画出A*算法求解框图。3.分析估价函数对搜索算法的影响。4.分析A*算法的特点。四、实验步骤：1.开始演示。进入N数码难题演示程序，可选8数码或者15数码，点击“选择数码”按钮确定。第一次启动后，点击两次“缺省”或者“随机”按钮，才会出现图片。2.点击“缺省棋局”，会产生一个固定的初始节点。点击“随机生成”，会产生任意排列的初始节点。3.算法执行。点击“连续执行”则程序自动搜索求解，并演示每一步结果；点击“单步运行”则每次执行一步求解流程。“运行速度”可自由调节。4.观察运行过程和搜索顺序，理解启发式搜索的原理。在下拉框中选择演示“15数码难题”，点击“选择数码”确定选择；运行15数码难题演示实例。5.算法流程的任一时刻的相关状态，以算法流程高亮、open表、close表、节点静态图、当前扩展节点移动图等5种形式在按钮上方同步显示，便于深入学习理解A*算法。6.根据程序运行过程画出A*算法框图。五、实验报告要求：1.A*算法流程图和算法框图。2.试分析估价函数的值对搜索算法速度的影响。3.根据A*算法分析启发式搜索的特点。搜索算法的实现实验目的熟悉和掌握广度优先、深度优先及启发式搜索的定义、估价函数涵义及作用，掌握算法实现方法，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。实验步骤1.开始演示。进入N数码难题演示程序，可选8数码或者15数码，点击“选择数码”按钮确定。第一次启动后，点击两次“缺省”或者“随机”按钮，才会出现图片。2.点击“缺省棋局”，会产生一个固定的初始节点。点击“随机生成”，会产生任意排列的初始节点。3.算法执行。点击“连续执行”则程序自动搜索求解，并演示每一步结果；点击“单步运行”则每次执行一步求解流程。“运行速度”可自由调节。4.观察运行过程和搜索顺序，理解启发式搜索的原理。在下拉框中选择演示“15数码难题”，点击“选择数码”确定选择；运行15数码难题演示实例。5.算法流程的任一时刻的相关状态，以算法流程高亮、open表、close表、节点静态图、当前扩展节点移动图等5种形式在按钮上方同步显示，便于深入学习理解A*算法。6.根据程序运行过程画出A*算法框图。实验结果分析估价函数对搜索算法的影响：估价函数就是评价函数，它用来评价子结点的好坏，因为准确评价是不可能的，所以称为估值。这就是我们所谓的有信息搜索。如果估值函数只考虑结点的某种性能上的价值，而不考虑深度，比较有名的就是有序搜索（Ordered-Search），它着重看好能否找出解，而不看解离起始结点的距离（深度）。如果估值函数考虑了深度，或者是带权距离（从起始结点到目标结点的距离加权和），那就是A*如果不考虑深度，就是说不要求最少步数，移动一步就相当于向后多展开一层结点，深度多算一层，如果要求最少步数，那就需要用A*。简单的来说A*就是将估值函数分成两个部分，一个部分是路径价值，另一个部分是一般性启发价值，合在一起算估整个结点的价值，考虑到八数码问题的特点，在本实验中使用A*算法求解。分析A*算法的特点：A*搜索是一种效的搜索算法，它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价：f(n)=g(n)+h(n)。当h(n)是可采纳时，使用Tree-Search的A*算法将是最优的。实验五博弈树的启发式搜索一、实验目的：内容为极大极小搜索和α—β剪枝技术。极大极小搜索方法表示：对博弈树中的“或”节点，选其子节点中一个最大的得分作为父节点的得分，即选一个对自己最有利的方案；对“与”节点，选