人工智能实验报告模板.doc

《人工智能实验报告模板.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、人工智能实验报告姓名孙博宇学号班级数字1201指导教师于瑞云开设学期2015-2015第一学期实验题目实验一A*搜索解决罗马尼亚度假问题实验日期2015/05/05—2015/05/11评定成绩评定人签字评定日期东北大学软件学院一、实验目的A*搜索也使用启发式函数计算搜索空间。A*搜索与最佳优先搜索不同的是，它既是最优的，也是完备的。A*搜索解决罗马尼亚度假问题：二、实验内容与实验步骤图结构——地图#include"graph.h"优先队列——OPEN表#include"pqueue.h"数组或队列——CLOSED表#inc

2、lude"queue.h"堆栈——问题的最终解#include"stack.h"问题的最终解存在堆栈中。首先对地图中的点进行初始化，地址信息存放在OPEN表里，CLOSE表设置为空。当OPEN表中没满时循环操作A*搜索。A_Star_Search：A*算法最为核心的部分，就在于它的一个估值函数的设计上：f(n)=g(n)+h(n)其中f(n)是每个可能试探点的估值，它有两部分组成：一部分，为g(n)，它表示从起始搜索点到当前点的代价。另一部分，即h(n)，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值。A*算

3、法最为核心的过程，就在每次选择下一个当前搜索点时，是从所有已探知的但未搜索过点中(可能是不同层，亦可不在同一条支路上)，选取f值最小的结点进行展开。而所有“已探知的但未搜索过点”可以通过一个按f值升序的队列(即优先队列)进行排列。这样，在整体的搜索过程中，只要按照类似广度优先的算法框架，从优先队列中弹出队首元素（f值），对其可能子结点计算g、h和f值，直到优先队列为空(无解)或找到终止点为止。首先将起始结点S放入OPEN表，CLOSE表置空，算法开始时：1、如果OPEN表不为空，从表头取一个结点n，如果为空算法失败。2、n是

4、目标解吗？是，找到一个解（继续寻找，或终止算法）。3、将n的所有后继结点展开，就是从n可以直接关联的结点（子结点），如果不在CLOSE表中，就将它们放入OPEN表，并把S放入CLOSE表，同时计算每一个后继结点的估价值f(n)，将OPEN表按f(x)排序，最小的放在表头，重复算法，回到1。A*算法流程图：三、实验过程与分析//OPEN-->CLOSE，起点-->任意顶点g(n)-->目标顶点h(n)closedset:=theemptyset//已经被估算的节点集合openset:=setcontainingtheiniti

5、alnode//将要被估算的节点集合g_score[start]:=0//g(n)h_score[start]:=heuristic_estimate_of_distance(start,goal)//h(n)f_score[start]:=h_score[start]whileopensetisnotempty//若OPEN表不为空x:=thenodeinopensethavingthelowestf_score[]value//x为OPEN表中最小的ifx=goal//如果x是一个解returnreconstruct_p

6、ath(came_from,goal)//removexfromopensetaddxtoclosedset//x放入CLSOE表foreachyinneighbor_nodes(x)ifyinclosedsetcontinuetentative_g_score:=g_score[x]+dist_between(x,y)ifynotinopensetaddytoopensettentative_is_better:=trueelseiftentative_g_score

7、er:=trueelsetentative_is_better:=falseiftentative_is_better=truecame_from[y]:=xg_score[y]:=tentative_g_scoreh_score[y]:=heuristic_estimate_of_distance(y,goal)//x-->y-->goalf_score[y]:=g_score[y]+h_score[y]returnfailurefunctionreconstruct_path(came_from,current_node

8、)ifcame_from[current_node]issetp=reconstruct_path(came_from,came_from[current_node])return(p+current_node)elsereturntheemptypath四、实验结果总结一种具有f(n)=