人工智能实验报告模板.doc
人工智能实验报告姓 名孙博宇学 号班 级数字1201指 导 教 师于瑞云开 设 学 期2015-2015第一学期实验题目 实验一 A*搜索解决罗马尼亚度假问题实验日期2015/05/052015/05/11评 定 成 绩评定人签字评 定 日 期东北大学软件学院一、 实验目的A* 搜索也使用启发式函数计算搜索空间。A*搜索与最佳优先搜索不同的是，它既是最优的，也是完备的。A*搜索解决罗马尼亚度假问题 ：二、 实验内容与实验步骤图结构地图#include "graph.h"优先队列OPEN表#include "pqueue.h"数组或队列CLOSED表#include "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*算法最为核心的过程，就在每次选择下一个当前搜索点时，是从所有已探知的但未搜索过点中(可能是不同层，亦可不在同一条支路上)，选取f值最小的结点进行展开。而所有“已探知的但未搜索过点”可以通过一个按f值升序的队列(即优先队列)进行排列。这样，在整体的搜索过程中，只要按照类似广度优先的算法框架，从优先队列中弹出队首元素（f值），对其可能子结点计算g、h和f值，直到优先队列为空(无解)或找到终止点为止。首先将起始结点S放入OPEN表，CLOSE表置空，算法开始时：1、如果OPEN表不为空，从表头取一个结点n，如果为空算法失败。 2、n是目标解吗？是，找到一个解（继续寻找，或终止算法）。 3、将n的所有后继结点展开，就是从n可以直接关联的结点（子结点），如果不在CLOSE表中，就将它们放入OPEN表，并把S放入CLOSE表，同时计算每一个后继结点的估价值f(n)，将OPEN表按f(x)排序，最小的放在表头，重复算法，回到1。A*算法流程图：三、实验过程与分析/OPEN->CLOSE，起点->任意顶点g(n)->目标顶点h(n)closedset := the empty set /已经被估算的节点集合 openset := set containing the initial node /将要被估算的节点集合 g_scorestart := 0 /g(n) h_scorestart := heuristic_estimate_of_distance(start, goal) /h(n) f_scorestart := h_scorestart while openset is not empty /若OPEN表不为空 x := the node in openset having the lowest f_score value /x为OPEN表中最小的 if x = goal /如果x是一个解 return reconstruct_path(came_from,goal) / remove x from openset add x to closedset /x放入CLSOE表 for each y in neighbor_nodes(x) if y in closedset continue tentative_g_score := g_scorex + dist_between(x,y) if y not in openset add y to openset tentative_is_better := true else if tentative_g_score < g_scorey tentative_is_better := true else tentative_is_better := false if tentative_is_better = true came_fromy := x g_scorey := tentative_g_score h_scorey := heuristic_estimate_of_distance(y, goal) /x->y->goal f_scorey := g_scorey + h_scorey return failurefunction reconstruct_path(came_from,current_node) if came_fromcurrent_node is set p = reconstruct_path(came_from,came_fromcurrent_node) return (p + current_node) else return the empty path 四、 实验结果总结一种具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是： 1、搜索树上存在着从起始点到终了点的最优路径。 2、问题域是有限的。 3、所有结点的子结点的搜索代价值>0。 4、h(n)=<h*(n)（h*(n)为实际问题的代价值）。 当此四个条件都满足时，一个具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法，并一定能找到最优解。
