苏州大学《人工智能》实验指导书

《苏州大学《人工智能》实验指导书》由会员分享，可在线阅读，更多相关《苏州大学《人工智能》实验指导书（26页珍藏版）》请在金锄头文库上搜索。

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) 单调性一个启发函数 h 是单调的，如果a) 对所

3、有的状态n.和n.,其中n.是n.的子孙，h(n.)-h(n.)i j j i i j5斑吧),其中costgnj)是从ni到n.实际代价。b) 目标状态的启发函数值为 0,即 h(Goal)=0. 具有单调性的启发式搜索算法在对状态进行扩展时能保证所有被扩 展的状态的f值是单调递增(不减)。(3) 信息性比较两个启发策略hl和h2,如果对搜索空间中的任何一个状态n 都有hl(n) Wh2(n),就说h2比hl具有更多的信息性。一般而言，若搜索策略h2比hl有更多的信息性，则h2比hl考察的 状态要少。但必须注意的是更多信息性需要更多的计算时间,从而有 可能抵消减少搜索空间所带来的益处。3.

4、常用的启发式搜索算法(1)局部择优搜索算法(瞎子爬山法)瞎子爬山法是最简单的启发式算法之一。该算法在搜索过程中 扩展当前节点并估价它的子节点。最优的子节点别选择并进一步扩 展；该子节点的兄弟节点和父节点都不再被保留。当搜索到达一种状 态，该状态比它的所有子状态都要好，则搜索停止。因此，该算法的 估价函数可表示为f(n) = h(n)。在一个限定的环境下，瞎子爬山法可能会极大的提高搜索的效 率，但是对整个搜索空间而言，可能得不到全局最优解。 (2)最好优先搜索法(有序搜索法)该算法的估价函数采用f(n) = g(n) + h(n),在搜索过程中算法使 用OPEN表和CLOSE表来记录节点信息：O

5、PEN表中保留所有已生成 而未考察的节点；CLOSE表中保留所有已访问过的节点。算法在每 一次搜索过程中都会对OPEN表中的节点按照每个节点的f值进行排 序，选择f值最小节点进行扩展。算法的描述如下： 把起始节点S放到OPEN表中，计算f(S),并把其值与节点S联 系起来。 若OPEN是个空表，则算法失败退出，无解。 从OPEN表中选择一个f值最小的节点i。结果有几个节点合 格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其 中任一个节点作为节点i。 把节点i从OPEN表中移出，并把它放入到CLOSED的扩展节点 表中。 若节点i是个目标节点，则成功退出，求得一个解。 扩展i，生成其

6、全部后继节点。对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表中，则把它移回OPE N表。 转向。四、实验内容： 问题描述：用启发式搜索方法求解下列九宫问题1) 状态表示的数据结构2) 状态扩展

7、规则的表示3) 搜索产生的状态空间图(4) OPEN表和CLOSE表变化过程5) 程序清单(6) 实验结果讨论a你所采用的估价函数f(n) = g(n) + h(n)中，g(n)和h(n)的主要作用是什么？b 结合本实验举例说明不同启发策略对实验的效果有何影响？c 若问题的初始状态是随机产生的，你的实验程序应该如何改进？实验二基于产生式系统的问题求解一、实验目的：熟悉和掌握产生式系统的构成和运行机制，掌握基于规则推理的 基本方法和技术。二、实验方法：1.先熟悉产生式系统的基本概念；2.用C、C+或JAVA 语言编程实现实验内容。三、实验背景知识：产生式系统（Production system）

8、首先由波斯特（Post）于1943 年提出的产生式规则（Production rule）而得名，他们用这种规则 对符号串进行置换运算，后来，美国的纽厄尔和西蒙利用这个原理建 立了一个人类的认知模型（ 1 965年） ，同年，斯坦福大学利用产生式 系统结构设计出第一个专家系统DENDRAL。产生式系统用来描述若干个不同的以一个基本概念为基础的系 统。这个基本概念就是产生式规则或产生式条件和操作对象的概念。在产生式系统中，论域的知识分为两部份：（1）事实：用于表示静态知识，如事物、事件和它们之间的关 系；（2）规则：用于表示推理过程和行为一个产生式系统由三个部分组成，如图所示：1）总数据库：用来存

9、放与求解问题有关的数据以及推理过程 环境的当前状态的描述。2）产生式规则库：主要存放问题求解中的规则。（3）控制策 略：其作用是说明下一步应该选用什么规则，也就是说如 何应用规则。通常从选择规则到执行操作分三步：（1）匹配：把当前数据库和规则的条件部分相匹配。如果两者 完全匹配，则把这条规则称为触发规则。（2）冲突解决：当有一个以上的规则条件部分和当前数据库相 匹配时，就需要解决首先使用哪一条规则冲突解决。1）专一性排序：如果某一规则的条件部分比另一条规则的条件部分所规定的情况更为专门，则这条规则有较高的优先权。2）规则排序：如果规则编排顺序就表示了启用的优先级，则称之为排序。3）数据排序：把

