人工智能实验报告： 搜索策略

《人工智能实验报告： 搜索策略》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、“人工智能”实验报告专业：班级：学号：姓名：2017年4月日实验一搜索策略（一）实验内容1.熟悉和掌握启发式搜索的定义、估价函数和算法过程；比较不同算法的性能。2.修改八数码问题或路径规划问题的源程序，改变其启发函数定义，观察结果的变化，分析原因。（二）实验思路1.利用已有程序“search.jar”，利用已有的“简单搜索树”图或自行构建一个图，选择DFS/BFS/LowestCostFirst/Best-First/HeuristicDepthFirst/A*等不同的搜索策略，观察程序运行中，OPEN表和CLOS

2、ED表的变化，观察搜索过程的变化，理解各个算法的原理。2.任选八数码问题或路径规划问题的源程序，思考程序如何解决该问题，并对其启发函数进行修改，观察结果的变化，并分析原因（三）程序清单此处我选择了路径规划问题：由于篇幅原因，只附上启发函数的定义部分。原启发函数：floatMapSearchNode::GoalDistanceEstimate(MapSearchNode&nodeGoal){floatxd=fabs(float(((float)x-(float)nodeGoal.x)));floatyd=fabs(f

3、loat(((float)y-(float)nodeGoal.y)));return(xd+yd);}第一次修改后的启发函数：floatMapSearchNode::GoalDistanceEstimate(MapSearchNode&nodeGoal){floatxd=fabs(float(((float)x-(float)nodeGoal.x)));floatyd=fabs(float(((float)y-(float)nodeGoal.y)));floatd=sqrt(xd*xd+yd*yd);returnd

4、;}第二次修改后的启发函数：floatMapSearchNode::GoalDistanceEstimate(MapSearchNode&nodeGoal){floatxd=fabs(float(((float)x-(float)nodeGoal.x)));floatyd=fabs(float(((float)y-(float)nodeGoal.y)));floatd=3*sqrt(xd*xd+yd*yd);returnd;}第三次修改后的启发函数：floatMapSearchNode::GoalDistanceE

5、stimate(MapSearchNode&nodeGoal){floatxd=fabs(float(((float)x-(float)nodeGoal.x)));floatyd=fabs(float(((float)y-(float)nodeGoal.y)));floatd=xd*xd+yd*yd;returnd;}（四）运行结果说明1.首先对实验内容1进行说明图一图一展示A*算法的搜索过程（此处的g(n),h(n)由系统自动给定），绿色表示可拓展节点（在OPEN表内），灰色表示已扩展结点（CLOSED表），没有

6、颜色表示未入表，红色代表当前路径由课上学习我们易知f(n)=g(n)+h(n)下面我们通过改变g(n)，h(n)来验证上式是否成立。图二①图二为图一的放大图，我们可以看出f(Node1)=g(Node1)+h(Node1)=26.9+56.8=83.7f(Node2)=g(Node2)+h(Node2)=34.2+31.5=65.7显然f(Node1)>f(Node2),因此由A*算法，我们选择Node2图三②在图三中，我修改了Node2的启发值，其他不变f(Node1)=g(Node1)+h(Node1)=26.

7、9+56.8=83.7f(Node2)=g(Node2)+h(Node2)=34.2+100.0=134.2显然f(Node1)

8、算法的确是根据f(n)的值来进行搜索的2.对实验内容2的说明实验内容2我一共做了三次启发函数值的修改①floatd=sqrt(xd*xd+yd*yd);②floatd=3*sqrt(xd*xd+yd*yd);③floatd=xd*xd+yd*yd;图五图五是未进行修改的结果，此时路径经过22个点，搜索了23个点未进行修改，原程序采用的是曼哈顿距离（Manha