人工智能实验报告模板

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

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

2、e.h"数组或队列——CLOSED表#include"queue.h"堆栈——问题的最终解#include"stack.h"问题的最终解存在堆栈中。第6页共6页人工智能实验报告首先对地图中的点进行初始化，地址信息存放在OPEN表里，CLOSE表设置为空。当OPEN表中没满时循环操作A*搜索。A_Star_Search：A*算法最为核心的部分，就在于它的一个估值函数的设计上：f(n)=g(n)+h(n)其中f(n)是每个可能试探点的估值，它有两部分组成：一部分，为g(n)，它表示从起始搜索点到当前点的代价。另一部分

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

4、SE表置空，算法开始时：1、如果OPEN表不为空，从表头取一个结点n，如果为空算法失败。2、n是目标解吗？是，找到一个解（继续寻找，或终止算法）。3、将n的所有后继结点展开，就是从n可以直接关联的结点（子结点），如果不在CLOSE表中，就将它们放入OPEN表，并把S放入CLOSE表，同时计算每一个后继结点的估价值f(n)，将OPEN表按f(x)排序，最小的放在表头，重复算法，回到1。第6页共6页人工智能实验报告A*算法流程图：三、实验过程与分析//OPEN-->CLOSE，起点-->任意顶点g(n)-->目标顶点

5、h(n)closedset:=theemptyset//已经被估算的节点集合openset:=setcontainingtheinitialnode//将要被估算的节点集合g_score[start]:=0//g(n)第6页共6页人工智能实验报告h_score[start]:=heuristic_estimate_of_distance(start,goal)//h(n)f_score[start]:=h_score[start]whileopensetisnotempty//若OPEN表不为空x:=thenod

6、einopensethavingthelowestf_score[]value//x为OPEN表中最小的ifx=goal//如果x是一个解returnreconstruct_path(came_from,goal)//removexfromopensetaddxtoclosedset//x放入CLSOE表foreachyinneighbor_nodes(x)ifyinclosedsetcontinuetentative_g_score:=g_score[x]+dist_between(x,y)ifynotinop

7、ensetaddytoopensettentative_is_better:=trueelseiftentative_g_scorey

8、-->goalf_score[y]:=g_score[y]+h_score[y]returnfailurefunctionreconstruct_path(came_from,current_node)ifcame_from[current_node]isset第6页共6页人工智能实验报告p=reconstruct_path(came_from,came_from[cur