A算法的改进课程设计

1、课程设计说明书 NO.1A*最短路径算法的改进1.课程设计的目的本课程设计是学习数据通信与通信网技术课程必要的教学环节。由于该课程是专业必修课，需要通过实践巩固基础知识，为使学生取得最现代化的设计技能和研究方法，课程设计训练也就成为了一个重要的教学环节。通过对路由算法的设计和实现，达到进一步完善对通信网基础及应用课程学习的效果。2.设计方案论证算法具体的形式包括：确定起点的最短路径问题：即已知起始结点，求最短路径的问题。确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起

2、点的问题。确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。全局最短路径问题：求图中所有的最短路径。（1）Floyd求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度O(V3)。Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。Floyd-Warshall的原理是动态规划：设Di,j,k为从i到j的只以(1.k)集合中的节点为中间节点的最短路径的长度。若最短路径经过点k，

3、则Di,j,k = Di,k,k-1 + Dk,j,k-1；若最短路径不经过点k，则Di,j,k = Di,j,k-1。因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。 沈 阳 大 学课程设计说明书 NO2Floyd-Warshall算法的描述如下：for k 1 to n do for i 1 to n do for j 1 to n do if (Di,k + Dk,j < Di,j) then Di,j Di,k + Dk,j; 其中Di,j表示由点i到点j

4、的代价，当Di,j为 表示两点之间没有任何连接。（2）Dijkstra求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）。源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV）。当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V2） 。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（V*lgV + E）。（3）Bellman-Ford求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（VE）。Bellman-Ford算法是求解单源最短路径问题的一种算法。单源点的最短路径问题是指：给定一个加权有向图G和源

5、点s，对于图G中的任意一点v，求从s到v的最短路径。与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数。设想从我们可以从图中找到一个环路（即从v出发，经过若干个点之后又回到v）且这个环路中所有边的权值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。A*（A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。注意是最有效的直接搜索算法。之后涌现了很多预处理算法（ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。公

6、式表示为： f(n)=g(n)+h(n),其中 f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取： 沈 阳 大 学课程设计说明书 NO.3估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行，此时的搜索效率是最高的。如果估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能

7、保证得到最优解。 算法是一种启发式搜索算法, 在路径规划中得到广泛的应用, 其中启发函数的设计尤其重要。本文针对路径规划问题, 对A* 算法作了以下改进: 一是在估价函数中考虑以距离和方向两个要素, 通过归一化处理解决了单位不统一的问题; 二是利用 k- d树空间索引结构, 动态加载节点信息, 减小内存使用空间。实验结果表明, 改进后的A* 算法的搜索效率得到了明显的提高。最经典的最短路径搜索算法是 Dijkstra算法,属于遍 历搜索, 它简单易用并总能搜索到最短路径。但是当网 络中节点数较多时,该算法搜索的结点数量会很大,效率非常低。因此有人提出了启发式搜索算法,如: 局部择 优搜索法、最

8、好优先搜索法、A*算法等。启发式搜索就是 在状态空间中, 对每一个搜索的位置进行评估, 得到最好的位置,从而在这个位置进行搜索直到搜索到目标为止。 目前在路径优化领域, 最流行的启发式搜索算法当属由 H ar,t Nilsson, Raphael等人首先提出的 A* 算法。它利用启发函数来估计任意点到目标点的远近程度, 从而减少 搜索空间, 提高搜索效率。许多文献都对 A* 算法进行了研究, 并且都提出在估价函数中引入距离和方向两个要素。但是距离和方向的单位是不统一的,所以在利用时会出现一些问题, 本文针对这一问题进行了研究,并对估价函数进行了改进。另外,为了进一步提高算法的运行效率,本文在算

9、法运行结构上,采用 k- d树空间索引结构,降低内存存储空间。实验结果证明了改进后算法的合理性和可行性。3.设计的过程与分析 A*算法是建立在Dijkstra和 BFS(最好优先搜索 )算法基础上的。它的整体框架采用遍历搜索法, 但是它采 用了启发函数来估计地图上任意点到目标点的费用, 从而可以很好地选择搜索方向。A*算法引入了当前节点j的启发函数 f*( j),当前节点 j的启发函数定义为: f*(j)=g(j)+h*(j)(1)其中 g(j)是从起点到当前节点 j的实际费用的量度, h*(j)是从当前节点j到终点的最小费用的估计。 沈 阳 大 学课程设计说明书 NO.4注意到若 h *(j

10、) = 0,即没有利用任何全局信息,这时A* 算法就变成了普通的 Dijkstra算法。因此普通的Dijkstra算法可 看作 A* 算法的特殊情形。h* (j)要满足相容性条件: 即不能高于节点 j到终点的实际最小费用。可以证明,如果估价函数满足相容性条件, 且原问题存在最优解,则 A* 算 法一定能够求出最优路径 。A* 算法的优点在于利用启发函数, 使搜索方向更加智能的趋向于终点,所以其搜索深度较小, 搜索的节点数少,故占用存储空间少,如图 1所示。 图1 A*算法与Dijkstra算法搜索区域对比 A* 算法的估价函数 A* 算法的关键在于设计一个合适的启发函数。有文 献对其特点进行了

