Dijkstra和Astar算法在智能导航中的应用分析.pdfVIP

第12卷第6期 重庆科技学院学报(自然科学版) 2010年12月 陈圣群1’2董林飞- (1．福建江夏学院，福州350108；2．福州大学，福州350002) 摘要：Dijkstra算法是最经典的最短路径算法，A一咖r算法是最有前景的启发式有哪些信誉好的足球投注网站算法。深入分析和比较两种算 法，在复杂的交通地形图中，通过改进估价函数，证实了A—star算法在智能导航中更加高效。 关键词：启发式有哪些信誉好的足球投注网站算法：估价函数；A-smr算法；Dijkstra算法 中图分类号：TP301 文献标识码：A 文章编号：1673—1980(2010)06—0159—03 Dijkstra和A—star算法不仅在解决路径有哪些信誉好的足球投注网站相关H讨=Abs[xl叫2]+Abs[yJ嘞] 的应用中十分普遍，包括网络路由算法、机器人探 定义6完备性：如果存在一个解答，该策略是 路、人工智能、游戏设计等，而且在GIS的交通路线导 否保证能够找到? 航、路径分析领域应用更加广泛。它们是人工智能 定义7最优性：如果存在不同的几个解答，该 领域的一种图有哪些信誉好的足球投注网站策略。A—star算法采用了启发式策略是否可以发现最高质量的解答? 函数对有哪些信誉好的足球投注网站过程中产生的分支进行评估，以选择最 2算法描述 佳的分支进行有哪些信誉好的足球投注网站。它的实现关键在于建立一个合 适的估价函数，估价函数构造得越准确，则有哪些信誉好的足球投注网站策略 2．1 Dijkstra算法 越优。一般有哪些信誉好的足球投注网站策略可以通过下面4个准则来评价【1·21： 完备性、时间复杂性、空间复杂性和最优性。 值大小递增的次序产生最短路径的算法，它可用于 计算从有向图中任意一节点到其他节点的最优路 1 相关定义 径。下面以邻接矩阵来描述该算法的实现过程【3．41。 为方便后续讨论。先对图和最短路径算法的相 假定某向量的起始点在有向图中的序号为m，并设 关概念作如下定义： 定义1|s为已经找到的从起点出发的最短路径 按以下步骤： 的终点的集合：V是节点的集合。 StepI选择yj，使得： 定义2分量Dist[i]表示从起始点到每个终点y， EV Dist[j]=min{Dist[i]／Vf∈y—S}yi 的最小权值，V；∈V。 yi就是当前求得的一条从矿。出发的最优路径的 定义3带权的邻接矩阵Cost来表示带权的具 终点，令： 有Ⅳ个节点的有向图，邻接矩阵Cost[i√]表示弧yj，岭，S=SU{一} 的权值，其中Vi，V年V，如果从y到yi不通，StJCost Step2修改从y。出发到集合y_s中任意一顶点％ [i，，]=∞。 的最短路径长度。如果 定义4既为节点i至目标点D的Euclid距离(直 Dist[j]+Cost[j，k]Dist[k] 线距离) Step3修改Dist[k]为： Disk[k]=Dist[j]+Cost[．／，k] Ez=sqrt@,一心)木(吃一致)+(以一nJ木(匆一nJ) 定义5日讨为节点i至目标点D的Hamilton距离 求得从y。出发到目标节点的最短路径。 (垂直距离和水平距离之和) 收稿B期：2010-06-20 作者简介：陈圣群(1977一)，男，福建莆田人，福建江夏学院工程