人工智能导论实验指导书

《人工智能导论实验指导书》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验一基本的搜索技术【实验目的】通过运行演示程序，理解深度优先、广度优先、A*算法的原理和运行过程。【实验内容】1.分别以深度优先、广度优先、A*算法为例演示搜索过程2.观察运行过程记录搜索顺序3.设置不同属性，观察和记录搜索过程的变化4.分析不同算法的特点【实验原理】在知识不完全时，一般不存在成熟的求解算法可以利用，只有利用已有的知识摸索前进，从许多可能的解中寻找真正的解这就是搜索。即使对于结构性能较好，理论上有算法可依的问题，由于问题本身的复杂性以及计算机在时间、空间上的局限性，往往也需要通过搜索来进行求解。总的来说搜索策略分为两

2、大类：盲目搜索和启发式搜索一、无信息的搜索策略——盲目搜索在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随即调用操作算子）进行的搜索，它能快速地运用一个操作算子。盲目搜索中，由于没有可参考的信息，因此只要能匹配的操作算子都须运用，这会搜索更多的状态。最重要的宽度优先和深度优先是最重要的盲目搜索方法。1.宽度优先搜索：从根结点出发，按从低到高的层次顺序搜索，同一层的结点按固定的顺序（例如从左到右、从右到左）搜索。宽度优先总是先搜索到距离最近的目标结点。宽度优先搜索不适合用于分支较多的情况。2.深度优先搜索：用回溯的思想搜

3、索图。深度优先搜索适用于分支较多而层次较浅的情况。二、利用知识引导搜索——启发式搜索16盲目搜索复杂度很大，为了提高算法效率，应该具体问题具体分析，利用与问题有关的信息，从中得到启发而来引导搜索，以达到减少搜索量的目的，这就是启发式搜索。启发信息：(1)陈述性启发信息：一般被用于更准确、更精炼地描述状态，使问题的状态空间缩小,如待求问题的特定状况等属于此类信息(2)过程性启发信息：一般被用于构造操作算子，使操作算子少而精如一些规律性知识等属于此类信息(3)控制性启发信息：如何选择操作算子控制性启发信息往往被反映在估价函数之中。估价函数

4、的任务就是估计待搜索结点的“有希望”程度(或者说估计操作算子的“性能”)，并依此给它们排定次序。估价一个结点的价值，必须综合考虑两方面的因素：已经付出的代价(实际)和将要付出的代价(估计)f(n)=g(n)+h(n)采用这种估价函数的搜索叫A搜索。令h*(n)为n到目的结点的实际最小代价，如果对任意节点n均有h(n)≤h*(n)，则此时的A算法为A*算法。如某一问题有解，那么利用A*搜索算法对该问题进行搜索则一定能搜索到解，并且一定能搜索到最优的解而结束。这三种搜索算法都使用了两张表来记录状态信息：在open表中保留所有已生成而子状态

5、未扩展的状态；在closed表中记录已扩展过子状态的状态。广度优先搜索算法中的open表采用的是先进先出的“队列”。深度优先搜索算法中的open表采用的是后进先出的“栈”。启发式搜索算法中的open表中的元素是按启发估价函数值的大小排列的一个表，每次从表中优先取出启发估价函数值最小的状态加以扩展。同时并不丢弃其它的状态，而把它们保留在open表中。【实验步骤】1.浏览器打开下面网址，单击“StartApplet”按钮进入演示系统http://cai.csu.edu.cn/jpkc/rengongzhineng/rengongzhine

6、ng/search/search.html16图1演示系统图2162.单击主菜单中“File”→“LoadSampleGraph”，载入一个例子（例如“简单搜索树”），如图2红色椭圆标注，激活左侧“create”卡，鼠标指针指向右侧图中的结点或边，右击弹出菜单，单击“Properties”（即属性），可以查看或修改结点或边的属性。结点的heuristics属性表示结点的启发值，边的Edgecost属性表示边的代价。（A*算法中结点的估价函数值为从开始结点到该结点所有边的代价和再加上该结点的启发值。SABb85553图3如图3所示B的估

7、价值为13。）3.查看并记录所有结点的启发值和边的代价。4.激活左侧的“Solved”卡，如图4红色椭圆标注图4165.单击主菜单中“SearchAlgorithms”，分别选定“DepthFirst”、“BreadthFirst”、“A*”。重复单击左侧“Step”按钮（图4蓝色椭圆标注），直到右侧图中所有结点访问完毕。记录访问的结点顺序，并与自己预测的深度优先、宽度优先、A*的搜索顺序比较。（注：运行过程中红色的结点保存于closed表中，绿色的结点保存于open表中，蓝色的结点表示新展开的结点）6.单击主菜单中“File”→“C

8、reatenewGraph”，激活左侧“create”卡，新建一个图。分别选定“DepthFirst”、“BreadthFirst”、“A*”，进行搜索，记录搜索顺序，并与自己预测的深度优先、宽度优先、A*的搜索顺序比较