《《人工智能》实验指导书》由会员分享，可在线阅读，更多相关《《人工智能》实验指导书（24页珍藏版）》请在金锄头文库上搜索。
1、 人工智能 实验指导书专业年级姓名学号指导老师实验室使用日期实验一实验一 启发式搜索启发式搜索一、实验目的：一、实验目的：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用 A算法求解九宫问题，理解求解流程和搜索顺序。二、实验方法：二、实验方法：1.先熟悉启发式搜索算法；2.用 C、C+或 JAVA语言编程实现实验内容。三、实验背景知识：实验背景知识：1.估价函数估价函数在对问题的状态空间进行搜索时， 为提高搜索效率需要和被解问题的解有关的大量控制性知识作为搜索的辅助性策略。 这些控制信息反映在估价函数中。估价函数的任务就是估计待搜索节点的重要程度， 给这些节点排定次序。估价函数可以是任意
2、一种函数，如有的定义它是节点 x 处于最佳路径的概率上，或是 x 节点和目标节点之间的距离等等。在此，我们把估价函数 f(n)定义为从初始节点经过 n 节点到达目标节点的最小代价路径的代价估计值，它的一般形式是：f(n) = g(n) + h(n)其中 g(n)是从初始节点到节点 n 的实际代价，g(n)可以根据生成的搜索树实际计算出来；h(n)是从 n 到目标节点的最佳路径的代价估计，h(n)主要体现了搜索的启发信息。2. 启发式搜索过程的特性启发式搜索过程的特性（1）可采纳性当一个搜索算法在最短路径存在的时候能保证能找到它， 我们就称该算法是可采纳的。所有 A*算法都是可采纳的。（2）单调
3、性一个启发函数 h 是单调的，如果a）对所有的状态 ni和 nj，其中 nj是 ni的子孙，h(ni)- h(nj)cost(ni,nj),其中 cost(ni,nj)是从 ni到 nj实际代价。b）目标状态的启发函数值为 0，即 h(Goal)=0.具有单调性的启发式搜索算法在对状态进行扩展时能保证所有被扩展的状态的f值是单调递增（不减） 。（3）信息性比较两个启发策略h1和h2，如果对搜索空间中的任何一个状态n都有h1(n) h2(n)，就说h2比h1具有更多的信息性。一般而言，若搜索策略h2比h1有更多的信息性，则h2比h1考察的状态要少。但必须注意的是更多信息性需要更多的计算时间，从而
4、有可能抵消减少搜索空间所带来的益处。3.常用的启发式搜索算法（1）局部择优搜索算法（瞎子爬山法）瞎子爬山法是最简单的启发式算法之一。该算法在搜索过程中扩展当前节点并估价它的子节点。最优的子节点别选择并进一步扩展；该子节点的兄弟节点和父节点都不再被保留。当搜索到达一种状态，该状态比它的所有子状态都要好，则搜索停止。因此，该算法的估价函数可表示为f(n) = h(n)。在一个限定的环境下，瞎子爬山法可能会极大的提高搜索的效率，但是对整个搜索空间而言，可能得不到全局最优解。（2）最好优先搜索法（有序搜索法）该算法的估价函数采用f(n) = g(n) + h(n)，在搜索过程中算法使用OPEN表和CL
5、OSE表来记录节点信息：OPEN表中保留所有已生成而未考察的节点；CLOSE表中保留所有已访问过的节点。算法在每一次搜索过程中都会对OPEN表中的节点按照每个节点的f值进行排序，选择f值最小节点进行扩展。算法的描述如下： 把起始节点S放到OPEN表中，计算f(S),并把其值与节点S联系起来。 若OPEN是个空表，则算法失败退出，无解。 从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i 。 把节点i从OPEN表中移出，并把它放入到CLOSED的扩展节点表中。 若节点i是个目标节点，则成功退出，求得一个解。
6、扩展i，生成其全部后继节点。对i的每个后继节点j：（a）计算f(j)。（b）如果j既不在OPEN表中，也不在CLOSED表中，则用估价函数f将其添加到OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。（c）如果j已则OPEN表中或CLOSED表中， 则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f的值。 若新的f值较小，则（i）以此值取代旧值。（ii）从j指向i，而不是指向它的父辈节点。（iii） 若节点j在CLOSED表中，则把它移回OPEN表。 转向。四、实验内容：四、实验内容：问题描述：问题描述：用启发式搜索方法求解下列九宫问题28316475五
7、、问题五、问题（1）状态表示的数据结构）状态表示的数据结构（2）状态扩展规则的表示）状态扩展规则的表示（3）搜索产生的状态空间图）搜索产生的状态空间图（4）OPEN表和表和CLOSE表变化过程表变化过程（5）程序清单）程序清单12384765（6）实验结果讨论）实验结果讨论a. 你所采用的估价函数f(n) = g(n) + h(n)中，g(n)和h(n)的主要作用是什么？b. 结合本实验举例说明不同启发策略对实验的效果有何影响？c. 若问题的初始状态是随机产生的，你的实验程序应该如何改进？实验二实验二 基于产生式系统的问题求解基于产生式系统的问题求解一、实验目的：一、实验目的：熟悉和掌握产生式
8、系统的构成和运行机制， 掌握基于规则推理的基本方法和技术。二、实验方法：实验方法：1.先熟悉产生式系统的基本概念；2.用 C、C+或 JAVA语言编程实现实验内容。三、实验背景知识：实验背景知识：产生式系统 （Production system） 首先由波斯特 （Post） 于 1943年提出的产生式规则（Production rule）而得名，他们用这种规则对符号串进行置换运算，后来，美国的纽厄尔和西蒙利用这个原理建立了一个人类的认知模型（1965 年） ，同年，斯坦福大学利用产生式系统结构设计出第一个专家系统 DENDRAL。产生式系统用来描述若干个不同的以一个基本概念为基础的系统。这个基
9、本概念就是产生式规则或产生式条件和操作对象的概念。在产生式系统中，论域的知识分为两部份：（1）事实：用于表示静态知识，如事物、事件和它们之间的关系；（2）规则：用于表示推理过程和行为一个产生式系统由三个部分组成，如图所示：（1）总数据库：用来存放与求解问题有关的数据以及推理过程环境的当前状态的描述。（2）产生式规则库：主要存放问题求解中的规则。（3）控制策略： 其作用是说明下一步应该选用什么规则， 也就是说如何应用规则。通常从选择规则到执行操作分三步：（1）匹配：把当前数据库和规则的条件部分相匹配。如果两者完全匹配，则把这条规则称为触发规则。（2）冲突解决：当有一个以上的规则条件部分和当前数据
10、库相匹配时，就需要解决首先使用哪一条规则冲突解决。1）专一性排序：如果某一规则的条件部分比另一条规则的条件部分所规定的情况更为专门，则这条规则有较高的优先权。2）规则排序：如果规则编排顺序就表示了启用的优先级，则称之为排序。3）数据排序：把规则条件部分的所有条件按优先级次序编排总数据库控制策略规则库起来，运行时首先使用在条件部分包含较高优先级数据的规则。4）规模排序：按规则的条件部分的规模排列优先级，优先使用被满足的条件较多的规则。5）就近排序：把最近使用的规则放在最优先的位置。6）上下文限制：把产生式规则按他们所描述的上下文分组，也就是说按上下文对规则分组，在某种上下文条件下，只能从与其相对
11、应的那组规则中选择可应用的规则。7）使用次数排序：把使用频率较高的排在前面。（3）操作：执行规则的操作部分，经过修改以后，当前数据库将被修改。四、四、实验内容：实验内容：问题描述：问题描述：用基于产生式系统的方法求解传教士和野人问题有 N 个传教士和 N 个野人来到河边准备渡河，河岸有一条船，每次至多可供 K 个乘渡，问传教士为了安全起见，应如何规划摆渡方案，使得任何时刻，河岸两边以及船上的野人数目总是不超过传教土的数目，即求解传教士和野人从左岸全部摆渡到右岸的过程中，任何时刻满足 M（传教士数）C（野人数）和 M+CK 的摆渡方案。五、问题五、问题（1 1）问题状态的表示）问题状态的表示（2
12、 2）数据库描述）数据库描述（3 3）规则库的描述）规则库的描述（4 4）控制机制）控制机制（5 5）状态空间图）状态空间图（6 6）程序清单）程序清单（7 7）实验结果讨论实验结果讨论a.a. 你采用何种策略来控制产生式系统的搜索？你采用何种策略来控制产生式系统的搜索？b b你能否对产生式系统进行改进，若能请把你的想法写下来。你能否对产生式系统进行改进，若能请把你的想法写下来。实验三实验三 归结原理归结原理一、实验目的一、实验目的熟悉和掌握归结原理的基本思想和基本方法， 通过实验培养学生利用逻辑方法表示知识， 并掌握采用机器推理来进行问题求解的基本方法。二、实验要求二、实验要求1.先熟悉归结
13、原理的基本思想和归结否证的步骤；2.用 C、C+、JAVA 或 Prolog语言编程实现实验内容；3.利用所学的知识及实验结果，来完成实验报告的各项内容。三、实验背景知识三、实验背景知识归结是一种应用于谓词演算中的定理证明技术，从 60 年代中期开始，它就成为人工智能问题求解研究的一个组成部分。归结原理描述了如何用最少的合一次数在一个子句数据库中发现矛盾的方法。 归结否证定理证明的方法是，对所要证明的命题取反，把它加到一个已知为真的公里集中，然后用归结推理规则证明这将导致一个矛盾，一旦定理证明程序证明了否定目标与已知的公理集合不一致， 就能推导出原来的目标与公理集是一致的。这就证明了该定理。归
14、结否证包含以下步骤：（1）把前提或公理转换成子句形式；（2）把求证目标的否定的子句形式加到公理集合中；（3）对所有这些子句进行归结，产生它们的逻辑结果子句；（4）用产生空子句的方法来得出矛盾；（5）否定目标的否证在用于产生空子句的代换下为真。如何把前提或公理化为子句形式是进行归结的前提， 其过程包含如下步骤：（1）消去蕴涵符号用 PQ 替换 PQ（2）减少否定符号的辖域每个否定符号 最多只作用在一个谓词符号上（3）对变量标准化每个变量仅受一个量词作用（4）消去存在量词若存在量词前没有全称量词， 则直接消去； 否则， 要Skolem。化。（5）化为前束范式前束范式：一个公式，如果量词均非否定地出
15、现在公式最前面，其辖域延伸到整个公式的末尾，且在公式中仅含有联结词 ，则称此种形式为前束范式。前束范式 = （前缀）（母式）（6）化母式为合取范式（7）消去全称量词（8）消去连接词符号用A，B替代（AB）（9）将分离的变元归一化四、实验内容四、实验内容问题描述问题描述：四对夫妇中，王结婚时，周送了礼；周和钱是同一排球队的队员； 李的爱人是陈的爱人的表哥； 陈夫妇与邻居吵架时， 徐、周、吴的爱人都去助战；李、徐、周结婚前住在同一宿舍，试用归结原理求王、周、钱、陈、李、徐、吴、孙几人谁和谁是夫妇。五、问题五、问题（1 1）利用逻辑表达式对问题的前提和结论进行描述。）利用逻辑表达式对问题的前提和结论
16、进行描述。（2 2）将前提和结论的否定化为子句形式。）将前提和结论的否定化为子句形式。（3 3）写出问题的子句集形式。）写出问题的子句集形式。（4 4）利用归结原理对问题进行求解，写出求解过程。）利用归结原理对问题进行求解，写出求解过程。（5 5）编写程序进行问题求解，列出程序清单。编写程序进行问题求解，列出程序清单。（6 6）写出实验结果。）写出实验结果。（7 7）实验结果讨论：）实验结果讨论：你在实验中采用的归结策略是何种策略，能否有该进？如何改进？实验四实验四 简单遗传算法简单遗传算法一、实验目的：一、实验目的：熟悉和掌握遗传算法的基本思想和基本方法， 通过实验培养学生利用遗传算法进行问题求解的基本技能， 并且了解进化计算其他分支的基本思想和基本方法。二、实验方法：实验方法：1.先熟悉进化计算中遗传算法的基本思想和流程；2.用 C、C+、JAVA 或 Prolog语言编程实现实验内容。三、实验背景知识：实验背景知识：生物群体的生存过程普遍遵循达尔文的物竞天择、