11、分析, 认为启发函数 f* (j)值是非递减 的,只要能够满足相容性条件即估价函数 h* ( j)小于节点 j到目标点的实际费用,它生成的路径一定是最优的。许多文献都在估价函数的构造中引入了距离和方向两个要素 ,即: h*(j) = w1* L+w2*如图2所示。其中 L 表示当前节点到终点的欧氏距离,表示起点到当前节点的线段与当前节点到终点的线段的夹角即 SjE,有文献也用到了中间节点与关联节点的线段和关联节点与终点的线段夹角 NjE。w1和w2分别是距离和角度的加权值,w1和w2 的取值范围分别为 055- 0.65和0.35-0.45。但距离和角度的单位不统 一的问题不能忽略,即使角度的

12、单位为弧度、距离的单位 为千米,它们之间也很有可能出现距离值远大于角度值 (即 L )的情况,特别是在大区域路径规划过程中,问题更明显。 沈 阳 大 学课程设计说明书 NO.5而当 L时, 方向不再有约束力,而使得估价函数失去意义。 A* 算法的运行结构 当构造合适的估价函数后就要考虑算法的运行,目前大多数方法是将全部数据读入到内存当中, 然后搜索 最短路径。从理论上讲, A* 算法可以通过搜索更少的节 点完成最短路径的搜索。但是算法运行时,必须要考虑两个问题:一是数据读取的速度。即使可以很快地将数 据读入到内存中,我们也还要考虑第二个问题, 即系统内 存的大小。如果系统内存足够大,在算法运行

13、过程中,也将会出现对同一节点进行重复的搜索,从而降低算法的运行效率。针对数据的读取问题,有学者提出了基于限 制区域的A* 算法,减小数据的加载量。但是由于A* 算法本身就是一种有损算法, 这种方法很有可能搜索 不到最短路径, 特别是在考虑道路属性信息和交通限制信息时。图2 估价函数构造示意图 改进的 A* 算法 （1） A* 算法估价函数的改进针对A* 算法估价函数所出现的问题,我们将距离和角度进行归一化处理,即首先计算当前节点所有关联节点相应的距离和角度值,然后求它们的平均值即 L，从而使得估价函数 变为: h* (j) = w1* L + w2* (5) 其中: L= L/L (6)=/(

14、7) 归一化处理以后,只考虑距离和角度对路径的贡献,而不必考虑距离和角度的数值大小。从而避免了距离和 角度单位不统一的问题。虽然算法的运行要增加计算 量, 但是我们可以通过进一步减小算法的搜索空间, 改善 算法的运行结构来提高算法的搜索效率。 沈 阳 大 学课程设计说明书 NO.6 针对算法运行效率的问题, 建立k-d树空间索引结构, 动态加载路网数据, 从而提高算法效率不失为一个好方法。 k- d树索引结构是 k( k > 1)的二叉检索树,主要用于索引多属性的数据或多维点数据, 它可以通 过坐标快速的访问区域中的路网数据。在算法执行过程中,并非开始就装载所有的路网数据,而是根据算法的

