人工智能导论实验指导书

1 实验一 基本的搜索技术 【实验目的】 通过运行演示程序，理解深度优先、广度优先、A*算法的原理和运行过程。

【实验内容】 1. 分别以深度优先、广度优先、A*算法为例演示搜索过程 2. 观察运行过程记录搜索顺序 3. 设置不同属性，观察和记录搜索过程的变化 4. 分析不同算法的特点

【实验原理】 在知识不完全时，一般不存在成熟的求解算法可以利用，只有利用已有的知识摸索前进，从许多可能的解中寻找真正的解这就是搜索。即使对于结构性能较好，理论上有算法可依的问题，由于问题本身的复杂性以及计算机在时间、空间上的局限性，往往也需要通过搜索来进行求解。 总的来说搜索策略分为两大类：盲目搜索和启发式搜索 一、无信息的搜索策略——盲目搜索 在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随即调用操作算子）进行的搜索，它能快速地运用一个操作算子。盲目搜索中，由于没有可参考的信息，因此只要能匹配的操作算子都须运用，这会搜索更多的状态。最重要的宽度优先和深度优先是最重要的盲目搜索方法。 1. 宽度优先搜索：从根结点出发，按从低到高的层次顺序搜索，同一层的结点按固定的顺序（例如从左到右、从右到左）搜索。宽度优先总是先搜索到距离最近的目标结点。宽度优先搜索不适合用于分支较多的情况。 2. 深度优先搜索：用回溯的思想搜索图。深度优先搜索适用于分支较多而层次较浅的情况。 二、利用知识引导搜索——启发式搜索 盲目搜索复杂度很大，为了提高算法效率，应该具体问题具体分析，利用与问题有关的信息，从中得到启发而来引导搜索，以达到减少搜索量的目的，这就 2

是启发式搜索。 启发信息： (1) 陈述性启发信息：一般被用于更准确、更精炼地描述状态，使问题的状态空间缩小,如待求问题的特定状况等属于此类信息 (2) 过程性启发信息：一般被用于构造操作算子，使操作算子少而精 如一些规律性知识等属于此类信息 (3) 控制性启发信息：如何选择操作算子 控制性启发信息往往被反映在估价函数之中。估价函数的任务就是估计待搜索结点的“有希望”程度(或者说估计操作算子的“性能”)，并依此给它们排定次序。 估价一个结点的价值，必须综合考虑两方面的因素：已经付出的代价(实际)和将要付出的代价(估计) f (n) = g (n) + h (n) 采用这种估价函数的搜索叫A搜索。令h*(n)为n到目的结点的实际最小代价，如果对任意节点n均有h(n)≤h*(n)，则此时的A算法为A*算法。 如某一问题有解，那么利用A*搜索算法对该问题进行搜索则一定能搜索到解，并且一定能搜索到最优的解而结束。 这三种搜索算法都使用了两张表来记录状态信息：在open表中保留所有已生成而子状态未扩展的状态；在closed表中记录已扩展过子状态的状态。 广度优先搜索算法中的open表采用的是先进先出的“队列”。 深度优先搜索算法中的open表采用的是后进先出的“栈”。 启发式搜索算法中的open表中的元素是按启发估价函数值的大小排列的一个表，每次从表中优先取出启发估价函数值最小的状态加以扩展。同时并不丢弃其它的状态，而把它们保留在open表中。

【实验步骤】 1. 浏览器打开下面网址，单击“Start Applet”按钮进入演示系统 http://cai.csu.edu.cn/jpkc/rengongzhineng/rengongzhineng/search/search.html 3

图1 演示系统

图2 4

2. 单击主菜单中“File”→“Load Sample Graph”，载入一个例子（例如“简单搜索树”），如图2红色椭圆标注，激活左侧“create”卡，鼠标指针指向右侧图中的结点或边，右击弹出菜单，单击“Properties”（即属性），可以查看或修改结点或边的属性。结点的heuristics属性表示结点的启发值，边的Edge cost属性表示边的代价。

（A*算法中结点的估价函数值为从开始结点到该结点所有边的代价和再加

上该结点的启发值。

如图3所示B的估价值为13。） 3. 查看并记录所有结点的启发值和边的代价。 4. 激活左侧的“Solved”卡，如图4红色椭圆标注

S A B

8 5 5 5 3

图3

图4 5

5. 单击主菜单中“Search Algorithms”，分别选定“Depth First”、“Breadth First”、“A*”。重复单击左侧“Step”按钮（图4蓝色椭圆标注），直到右侧图中所有结点访问完毕。记录访问的结点顺序，并与自己预测的深度优先、宽度优先、A*的搜索顺序比较。

