A* (A-Star)算法是一种静态路网中求解最短路最有 A star算法在静态路网中的应用
效的方法。
公式表示为：f(n )=g( n)+h( n),
其中f(n)是节点n从初始点到目标点的估价函数，
g(n)是在状态空间中从初始节点到
n节点的实际代价，
h( n)的选取：
h(n)是从n到目标节点最佳路径的估计代价。
保证找到最短路径(最优解的)条件，关键在于估价函数 率低。但能得到最优解。
估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范 围大，效如果估价值〉实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优 解。估价值与实际值越接近估价函数取得就越好
例如对于几何路网来说，可以取两节点间欧几理德距离(直线距离)做为估价
值，即卩 f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny));这样估价函数 f 在 g 值一定 的情况下，会或多或少的受估价值 h的制约，节点距目标点近，h值小，f值相对 就小，能保证最短路的搜索向终点的方向进行。明显优于 Dijstra算法的毫无无方 向的向四周搜索。 con diti
ons of heuristic
Optimistic (must be less tha n 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 in CLOSE) { if( X的估价值小于CLOSE表的估价值){ 把n设置为X的父亲； 更新CLOSE表中的估价值； 把X节点放入OPEN 〃取最小路径的估价值 } } if(X not in both){ 把n设置为X的父亲； 求X的估价值； 并将X插入OPEN表中；//还没有排序 } }//end for 将n节点插入CLOSE表中； 按照估价值将OPEN表中的节点排序；//实际上是比较OPEN表内节点f的大小, 从最小路径的节点向下进行。 }//end while(OPEN!=NULL)保存路径，即 从终点开始，每个节点沿着父节点移动直至起点，这就是你的路 径； 启发式搜索其实有很多的算法 比如：局部择优搜索法、最好优先搜索法等等。当然 A*也是。这些算法都使用 了启发函数，但在具体的选取最佳搜索节点时的策略不同。象局部择优搜索法， 就是在搜索的过程中选取 最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直 得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的 节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最 佳。最好优先就聪明多了，他在搜索时，便没有舍弃节点(除非该节点是死节 点)，在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个 最佳的节点”。这样可以有效的防止 最佳节点”的丢失。那么A*算法又是一种什 么样的算法呢？ 其实A*算法也是一种最好优先的算法 只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出 状态空间搜索的最短路径，也就是用最快的方法求解问题， 的！ 我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳 性。A*算法是一个可采纳的最好优先算法。 f(n) = g'( n) + h'( n) A*算法的估价函数可表示为： A*就是干这种事情 这里，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)v=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*算法实现 一、 算法思想 搜索中利用启发式信息，对当前未扩展结点根据设定的估价函数值选取离目标最 近的结点进行扩展，从而缩小搜索空间，更快的得到最优解，提高效率。 二、 启发函数 1、 不在位数码个数 启发函数h( n)为当前结点不在位的数码个数。由于一次只能移动一个数字位， 因此h ( n ) <= h * ( n )，同时有h ( t ) = 0而且对于结点 m和n (n是m的子结 点)有h ( m ) -h ( n ) <= 1 = Cost ( m, n )即该启发函数满足单调限制条件，只要 扩展到某个结点，就找到了从初始结点到达该结点的最优路径。 2、 每个数字位与对应目标数字位间距离和 进一步考虑当前结点与目标结点的距离信息，令启发函数 位与目标结点对应数字位距离和(不考虑中间路径)， Cost ( m, n )满足单调限制条件。 h( n )为当前8个数字 同样满足h ( n ) <= h * (n )，且对于目标有h ( t ) = 0，对于结点m和n (n是m的子结点)有h ( m )- h ( n ) <= 1 = 三、 具体实现 1、 结点编码 对于8数码问题，每个结点有8个数字和一个空格，可以将空格看成0,那么一 共有9个数字，32位的int可以表示2 * 109，可以用一个整数表示一个结点对 应的信息。计算一个整数中0(即空格)的位置比较耗时间，用一个整数存储当 前结点0的位置，还要存储对应的g , h值以及该结点由哪个结点扩展来的信息。 2、 open表的数据结构表示 考虑对open表的操作，每次需要得到所有待扩展结点中 堆进行实现，可以达到 0 ( log ( he apSize ))时间复杂度。 3、 closed表的数据结构表示 f值最小的那个结点，用 closed表存储已扩展的结点间的扩展关系，主要用于输出路径。考虑结点扩展的 操作，设待扩展的结点为 m,由它扩展生成的结点为n1, n2,…。•结点m扩展完 成后被放到closed表中，放入后它在closed表中位置不发生变化，可以将 n1, n2, •的前驱结点置为m在closed表中的位置，当n1, n2, ..中有结点设为n1被扩 展放入closed表时，n1的前驱刚好已经存储好。下面说明 closed表中任意一个结 点都存储有它的前驱结点的信息，考虑 closed表中任意一个结点，如果它是初始 结点，它没有前驱结点，如果不是根结点，扩展该结点时它的前驱结点已经记 录。从而在closed表中形成扩展关系的树状结构。因为只需要前驱结点的下标位 置，可以用数组实现，每个结点记录整数表示的8数码格局和它的前驱结点的下 标，输出路径时，根据前驱结点形成到达根结点的链条，递归输出即可。 决结点重复扩展问题 4、解 对于一个结点有多种方式到达该结点，这样就可能多次将它加入 open表中，而 启发函数满足单调限制条件，后来达到该结点的路径不再是更优的，可以不予考 虑。扩展某结点时先看该结点是否已经扩展过，如果扩展过则略过。实现的可以 线形遍历closed表，但效率不高时间复杂度为 0 ( closedSize),考虑每个结点可 以用一个整数标识，用二叉平衡查 找树可以得到更好的时间复杂度 0 ( log (closedSize))，程序中用基于红黑树思想 的set实现。四、对比程序 为对比测试时间，实现了宽度优先方法求解8数码问题和两种启发函数的 法。宽度优先是一种盲目搜索方法，没有深入挖掘问题的可利用信息，或者说 点，搜索空间大，耗时比较长。而启发函数好坏将直接影响 性能。五、输入输出 程序采用文本输入输出，输入文件为 astar.in, A*算法第一种启发函数输出文件 为astarl.ou，第二个启发函数输出为 astar2.ou，宽度优先算法输出为bfs.out,可 以用记事本打开。 输入格式为一个测试用例由两个中间由一空行隔开的8数码格局组成，输出为对 应测试用例的走法路径及相关统计信息，程序假定输入数据符合要求，未做检 查。六、测试结果 测试用例最后一个需要3 0步才能得到结果，数据规模较大，宽度优先算法和第 一种启发函数A*算法需要几秒才能运行得出结果，第二种算法非常快即得到结 A*算法 A*算 h (n ) = 0。搜索扩展结点时，只是根据层数优先根据扩展结点的先后顺序选择当前 要扩展的结果。以下数据为VC++6.0编译得到的结果，VC++6.0对标准C++中STL支持不 好，利用g++进行编译可以极大的缩短时间(经测试所有测试用例均在 1秒内得 出正确结果)。 宽度优先算法： 输入抽编町
5
扩ftf仙点0
56
234K6
冷
加ft用时1鬼秒】
65 34961 7
节
15 I14L D
t JO
4 L8M13
A*算法1,利用第一个启发函数: ■入编界 1 盘獻11[1也全拧J 5 6 12?*) 1 13 2122 4 0 46 O 4266
4 40 输人故抑:编号
i 5 扩 5 1薩站点绘 11 0 理-蛊川恫i ■凯幻 A*算法2,利用第二个启发函数:
18 171 1 7W3 4 I20IU 0 0 35*) 1 30 4 七、结论：1宽度优先算法扩展结点时没有考虑结点与目标的距离盲目的从 open表中选取结点，A*算法利用估价函数计算open表中待扩展结点和目标结点 间的距离选取 最近”的结点进行扩展，扩展的结点少，保证得到最优解前提下减 小了搜索空间，提高效率。
2、启发函数好坏极大的影响 A*算法的性能，由上表可以看出，充分利用问题内 在信息，启发
函数设计的好，可以极大降低扩展的结点，对于需要 18步才能完
成的测试用例在1毫秒内即可完成，而对于需要 30步的测试用例也只需要0.359 秒，比第一个A*算法快非常多。以上选取的两个启发函数都满足单调限制条 件，扩展到某结点即得到了初始结点到该结点的最佳路径。 源代码及测试数据
/*
算法：A* 是否最优解：是
启发函数：每一个数字位与目标中该数字位的距离，满足单调限制条件； 函数：不在位的数字数
说明：A*算法是启发式搜索算法，搜索时充分利用当前状态距目标距离远近的 启发信息， 选取当前未扩展结点中估价函数最小的进行扩展，生成结点数少，搜索空间较 小，实现稍复杂，
备注：程序未对输入数据进行检查
*/
#pragma warni ng(disable:4786) #include blank记录当前空格位置，主要用于程序优化，扩展时可不必在寻找空格位置 g, h 对应 g(n), h(n) pre记录当前结点由哪个结点扩展而来 */ struct item { int state; int bla nk; in t g; int h; int pre; }; const int MAXSTEPS = 100000; const int MAXCHAR = 100; char buf[MAXCHAR][MAXCHAR]; //ope n 表 item ope n[M AXSTEPS]; int steps = 0; //closed表，已查询状态只要知道该状态以及它由哪个结点扩展而来即可，用于输 出路径//每次只需得到对应f值最小的待扩展结点，用堆实现提高效率 pairvi nt, i nt> elosed[MAXSTEPS]; 〃读入，将8数码矩阵格局转换为整数表示 bool read(pair & state) { if (!gets(buf[0])) return false; if (!gets(buf[1])) return false; if (!gets(buf[2])) return false; assert(strlen(buf[0]) == 5 && strlen(buf[1]) == 5 && strlen(buf[2])== 5)； state.first = 0; for (int i = 0, p = 1; i < 3; ++i) { for (i nt j = 0; j < 6; j += 2) { if (buf[i][j]=='') state.sec ond = i * 3 + j / 2; else state.first += p * (buf[i][j] - '0'); p *= 10; } } return true; } /* int calculate© nt curre nt, int target) { int ent = 0; for (i nt i = 0; i < 9; ++i) { if ((current % 10 != 0)&& (current % 10) != (target % 10)) ++cnt; curre nt /= 10; target /= 10; } return cnt; } */ 〃计算当前结点距目标的距离 int calculate(i nt curre nt, int target) { int c[9], t[9]; int i, ent = 0; for (i = 0; i < 9; ++i) { c[current % 10] = t[target % 10] = i; curre nt /= 10; target /= 10; } for (i = 1; i < 9; ++i) ent += abs(c[i] / 3 - t[i] / 3) + abs(c[i] % 3 - t[i] % 3); return ent; } //open表中结点间选择时的规则f(n) = g(n) + h(n) class cmp { public: inline bool operator()(item a, item b) { return a.g + a.h > b.g + b.h; } }; 〃将整数形式表示转换为矩阵表示输出 void pr(i nt state) { memset(buf, ' ', sizeof(buf)); for (i nt i = 0; i < 3; ++i) { for (i nt j = 0; j < 6; j += 2) { if (state % 10) buf[i][j] = state % 10 + 'O'; state /= 10; } buf[i][5] = '\\0'; puts(buf[i]); } } 〃用于判断当前空格是否可以向对应方向移动 in li ne bool suit(i nt a, int b) { return (a >= 0 && a < 3 && b >= 0 && b < 3); } 〃递归输出搜索路径路径 void path(i nt in dex) { if (in dex == 0) { pr(closed[i ndex].first); puts(\"\"); return; } path(closed[i ndex].sec on d); pr(closed[i ndex].first); puts(\"\"); ++steps; } int main() { un sig ned int t1 = clock(); freope n(\"astar.i n\freope n(\"astar2.out\setstates; char tmp[100]; int i, x, y, a, b, nx, ny, end, n ext, i ndex, kase = 0; pair start, target; item head; 〃4个方向移动时的偏移量 const int xtra n[4] = {-1, 0, 1, 0}; const int ytra n[4] = {0, 1,0,-1}; const in t p[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}; while (read(start)) { un sig ned int t2 = clock(); prin tf(\"Case %d:\\n\\n\gets(tmp); read(target); gets(tmp); 〃初始化open表，将初始状态加入 ope n[ O].state = start.first; ope n[0].h = calculate(start.first, target.first); ope n[ 0].bla nk = start.sec ond; ope n[ 0].pre = -1; ope n[ 0].g = 0; in dex = 0; states.i nsert(start.first); 〃提取open表中f值最小元素放入closed表，并对该结点进行扩展for (end = 1; end > 0; ++in dex) { assert(i ndex < MAXSTEPS); 〃临时存储 head = ope n[ 0]; 〃放入closed表记录当前格局和由哪个结点扩展而来(该结点肯定已在 中) closed[i ndex].first = ope n[ 0].state; closed[i ndex].sec ond = ope n[ 0].pre; closed表 〃从open表中删除该结点 pop_heap(ope n, ope n + end, cmp()); --end; 〃得到结果，递归输出路径 if (head.state == target.first) { path(i ndex); break; } x = head.bla nk / 3; y = head.bla nk % 3; for (i = 0; i < 4; ++i) { nx = x + xtra n[i]; ny = y + ytra n[ i]; if (suit(nx, ny)) { a = head.bla nk; b = nx * 3 + ny; 〃调换十进制表示整数对应两个数字位 next = head.state + ((head.state % p[a + 1]) / p[a] - (head.state % p[b + 1]) / p[b]) * p[b] + ((head.state % p[b + 1]) / p[b] - (head.state % p[a + 1]) / p[a]) * p[a]; 〃判断是否已经扩展过 if (states.fi nd(n ext) == states.e nd()) { states.i nsert( next); ope n[en d].pre = in dex; ope n[en d].bla nk = b; ope n[en d].state = n ext; ope n[en d].h = calculate( next, target.first); ope n[en d].g = head.g + 1; ++e nd; push_heap(ope n, ope n + end, cmp()); } } } } if (end <= 0) puts(\"No solutio n\"); else { prin tf(\"Num of steps: %d\\n\prin tf(\"Num of expa nded: %d\\n\prin tf(\"Num of gen erated: %d\\n\prin tf(\"Time con sumed: %d\\n\\n\} states.clear(); steps = 0; } printf(\"Total time consumed: %d\\n\return 0; } /* 算法：宽度优先 是否最优解：是 说明：宽度优先搜索属于盲目搜索，没有利用当前状态距目标距离远近的启发信 息， 在选取要扩展结点时只是按宽度优先或者层数优先选取先生成的结点，生成 数较多，搜索空间较大，实现思想较简单，但代码长度与 程序未对输入数据进行检查 */ #pragma warni ng(disable:4786) #include 因篇幅问题不能全部显示，请点此查看更多更全内容