人工智能作业

人工智能课程设计。

用a*算法编写迷宫问题。

学院：班级：

姓名：学号：

一、程序目的。

通过编制迷宫程序来熟练掌握a*算法并熟悉和掌握a*算法实现迷宫寻路功能，要求掌握启发式函数的编写以及各类启发式函数效果的比较。

二、算法概述。

下面给出a*算法：

open:=(s),f(s)=g(s)+h(s)=h(s),fm:=0;

loop：if open=( then exit(fail);

nest:=,计算f(n,mi):=g(n,mi)+h(mi);g(n,mi)是从s通过n到mi的耗散值，f（n,mi）是从s通过n、mi到目标结点耗散值的估计；

add(mi,open),标记mi到n的指针。

if f（n,mi） if f(n,m1)open中的节点按f值从小到达排序；

go loop。

下面给出源程序中所定义的函数：

bool bound(walked *a)

a为struct walked类型的节点。

该函数确定了迷宫模型的边界。

bool bound(walked *a)

int function_h(walked *a)

a为struct walked类型的节点。

该函数求出节点的h（s）值并返回。

void walking_path(walked *a)

a为struct walked类型的节点。

该函数回溯a节点的父节点，并且输出从已确定的最短路径的从开始到目标节点的路径。

walked* exist_open(walked *a)

a为struct walked类型的节点。

该函数确定节点a是否存在于open中，如果存在，则返回，如果不存在，return0

walked* exist_close(walked *a)

a为struct walked类型的节点。

该函数确定节点a是否存在于closed中，如果存在，则返回，如果不存在，return0

void expand(walked *a)

a为struct walked类型的节点。

该函数为扩展函数，即扩展a节点，并按照a*算法的步骤判断节点的可行性。

void sortstack()

该函数为排序函数，负责排序open和closed中的数据。

int gointomaze()

该函数负责初始化迷宫模型并且调用其他关键函数。

void printmaze()

该函数负责输出迷宫的模型。

三、实验原理。

1)a*算法。

a*（a-star)算法是一种静态路网中求解最短路最有效的方法。公式表示为： f(n)=g(n)+h(n),其中 f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)<=n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。

如果估价值》实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

其实a*算法也是一种最好优先的算法只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，a*就是干这种事情的！

我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。a*算法是一个可采纳的最好优先算法。a*算法的估价函数可表示为：

f'(n) =g'(n) +h'(n)这里，f'(n)是估价函数，g'(n)是起点到节点n的最短路径值，h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可（这一点特别的重要）。

可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是a*算法。举一个例子，其实广度优先算法就是a*算法的特例。

其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是。当然它是一种最臭的a*算法。

再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。

但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。

2)迷宫问题。

迷宫图从入口到出口有若干条道路，求从入口到出口最短路径的走法。

如图1为一简单迷宫示意图及其平面坐标表示。以平面坐标图来表示迷宫的道路时，问题的状态以所处的坐标位置来表示，即综合数据库定义为(x,y)，1<=x,y<=n(n为迷宫问题的最大坐标数)，则迷宫问题归结为求(1,1)到(4,4)的最短路径问题。

迷宫走法规定为向东、南、西、北前进一步，由此可见得到规则集简化形式如下。

r1：if(x,y) then(x+1,y)

r2: if(x,y) then(x,y-1)

r3: if(x,y) then(x-1,y)

r4: if(x,y) then(x,y+1)

对于这个简单例子，可给出状态空间如图2所示。

为求得最佳路径，可使用a*算法。假定搜索一步去单位耗散，则可定义：

h(n)=|xg-xn|+|yg-yn|

其中(xg,yg)为目标点坐标，(x,y)为节点n的坐标。由于该迷宫问题所有路径都是水平或者垂直的，没有斜路，因此，h(n)=|xg-xn|+|yg-yn|显然可以满足a*的条件，即h(n)<=h*(n)。取g(n)=d(n),有f(n)=d(n)+h(n)。

再设当不同结点的f值相等时，以深度优先排序，则搜索图如图3所示。最短路径为((1,1),(1.2),(1,3),(2,3),(2,4),(3,4),(3,3),(4,3),(4,4))。

在该搜索图中，目标节点的f时8，有几个节点的f也是8，那么这几个f为8的节点，也有被扩展的可能，就看他们在open表中的具体排列次序了。这里假定了f相等时，以深度优先排序。

图1 迷宫问题及其表示。

图2 状态空间图。

图3 迷宫问题启发式搜索图。

四、实验内容。

熟悉掌握a*算法，并用此算法解决迷宫的最短路径问题。

运用编程语言，写出a*算法的源程序，并利用源程序打印迷宫模型，并找出通过迷宫的最短路径，并且输出。

迷宫模型如图。

五、源**（包含注释）

#include

using namespace std;

int mazemap[7][7]=,0,3,0,3,2,3,2},1,2,1,2,1,2,1},2,3,2,3,0,3,2},1,2,1,2,1,2,1},2,3,0,3,2,3,0},1,2,1,2,1,2,1}};确定迷宫模型，0为不连接，1为节点，2为连接，3为空。

struct walked

int x;

int y;

int g;

int f;

struct walked *parent;

stackopen;

stackclose;//建立open和closed堆栈。

bool bound(walked *a)

//确定迷宫边界。

if(a->x>=0&&a->x<=6&&a->y>=0&&a->y<=6)

return 1;

elsereturn 0;

人工智能作业

人工智能作业

人工智能作业

人工智能作业

其他用户还读了