astar(a星)算法.doc

A*算法原理简介A*（A-Star)算法是一种静态路网中求解最短路最有Astar算法在静态路网中的应用效的方法。公式表示为： f(n)=g(n)+h(n),其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。估价值与实际值越接近估价函数取得就越好例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt(dx-nx)*(dx-nx)+(dy-ny)*(dy-ny)；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。conditions of heuristicOptimistic (must be less than or equal to the real cost)As close to the real cost as possible详细内容主要搜索过程伪代码如下：创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算起点的估价值;将起点放入OPEN表;while(OPEN!=NULL)从OPEN表中取估价值f最小的节点n;if(n节点=目标节点)break;for(当前节点n 的每个子节点X)算X的估价值;if(X in OPEN)if( X的估价值小于OPEN表的估价值 )把n设置为X的父亲;更新OPEN表中的估价值; /取最小路径的估价值if(X inCLOSE) if( X的估价值小于CLOSE表的估价值 )把n设置为X的父亲;更新CLOSE表中的估价值;把X节点放入OPEN /取最小路径的估价值if(X not inboth)把n设置为X的父亲;求X的估价值;并将X插入OPEN表中; /还没有排序/end for将n节点插入CLOSE表中;按照估价值将OPEN表中的节点排序; /实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。/end while(OPEN!=NULL)保存路径，即 从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；启发式搜索其实有很多的算法比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，便没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？其实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)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。 A*算法实现收藏A*算法实现一、算法思想搜索中利用启发式信息，对当前未扩展结点根据设定的估价函数值选取离目标最近的结点进行扩展，从而缩小搜索空间，更快的得到最优解，提高效率。二、启发函数、不在位数码个数 启发函数h ( n )为当前结点不在位的数码个数。由于一次只能移动一个数字位，因此h ( n ) = h * ( n )， 同时有h ( t ) = 0 而且对于结点m和n （n 是m的子结点） 有h ( m ) h ( n ) = 1 = Cost ( m, n ) 即该启发函数满足单调限制条件，只要扩展到某个结点，就找到了从初始结点到达该结点的最优路径。、每个数字位与对应目标数字位间距离和 进一步考虑当前结点与目标结点的距离信息，令启发函数h ( n )为当前8个数字位与目标结点对应数字位距离和（不考虑中间路径）， 同样满足h ( n ) = h * ( n )， 且对于目标有 h ( t ) = 0，对于结点m和n （n 是m的子结点） 有h ( m ) h ( n ) = 1 = Cost ( m, n ) 满足单调限制条件。三、具体实现、结点编码 对于数码问题，每个结点有个数字和一个空格，可以将空格看成，那么一共有个数字，位的int可以表示* 109 ，可以用一个整数表示一个结点对应的信息。计算一个整数中（即空格）的位置比较耗时间，用一个整数存储当前结点的位置，还要存储对应的 g , h 值以及该结点由哪个结点扩展来的信息。、open表的数据结构表示 考虑对open表的操作，每次需要得到所有待扩展结点中 f 值最小的那个结点，用堆进行实现，可以达到O ( log ( heapSize ) ) 时间复杂度。、closed表的数据结构表示 closed表存储已扩展的结点间的扩展关系，主要用于输出路径。考虑结点扩展的操作，设待扩展的结点为m，由它扩展生成的结点为n1, n2, 。结点m扩展完成后被放到closed表中，放入后它在closed表中位置不发生变化，可以将n1, n2, 的前驱结点置为m在closed表中的位置，当n1, n2, .中有结点设为n1被扩展放入closed表时，n1的前驱刚好已经存储好。下面说明closed表中任意一个结点都存储有它的前驱结点的信息，考虑closed表中任意一个结点，如果它是初始结点，它没有前驱结点，如果不是根结点，扩展该结点时它的前驱结点已经记录。从而在closed表中形成扩展关系的树状结构。因为只需要前驱结点的下标位置，可以用数组实现，每个结点记录整数表示的数码格局和它的前驱结点的下标，输出路径时，根据前驱结点形成到达根结点的链条，递归输出即可。、解决结点重复扩展问题 对于一个结点有多种方式到达该结点，这样就可能多次将它加入open表中，而启发函数满足单调限制条件，后来达到该结点的路径不再是更优的，可以不予考虑。扩展某结点时先看该结点是否已经扩展过，如果扩展过则略过。实现的可以线形遍历closed表，但效率不高时间复杂度为O ( closedSize)，考虑每个结点可以用一个整数标识，用二叉平衡查找树可以得到更好的时间复杂度O ( log (closedSize) ) ，程序中用基于红黑树思想的set实现。四、对比程序 为对比测试时间，实现了宽度优先方法求解数码问题和两种启发函数的A*算法。宽度优先是一种盲目搜索方法，没有深入挖掘问题的可利用信息，或者说h ( n ) = 0。搜索扩展结点时，只是根据层数优先根据扩展结点的先后顺序选择当前要扩展的结点，搜索空间大，耗时比较长。而启发函数好坏将直接影响A*算法性能。五、输入输出 程序采用文本输入输出，输入文件为astar.in，A*算法第一种启发函数输出文件为astar1.out，第二个启发函数输出为astar2.out，宽度优先算法输出为bfs.out，可以用记事本打开。输入格式为一个测试用例由两个中间由一空行隔开的数码格局组成，输出为对应测试用例的走法路径及相关统计信息，程序假定输入数据符合要求，未做检查。六、测试结果 测试用例最后一个需要步才能得到结果，数据规模较大，宽度优先算法和第一种启发函数A*算法需要几秒才能运行得出结果，第二种算法非常快即得到结果。以下数据为VC+6.0编译得到的结果，VC+6.0对标准C+中STL支持不好，利用g+进行编译可以极大的缩短时间（经测试所有测试用例均在1秒内得出正确结果）。宽度优先算法：输入数据编号步数扩展结点数生成结点数搜索用时(毫秒)1536651521823486349611141312704301814131814406235A*算法1，利用第一个启发函数：输入数据编号步数扩展结点数生成结点数搜索用时(毫秒)156130218127921224631140430984051229994266A*算法2，利用第二个启发函数：输入数据编号步数扩展结点数生成结点数搜索用时(毫秒)155110218171289031140430794312019359七、结论：1、宽度优先算法扩展结点时没有考虑结点与目标的距离盲目的从open表中选取结点，A*算法利用估价函数计算open表中待扩展结点和目标结点间的距离选取“最近”的结点进行扩展，扩展的结点少，保证得到最优解前提下减小了搜索空间，提高效率。2、启发函数好坏极大的影响A*算法的性能，由上表可以看出，充分利用问题内在信息，启发函数设计的好，可以极大降低扩展的结点，对于需要18步才能完成的测试用例在1毫秒内即可完成，而对于需要30步的测试用例也只需要0.359秒，比第一个A*算法快非常多。以上选取的两个启发函数都满足单调限制条件，扩展到某结点即得到了初始结点到该结点的最佳路径。源代码及测试数据/* 算法： A* 是否最优解： 是 启发函数： 每一个数字位与目标中该数字位的距离，满足单调限制条件； 启发函数： 不在位的数字数 说明： A*算法是启发式搜索算法，搜索时充分利用当前状态距目标距离远近的启发信息， 选取当前未扩展结点中估价函数最小的进行扩展，生成结点数少，搜索空间较小，实现稍复杂， 备注： 程序未对输入数据进行检查*/#pragma warning(disable:4786)#include #include #include #include #include #include #include using namespace std;/* item记录搜索空间中一个结点 state 记录用整数形式表示的8数码格局 blank 记录当前空格位置，主要用于程序优化，扩展时可不必在寻找空格位置 g, h 对应g(n), h(n) pre 记录当前结点由哪个结点扩展而来*/struct item int state; int blank; int g; int h; int pre;const int MAXSTEPS = 100000;const int MAXCHAR = 100;char bufMAXCHARMAXCHAR;/open表item openMAXSTEPS;int steps = 0;/closed表，已查询状态只要知道该状态以及它由哪个结点扩展而来即可，用于输出路径/每次只需得到对应f值最小的待扩展结点，用堆实现提高效率pair closedMAXSTEPS;/读入，将8数码矩阵格局转换为整数表示bool read(pair &state) if (!gets(buf0) return false; if (!gets(buf1) return false; if (!gets(buf2) return false; assert(strlen(buf0) = 5 & strlen(buf1) = 5 & strlen(buf2) = 5); state.first = 0; for (int i = 0, p = 1; i 3; +i) for (int j = 0; j 6; j += 2) if (bufij = ) state.second = i * 3 + j / 2; else state.first += p * (bufij - 0); p *= 10; return true;/*int calculate(int current, int target) int cnt = 0; for (int i = 0; i 9; +i) if (current % 10 != 0)& (current % 10) != (target % 10) +cnt; current /= 10; target /= 10; return cnt;*/计算当前结点距目标的距离int calculate(int current, int target) int c9, t9; int i, cnt = 0; for (i = 0; i 9; +i) ccurrent % 10 = ttarget % 10 = i; current /= 10; target /= 10; for (i = 1; i b.g + b.h; ;/将整数形式表示转换为矩阵表示输出void pr(int state) memset(buf, , sizeof(buf); for (int i = 0; i 3; +i) for (int j = 0; j = 0 & a = 0 & b 3);/递归输出搜索路径路径void path(int index) if (index = 0) pr(closedindex.first); puts(); return; path(closedindex.second); pr(closedindex.first); puts(); +steps;int main() unsigned int t1 = clock(); freopen(astar.in, r, stdin); freopen(astar2.out, w, stdout); setstates; char tmp100; int i, x, y, a, b, nx, ny, end, next, index, kase = 0; pair start, target; item head; /4个方向移动时的偏移量 const int xtran4 = -1, 0, 1, 0; const int ytran4 = 0, 1, 0, -1; const int p = 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000; while (read(start) unsigned int t2 = clock(); printf(Case %d:nn, +kase); gets(tmp); read(target); gets(tmp); /初始化open表，将初始状态加入 open0.state = start.first; open0.h = calculate(start.first, target.first); open0.blank = start.second; open0.pre = -1; open0.g = 0; index = 0; states.insert(start.first); /提取open表中f值最小元素放入closed表，并对该结点进行扩展 for (end = 1; end 0; +index) assert(index MAXSTEPS); /临时存储 head = open0; /放入closed表记录当前格局和由哪个结点扩展而来（该结点肯定已在closed表中） closedindex.first = open0.state; closedindex.second = open0.pre; /从open表中删除该结点 pop_heap(open, open + end, cmp(); -end; /得到结果，递归输出路径 if (head.state = target.first) path(index); break; x = head.blank / 3; y = head.blank % 3; for (i = 0; i 4; +i) nx = x + xtrani; ny = y + ytrani; if (suit(nx, ny) a = head.blank; b = nx * 3 + ny; /调换十进制表示整数对应两个数字位 next = head.state + (head.state % pa + 1) / pa - (head.state % pb + 1) / pb) * pb + (head.state % pb + 1) / pb - (head.state % pa + 1) / pa) * pa; /判断是否已经扩展过 if (states.find(next) = states.end() states.insert(next); openend.pre = index; openend.blank = b; openend.state = next; openend.h = calculate(next, target.first); openend.g = head.g + 1; +end; push_heap(open, open + end, cmp(); if (end = 0) puts(No solution); else printf(Num of steps: %dn, steps); printf(Num of expanded: %dn, index); printf(Num of generated: %dn, index + end); printf(Time consumed: %dnn, clock() - t2); states.clear(); steps = 0; printf(Total time consumed: %dn, clock() - t1); return 0;/* 算法： 宽度优先 是否最优解： 是 说明： 宽度优先搜索属于盲目搜索，没有利用当前状态距目标距离远近的启发信息， 在选取要扩展结点时只是按宽度优先或者层数优先选取先生成的结点，生成 结点数较多，搜索空间较大，实现思想较简单，但代码长度与A*算法差不多 备注： 程序未对输入数据进行检查*/#pragma warning(disable:4786)#include #include #include #include #include #include #include using namespace std;/* item 用来记录一个结点的对应信息 其中： state 表明当前8数码对应的格局比如102345678 对应： 8 7 6 5 4 3 2 1 由所有数字（0代替空格）反向连接而成 blank用于记录空格所在的位置上例中为 7 pre用于记录当前这个状态是由closed表中哪个状态扩展而来的*/struct item int state; int blank; int pre;const int MAXSTEPS = 500000;const int MAXCHAR = 100;char bufMAXCHARMAXCHAR;/0, top) 为closed表， top, end间为open表item openMAXSTEPS;/读入，将矩阵表示8数码转化为用整数表示bool read(pair &state) if (!gets(buf0) return false; if (!gets(buf1) return false; if (!gets(buf2) return false; assert(strlen(buf0) = 5 & strlen(buf1) = 5 & strlen(buf2) = 5); state.first = 0; for (int i = 0, p = 1; i 3; +i) for (int j = 0; j 6; j += 2) if (bufij = ) state.second = i * 3 + j / 2; else state.first += p * (bufij - 0); p *= 10; return true;/将整数表示的8数码转换成矩阵表示输出void pr(int state) memset(buf, , sizeof(buf); for (int i = 0; i 3; +i) for (int j = 0; j = 0 & a = 0 & b 3);int steps = 0;/记录需要移动的步数/递归打印出形成最终8数码的过程void path(int index) if (index = 0) pr(openindex.state); puts(); return; path(openindex.pre); pr(openindex.state); puts(); +steps;int main() unsigned int t1 = clock(), t2; freopen(astar.in, r, stdin); freopen(bfs.out, w, stdout); setstates; char tmp100; int i, x, y, a,