（注：运行过程中红色的结点保存于closed表中，绿色的结点保存于open表中，蓝色的结点表示新展开的结点） 6. 单击主菜单中“File”→“Create new Graph”，激活左侧“create”卡，新建一个图。分别选定“Depth First”、“Breadth First”、“A*”，进行搜索，记录搜索顺序，并与自己预测的深度优先、宽度优先、A*的搜索顺序比较。

S(4)

A(6) B(4) C(6) D(5) E(5) F(5) G(6) H(6) I(5) J(7) K(5) L(5) M(7) 6

实验二 传教士和野人问题 【实验目的】 通过具体问题的编程求解，了解人工智能的基本解决方法；使用一种搜索策略，以加深理解。

【实验内容】 设在河的一岸有三个野人、三个传教士和一条船，要用这条船把所有的人运到河对岸，但受以下条件的约束： (1) 传教士和野人都会划船，但每次船上至多可载两个人； (2) 二是在河的任一岸，如果野人数目超过修道士数，传教士会被野人吃掉。 (3) 如果野人会服从任何一次过河安排 编程实现一个确保传教士和野人都能过河，且没有传教士被野人吃掉的安全过河计划。

【实验原理】 传教士和野人问题是一个经典的智力游戏问题。有N个传教士和N个野人来到河边准备渡河，河岸(甲岸和乙岸)有一条船，每次至多可供k人乘渡。应如何规划摆渡方案，使得任何时刻，在河的两岸以及船上的野人数目总是不超过传教士的数目。即求解传教士和野人从左岸全部摆渡到右岸的过程中，任何时刻满足M（传教士数）≥C（野人数）和M＋C≤k的摆渡方案。 设N＝3，k＝2，则给定的问题可用下图表示，图中L和R表示左岸和右岸，B＝1或0分别表示有船或无船。约束条件是：两岸上M≥C，船上M＋C≤2

图1 M－C问题实例 7

简单的分析，总共有10种可能的操作： 两个野人过河（从甲到乙，从乙到甲)

两个传教士过河从（从甲到乙，从乙到甲) 一个传教士和一个野人过河（从甲到乙，从乙到甲) 一个野人过河（从甲到乙，从乙到甲) 一个传教士过河（从甲到乙，从乙到甲) 但对于一个具体状态，只有5种可能的操作（从甲到乙或从乙到甲)。 先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸： 初始状态：甲岸，3野人，3牧师； 乙岸，0野人，0牧师； 船停在甲岸，船上有0个人； 目标状态：甲岸，0野人，0牧师； 乙岸，3野人，3牧师； 船停在乙岸，船上有0个人； 整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）： 渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师 算符知道以后，剩下的核心问题就是搜索方法了，本文以深度优先搜索为基础，通过一个FindNext(…)函数找出下一步可以进行的渡河操作，如果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process(…)函数递规调用FindNext(…)，一级一级的向后扩展。 搜索中的算符采用下面的规则固定排序，合理的排序能更快的搜索到较优的解： 甲岸一次运走的人越多越好（即甲岸运多人优先），同时野人优先运走；乙岸一次运走的人越少越好（即乙岸运少人优先），同时牧师优先运走； 同时注意下面两点： 1. 不能重复上次渡船操作（通过链表中前一操作比较），避免进入死循环; 2. 任何时候河两边的野人和牧师数均分别大于等于0且小于等于3； 8

【实验过程】 设计程序求解传教士和野人问题。附录C++程序及注释如下：

//wildman.cpp #include "iostream.h" typedef struct _riverside // 岸边状态类型 { int wildMan; // 野人数 int churchMan; // 牧师数 }RIVERSIDE; typedef struct _boat // 船的状态类型 { int wildMan; // 野人数 int churchMan; // 牧师数 }BOAT; typedef struct _question // 整个问题状态 { RIVERSIDE riverSide1; // 甲岸 RIVERSIDE riverSide2; // 乙岸 int side; // 船的位置, 甲岸为-1, 乙岸为1 BOAT boat; // 船的状态 _question* pPrev; // 指向前一渡船操作 _question* pNext; // 指向后一渡船操作 }QUESTION;

//函数定义 bool Process(QUESTION* pQuest); bool FindNext(QUESTION* pQuest); void VisitList(QUESTION* pQuest); //遍历链表输出结果 //

int main() { // 初始化 QUESTION* pHead = new QUESTION; pHead->riverSide1.wildMan = 3; pHead->riverSide1.churchMan = 3;