10、规则条件部分的所有条件按优先级次序编排 起来，运行时首先使用在条件部分包含较高优先级数据的规则。4） 规模排序：按规则的条件部分的规模排列优先级，优先使用被满足的 条件较多的规则。5）就近排序：把最近使用的规则放在最优先的位置。6）上下文限制：把产生式规则按他们所描述的上下文分组， 也就是说按上下文对规则分组，在某种上下文条件下，只能从与其相 对应的那组规则中选择可应用的规则。7）使用次数排序：把使用频率较高的排在前面。（3）操作：执行规则的操作部分，经过修改以后，当前数据库 将被修改。四、实验内容： 问题描述：用基于产生式系统的方法求解传教士和野人问题 有 N 个传教士和 N 个野人来到河边

11、准备渡河，河岸有一条船， 每次至多可供 K 个乘渡，问传教士为了安全起见，应如何规划摆渡 方案，使得任何时刻，河岸两边以及船上的野人数目总是不超过传教 土的数目，即求解传教士和野人从左岸全部摆渡到右岸的过程中，任 何时刻满足M （传教士数）$C （野人数）和M+CWK的摆渡方案。五、问题（1）问题状态的表示（2）数据库描述（3）规则库的描述（4）控制机制（5）状态空间图（6）程序清单（7）实验结果讨论a. 你采用何种策略来控制产生式系统的搜索？b你能否对产生式系统进行改进，若能请把你的想法写下来。实验三 归结原理一、实验目的熟悉和掌握归结原理的基本思想和基本方法，通过实验培养学生 利用逻辑方法

12、表示知识，并掌握采用机器推理来进行问题求解的基本 方法。二、实验要求1. 先熟悉归结原理的基本思想和归结否证的步骤；2. 用C、C+、JAVA或Prolog语言编程实现实验内容；3. 利用所学的知识及实验结果，来完成实验报告的各项内容。三、实验背景知识归结是一种应用于谓词演算中的定理证明技术，从60 年代中期 开始，它就成为人工智能问题求解研究的一个组成部分。归结原理描 述了如何用最少的合一次数在一个子句数据库中发现矛盾的方法。归 结否证定理证明的方法是，对所要证明的命题取反，把它加到一个已 知为真的公里集中，然后用归结推理规则证明这将导致一个矛盾，一 旦定理证明程序证明了否定目标与已知的公理

13、集合不一致，就能推导 出原来的目标与公理集是一致的。这就证明了该定理。归结否证包含以下步骤：（1）把前提或公理转换成子句形式；（2）把求证目标的否定的子句形式加到公理集合中；（3）对所有这些子句进行归结，产生它们的逻辑结果子句；（4）用产生空子句的方法来得出矛盾；（5）否定目标的否证在用于产生空子句的代换下为真。如何把前提或公理化为子句形式是进行归结的前提，其过程包含 如下步骤：（1）消去蕴涵符号用PVQ替换P-Q（2）减少否定符号的辖域 每个否定符号最多只作用在一个谓词符号上（3）对变量标准化每个变量仅受一个量词作用（4）消去存在量词若存在量词前没有全称量词，则直接消去;否则，要Skolem

14、。 化。（5）化为前束范式 前束范式：一个公式，如果量词均非否定地出现在公式最前面，其辖域延伸到整个公式的末尾，且在公式中仅含 有联结词，V,A，则称此种形式为前束范式。前束范式 = （前缀） （母式）（6）化母式为合取范式（7）消去全称量词（8）消去连接词符号人用A, B替代（AAB）（9）将分离的变元归一化四、实验内容问题描述：四对夫妇中，王结婚时，周送了礼；周和钱是同一排 球队的队员；李的爱人是陈的爱人的表哥；陈夫妇与邻居吵架时，徐、 周、吴的爱人都去助战；李、徐、周结婚前住在同一宿舍，试用归结 原理求王、周、钱、陈、李、徐、吴、孙几人谁和谁是夫妇。五、问题（1）利用逻辑表达式对问题的前

15、提和结论进行描述。（2）将前提和结论的否定化为子句形式。（3）写出问题的子句集形式。（4）利用归结原理对问题进行求解，写出求解过程。（5）编写程序进行问题求解，列出程序清单。（6）写出实验结果。（7）实验结果讨论：你在实验中采用的归结策略是何种策略，能否 有该进？如何改进？实验四 简单遗传算法一、实验目的：熟悉和掌握遗传算法的基本思想和基本方法，通过实验培养学生 利用遗传算法进行问题求解的基本技能，并且了解进化计算其他分支 的基本思想和基本方法。二、实验方法：1.先熟悉进化计算中遗传算法的基本思想和流程；2.用C、C+、JAVA或Prolog语言编程实现实验内容。三、实验背景知识：生物群体的生存过程普遍遵循达尔文的物竞天择、适者生存的进 化准则。群体中的个体根据对环境的适应能力而被大自然所选择或淘 汰。进化计算(evolu tionary compu tat ion, EC)就是通过模拟自然物 群进化的一类非常鲁棒的优化算法，它们模拟群体(其中组成群体的 每个个体表示搜索问题解空间中的一个