15、需要,读取节点的相关信息,或删除节点信息,虽然会增加运算过程中的 I/O运算,但是这样可以避免无效数据的大量装载,占用大量的内存空间。例如,首先判断当前节点是否在确定的范围内, 如果不在则装载相应区域的数据,如果在确定的范围内,则读取数据的相关信息,并进行节点扩展。然后,在此基础上计算路段的启发值,搜索最短路径。 （2） A* 算法的实现在算法的实现过程中,要构造两个链表。分别存储待扩展的节点和已扩展的节点,分别称为Open表和 Close 表。算法步骤如下: 初始化设置。将起点信息加载到 Open表中, Close 表赋值为空。令g(j) = 0。 搜索距离当前节点最近的节点,即求f* (j

16、)的最小值,将节点j从Open表中删除并加载到Close表中。判断节点 j是否为终点,如果是,终点转向步骤4;否则转向步骤3。判断节点j的节点信息是否在确定的范围内,如果在范围内,则扩展节点j;否则加载节点j的节点信息并进行扩展。转向步骤2。从节点j开始, 利用回溯的方法输出起始节点到目 标节点的最优路径, 以及最短距离,算法终止。在算法的运行过程中,避免了对同一节点的重复访 问, 极大地缩小了搜索空间, 从而缩短了算法的运行时间。对改进后的A*算法进行了实验, 在估价函数归一化处理前后的最短路径搜索结果如图3(a), (b)所示。图3a改进前的搜索路径 沈 阳 大 学课程设计说明书 NO.7

17、图3b 改进后的搜索路径（3） 实验采用郑州市地图,节点2606个,路段4127条,在 core i5, 8GB内存的 PC机上运行。与其他算法的实验结果进行了对比, 结果见表1。表 中: T 表示临时标记节点个数,N表示永久标记节点的个数, D表示规划路径长度。表1 算法比较图4 临时标记节点个数比较 沈 阳 大 学课程设计说明书 NO.8图5 永久标记节点个数比较 将表1数据中的临时标记节点,永久标记节点比较关 系用图4、图5表示。通过实验由图4可以看出,归一化处理后的A* 算法的搜索区域明显减小,由表1可以看出 A* 算法的搜索效率要比 Dijkstra算法的搜索效率高。由图4、图5可知

18、,改进后的A* 算法的搜索效率明显要高,在利用 k- d树建立 空间索引结构以后,使得搜索的点数明显减少,特别是在区域比较大时,改进后的A* 算法的效率提高得更加明显。需要指出的是, 由于A* 算法本身就是有损算法,所以其寻找到的路径长度一般要比 Dijkstra算法的规划结果要长,但由于所选的道路更加合理,所以改进后算法的搜索结果更加实用。4设计体会通过这次的课程设计，利用A*算法求解最短路径，加深了对A*算法的了解与认识。课程设计环节中把教材里面的理论知识与实践联系起来，利用理论知识指导实践仿真，取得很多的收获。学习这个算法开始的时候会觉得比较难，花了一天的时间看资料理解算法的原理。在知道

19、原理后的第二天开始编写代码，同样也花了一天时间。最后是程序的显示的优化。总之通过学习这个算法编写程序，可以慢慢的从参考别人的代码转变自己知道原理后编写代码这个过程会比较慢需要不断的联系。A* 算法作为一种启发式搜索算法在路径规划中得到 了非常广泛的应用。利用启发函数减小搜索空间,从而提高搜索效率,因此启发函数在 A* 算法中起着关键的作用。针对A* 算法启发函数中距离和角度两个要素单 沈 阳 大 学课程设计说明书 NO.9位不统一的问题做了研究,提出将距离和角度归一化处理,并且利用 k-d树的空间索引结构,减少搜索空间。试验结果表明,改进后的A* 算法的效率明显提高。5参考文献 1T.H.Co

20、rmen,C.E.Leiserson,R.L.Rives,teta.lIntroductiontoAlgorithmsM . McGraw- H il,l 2001. 2 StevenM. LaVatle P lanning A lgorithm sM . Cambridge University Press, 2006. 3李擎，宋顶立.两种改进的最优路径规划算法J.北京科技大学学报，2011.4周春辉，李诗高.Dijkstra算法与A算法研究J.软件导刊，2007.5马进通信网分析M北京：人民交通出版社，2003 沈 阳 大 学课程设计说明书 NO.10附录部分程序代码：package c

21、om.ubird.astar.core.exception;public class AStarPositionException extends RuntimeException private static final long serialVersionUID = 5968574301453821996L; public AStarPositionException(String msg) super(msg); package com.ubird.astar.core;import java.util.ArrayList;import java.util.HashMap;import

22、java.util.List;import java.util.Map;public class AStarMap private List<AStarNode> openList = new ArrayList(); private Map<String, AStarNode> closeMap = new HashMap(); private boolean isFind = false; private List<AStarNode> path = new ArrayList(); public static final int STATE_BARRI

