A的改进路径规划算法.pdfVIP

第 7卷 第 4期 信 息 与 电 子 工 程 VO1．7．No．4 2009年 8月 INFORMATIONANDELECTRONICENGINEERING Aug．，2009 文章编号：1672-2892(2009)04-0326-04 A冰的改进路径规划算法 漆阳华，杨战平，黄清华 (中国工程物理研究院 电子工程研究所 ，四川 绵 阳 621900) 摘 要：通过对地 图数据的预处理和启发函数的设计 ，对 A 算法进行 了改进 。利用 VC++编 程实现改进算法，并在实际城市地 图上对改进算法进行 了验证，结果表明改进算法提高 了有哪些信誉好的足球投注网站最 优路径的成功率，同时解决了原算法易出现有哪些信誉好的足球投注网站死循环的问题，可适应不规则的城市路网。 关键词 ：路径规划；A{算法；启发函数 中图分类号：TUl98．1 文献标识码 ：A Improvedpathplanningalgorithm basedonA术algorithm QIYang—hua，YANGZhan—ping，HUANGQing—hua (InstituteofElectronicEngineering，ChinaAcademyofEngineeringPhysics，MianyangSichuan621900，China) Abstract：A algorithm wasimprovedbypre—beatingmapdataandselectingappropriatedevelopmental function．An experimentwascarried outbycodingwith VC++．Theresultshowed thatthe improved algorithm increasedsuccessrateofoptimalpathsearching，andsolvedrepetitionproblem ofA algorithm． Thisalgorithm couldadaptwelltoirregularcitypathnetwork． Keywords：pathplanning；A algorithm；developmentalfunction A 算法是建立在Dijkstra算法基础上的启发式有哪些信誉好的足球投注网站算法 l【】，其主要特点在于选择下一个路径节点时引人了已 知的路网信息 ，特别是 目标点信息 ，计算所有候选节点到 目标点之间的某种 目标函数 (比如最短距离、最小时间 等等)，以此作为评价候选节点是否属于最优路径节点的指标，优先选择具有最优 目标函数的候选节点作为下一 个路径节点。 根据实际路径规划 目的，可以设计多种 目标函数的最优路径，比如距离最短、时间最少、运输成本最低和拥 挤程度最小等等。尽管不同优化 目标可对应不同优化算法，但它们或多或少都与路段距离相关。不失一般性 ，本 文以起点与 目标点之间的最短路径作为优化 目标 ，探讨对A+算法的改进。 A算法被证明是最佳优先算法 2【】，然而实际城市路网的拓扑关系纷繁复杂，与理想网络差别较大 ，利用 A+ 算法进行最短路径规划时常会出现 “死循环”3【】，找不到起点与 目标点间路径，以至影响其实用性 4【J。本文拟对 A· 算法加以改进 ，使之适应路网复杂的城市导航应用。 l A 算法简介及其分析 1．1A·算法基本思想及实现步骤 A+算法的关键是确立如下形式的启发函数 ，() g(”)+ () (1) 式中：g(n)是从起点到候选节点实际花费的代价；h(n)是从候选节点到 目标点的估计代价。通过比较f(n)，选 取代价最小的候选节点作为下一路径节点。 A 算法的实现步骤如下： 1)以起点为第 1个路径节点，寻找与之相连的候选节点； 2)对与之相连的每一个候选节点，计算其启发函数值，选出函数值最小的节点作为下一个路径节点； 3)如果该节点