dijkstra和a-star算法在智能导航中的应用分析new

《dijkstra和a-star算法在智能导航中的应用分析new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据第12卷第6期重庆科技学院学报(自然科学版)2010年12月Dijkstra禾nA—star算法在智能导航中的应用分析陈圣群1’2董林飞-(1．福建江夏学院，福州350108；2．福州大学，福州350002)摘要：Dijkstra算法是最经典的最短路径算法，A一咖r算法是最有前景的启发式搜索算法。深入分析和比较两种算法，在复杂的交通地形图中，通过改进估价函数，证实了A—star算法在智能导航中更加高效。关键词：启发式搜索算法：估价函数；A-smr算法；Dijkstra算法中图分类号：TP301文献标识码：A文章编号：1673—1980(2010)0

2、6—0159—03Dijkstra和A—star算法不仅在解决路径搜索相关的应用中十分普遍，包括网络路由算法、机器人探路、人工智能、游戏设计等，而且在GIS的交通路线导航、路径分析领域应用更加广泛。它们是人工智能领域的一种图搜索策略。A—star算法采用了启发式函数对搜索过程中产生的分支进行评估，以选择最佳的分支进行搜索。它的实现关键在于建立一个合适的估价函数，估价函数构造得越准确，则搜索策略越优。一般搜索策略可以通过下面4个准则来评价【1·21：完备性、时间复杂性、空间复杂性和最优性。1相关定义为方便后续讨论。先对图和最短路径算法的相关概念作如下定义：定

3、义1

4、s为已经找到的从起点出发的最短路径的终点的集合：V是节点的集合。定义2分量Dist[i]表示从起始点到每个终点y，的最小权值，V；∈V。定义3带权的邻接矩阵Cost来表示带权的具有Ⅳ个节点的有向图，邻接矩阵Cost[i√]表示弧

5、6完备性：如果存在一个解答，该策略是否保证能够找到?定义7最优性：如果存在不同的几个解答，该策略是否可以发现最高质量的解答?2算法描述2．1Dijkstra算法Dijkstra算法的基本思路是：Dijkstra是一个按权值大小递增的次序产生最短路径的算法，它可用于计算从有向图中任意一节点到其他节点的最优路径。下面以邻接矩阵来描述该算法的实现过程【3．41。假定某向量的起始点在有向图中的序号为m，并设定该向量的初始值为：Dist[i]=Cost[m,i]，5={y。}，则按以下步骤：StepI选择yj，使得：Dist[j]=min{Dist[i]／Vf∈y—

6、S}yiEVyi就是当前求得的一条从矿。出发的最优路径的终点，令：S=SU{一}Step2修改从y。出发到集合y_s中任意一顶点％的最短路径长度。如果Dist[j]+Cost[j，k]

7、—star算法在智能导航中的应用分析2．2A—star算法A—star算法在宽度优先搜索的基础上引入了一个估价函数，每次并不是把所有可展的结点展开，而是利用这个估价函数对所有未展开的结点进行估价，从而找出最应该被展开的结点，将其展开，直到找到目标结点为止。其估价函数八n)定义为坂凡)i甙n)+^∽，其中烈n)为源节点到达当前节点的耗费，而^①)表示对从当前节点到达目标节点的耗费的估计，要求评估函数满足^∽≤^+(妨。它必须满足两个条件il，21：(1)矗㈤必须小于等于实际的从当前节点到达目标节点的最小耗费h+；(2：17m)必须保持单调递增。算法如下：Pr

8、ocedureA—starBegin把源节点放入队列Q；For(i=2，

9、括Ⅳ+1个节’』点所必需的分支因子。因此，Ⅳ+1=1+6H6丁+⋯