23、ER = 2; AStarNode target; AStarNode source; int astarData; public AStarMap(int xGridNum, int yGridNum) this.astarData = new intyGridNumxGridNum; this.source = new AStarNode(0, 0); this.target = new AStarNode(xGridNum - 1, yGridNum - 1); public AStarNode getTarget() return this.target; 沈 阳 大 学课程设计说明书

24、 NO.11public AStarNode getSource() return this.source; public int getAStarData() return this.astarData; public List<AStarNode> find() init(); AStarNode current = null; while (!isEnd() && (!isFind() current = getMinFNodeFromOpenList(); if (isAchieve(current) buildPath(current); this.isF

25、ind = true; else add2CloseMap(current); for (AStarNode neighbor : getNeighbor(current) if (neighbor = null) | (isInCloseMap(neighbor) | (isCanNotGo(current, neighbor) continue; boolean isBetter = true; AStarNode nodeFromOpenList = getNodeFromOpenList(neighbor); if (nodeFromOpenList != null) neighbor

26、 = nodeFromOpenList; int tg = neighbor.distinctG(current); isBetter = tg <= neighbor.getG(); else add2OpenList(neighbor); if (isBetter) neighbor.reCalculatorGAndH(current, this.target); return this.path; 沈 阳 大 学课程设计说明书 NO.12private AStarNode getNodeFromOpenList(AStarNode node) for (AStarNode open

27、Node : this.openList) if (openNode.equals(node)return openNode;return null;private boolean isCanNotGo(AStarNode from, AStarNode to)if (isBarrier(to) return true;int offsetX = from.getX() - to.getX();int offsetY = from.getY() - to.getY();return (Math.abs(offsetX) = 1) && (Math.abs(offsetY) =

28、1) && (offsetX = 1) && (offsetY = -1) && (isValidX(from.getX() - 1) && (2 = this.astarDatafrom.getY()(from.getX() - 1) | (isValidY(from.getY() + 1) && (2 = this.astarData(from.getY() + 1)from.getX() | (offsetX = 1) && (offsetY = 1) && (isValidY

29、(from.getY() - 1) && (2 = this.astarData(from.getY() - 1)from.getX() | (isValidX(from.getX() - 1) && (2 = this.astarDatafrom.getY()(from.getX() - 1) | (offsetX = -1) && (offsetY = 1) && (isValidX(from.getX() + 1) && (2 = this.astarDatafrom.getY()(from.getX() +

30、 1) | (isValidY(from.getY() - 1) && (2 = this.astarData(from.getY() - 1)from.getX() | (offsetX = -1) && (offsetY = -1) && (isValidX(from.getX() + 1) && (2 = this.astarDatafrom.getY()(from.getX() + 1) | (isValidY(from.getY() + 1) && (2 = this.astarData(from.get

31、Y() + 1)from.getX();private boolean isValidX(int x)return (x >= 0) && (x < this.astarData0.length);private boolean isValidY(int y) return (y >= 0) && (y < this.astarData.length); private AStarNode getMinFNodeFromOpenList() int index = 0; int minF = (AStarNode)this.openLis

32、t.get(index).getF(); int length = this.openList.size(); 沈 阳 大 学课程设计说明书 NO.13for (int i = 1; i < length; i+) AStarNode aStarNode = (AStarNode)this.openList.get(i); if (minF > aStarNode.getF() minF = aStarNode.getF(); index = i; return (AStarNode)this.openList.remove(index); private boolean isAc

33、hieve(AStarNode current) return current.equals(this.target); private void init() initParameter(); initOpenListAndCloseMap(); addSource2OpenList(); private void initParameter() this.isFind = false; this.source.init(this.target); this.path.removeAll(this.path); private void initOpenListAndCloseMap() c

34、learOpenList(); this.closeMap.clear(); public void clearOpenList() this.openList.removeAll(this.openList); private void addSource2OpenList() add2OpenList(this.source); 沈 阳 大 学课程设计说明书 NO.14 private void add2OpenList(AStarNode node) this.openList.add(node); private void add2CloseMap(AStarNode node) th

35、is.closeMap.put(node.toString(), node); private boolean isFind() return this.isFind; private boolean isEnd() return this.openList.size() = 0; public void loadData(int data, int barrierVal, int clearVal) if (data = null) return; if (data.length != this.astarData.length) | (this.astarData0.length != d

36、ata0.length) throw new RuntimeException("new data should be as large as the old astar map' data"); for (int i = 0; i < this.astarData.length; i+) for (int j = 0; j < this.astarDatai.length; j+) if (dataij = barrierVal) this.astarDataij = 2; else if (dataij = clearVal) this.astarD

37、ataij = 0; public void initTargetAndSource(int x, int y) this.source.setX(this.target.getX(); this.source.setY(this.target.getY(); this.target.setX(x); this.target.setY(y); package com.ubird.astar.core; 沈 阳 大 学课程设计说明书 NO.15import com.ubird.astar.core.exception.AStarPositionException;public class ASt

38、arNode implements Comparable<AStarNode> private static final int G_1 = 10; private static final int G_2 = 14; private static final int G_3 = 10; private static final int G_4 = 14; private static final int G_5 = 10; private static final int G_6 = 14; private static final int G_7 = 10; private s

39、tatic final int G_8 = 14; private static final int G_0 = 10; private int g; private int h; private int f; private int x; private int y; private AStarNode father; public AStarNode(int x, int y) this.x = x; this.y = y; public int getX() return this.x; public void setX(int x) this.x = x; public int get

40、Y() return this.y; public void setY(int y) this.y = y; public AStarNode getFather() return this.father; 沈 阳 大 学课程设计说明书 NO.16public void setFather(AStarNode father) this.father = father; public void init(AStarNode target) this.g = 0; this.h = heuristicCostEstimate(this, target); this.f = (this.g + th

41、is.h); public int heuristicCostEstimate(AStarNode source, AStarNode target) return (Math.abs(source.x - target.x) + Math.abs(source.y - target.y) * 10; public int compareTo(AStarNode o) return this.f < o.f ? -1 : 1; public boolean equals(Object obj) if (obj = null) | (!(obj instanceof AStarNode)

42、return false; AStarNode node = (AStarNode)obj; return (node.x = this.x) && (node.y = this.y); public String toString() return this.x + ", " + this.y; public void reCalculatorGAndH(AStarNode father, AStarNode target) this.g = distinctG(father); this.h = heuristicCostEstimate(this, t

43、arget); this.f = (this.g + this.h); this.father = father; 沈 阳 大 学课程设计说明书 NO.17public int distinctG(AStarNode father) int offsetX = this.x - father.x; int offsety = this.y - father.y; int distinct = 0; if (offsetX = 0) && (offsety = -1) distinct = 10; else if (offsetX = 1) && (offsety

44、 = -1) distinct = 14; else if (offsetX = 1) && (offsety = 0) distinct = 10; else if (offsetX = 1) && (offsety = 1) distinct = 14; else if (offsetX = 0) && (offsety = 1) distinct = 10; else if (offsetX = -1) && (offsety = 1) distinct = 14; else if (offsetX = -1) &&

45、amp; (offsety = 0) distinct = 10; else if (offsetX = -1) && (offsety = -1) distinct = 14; else throw new AStarPositionException("Unvalid relation between current node(" + this + ") and fater node(" + father + ")"); return distinct + father.g; public int getG() r

46、eturn this.g; public boolean isBetter(AStarNode node) return isGBetter(node); public boolean isGBetter(AStarNode node) return this.g + distinctG(node) < node.g; 沈 阳 大 学课程设计说明书 NO.18public boolean isFBetter(AStarNode node) return this.f < node.f; public int getF() return this.f; package com.ubi

47、rd.astar.demo;import com.ubird.astar.ui.AStarMenuBar;import com.ubird.astar.ui.AstarPanel;import com.ubird.astar.ui.ControlPanel;import com.ubird.astar.ui.StatusPanel;import com.ubird.astar.ui.UFrame;import java.awt.Container;import javax.swing.SwingUtilities;public class AStarDemo public static voi

48、d main(String args) SwingUtilities.invokeLater(new Runnable() public void run() UFrame frame = new UFrame(); AstarPanel astarPanel = new AstarPanel(15, 15, 60, 40); StatusPanel statusPanel = new StatusPanel(); astarPanel.setStatusPanel(statusPanel); frame.getContentPane().add(astarPanel, "Cente

49、r"); frame.getContentPane().add(new ControlPanel(astarPanel), "North"); frame.getContentPane().add(statusPanel, "South"); frame.setJMenuBar(new AStarMenuBar(astarPanel); frame.pack(); frame.setVisible(true); frame.setDefaultCloseOperation(3); astarPanel.requestFocus(); ); 沈 阳 大 学课程设计说明书 NO.19在算法的实现过程中, 要构造两个链表。分别存储 待扩展的节点和已扩展的节点, 分别称为 Open表和 C lose 表。