改进双向启发式搜索算法及其车载导航仪中应用
发布时间:2008/6/5 0:00:00 访问次数:452
|
摘 要： 介绍单车辆路径规划的有关算法，针对车载导航仪的应用，对双向启发式搜索算法进行了改进和优化，提出了可靠有效的搜索终止条件和搜索切换标准，给出了改进算法的流程。最后给出了四种算法的实际测试和比较结果。结果表明改进的双向启发式搜索算法快速高效。
关键词： 路径规划 启发式搜索算法 双向搜索算法
|
|
车载导航仪也称为车载定位和导航系统(vehicle location and navigation system。它的主要功能是利用全球定位系统(gps)获取定位信息并与电子地图进行匹配，以决定车辆的当前位置并用图形化方式显示；按要求规划从出发地到目的地的最优驾驶路线；按照预先设定的路线，自动根据车辆的位置向驾驶员提供操作指令引导驾驶；提供与电子地图相关的集成信息服务；提供无线通信服务等。车载导航仪把先进的全球卫星定位技术、地理信息技术、数据库技术、多媒体技术和现代通信技术综合在一起能够实时、高效地向驾驶员提供多种重要信息，具有很强的实用价值和广阔的市场前景。
路径规划是车载导航仪的重要功能模块。在开发车载导航仪过程中，为了实现路径规划模块，对单车辆路径规划算法进行了研究。
|
|
1 路径规划算法
所谓路径规划，就是在路网中找到任意给定两点之间的最优路径。最优的标准是旅行费用最小或最大。旅行费用可以是距离、时间或速度等因素。路径规划主要算法有：迪杰斯特拉(dijkstra)算法及其改进算法、启发式搜索算法、双向搜索算法和双向启发式搜索算法等。
迪杰斯特拉算法是解决两点之间最短距离的有效算法。算法的思想是从原节点开始，算法每前进一步，都找到一个与原节点之间费用（距离）最小的节点，直至找到所有节点离原节点的最小费用。该算法的特点是只要各段路径的费用非负，一定可以找到从原节点到各节点的最优解。缺点是需遍历所有节点。算法的运行时间为o slogn 1，其中n、s分别为路径节点和路段的总数。单车导航没有必要找到所有节点到原节点的最优路径。改进的迪杰斯特拉算法在找到目标节点的最优路径后，算法停止。其运行时间为o bd，其中b是各节点的平均后继节点数，d为算法的搜索深度，即遍历树的层数。
启发式搜索算法引入启发式估价函数f'n＝g n+h'n，其中gn表示从原节点到当前节点n的实际费用，h'n为当前节点ｎ到目标节点的估计费用。启发式搜索算法基本同于改进的迪杰斯特拉算法，唯一不同的是前者的费用是f'n，而后者为g n。估计费用h' n能引导算法优先搜索接近目标节点的节点，因此比改进的迪杰斯特拉算法有更快的速度。其运行时间为o bd。注意这里的d要比改进的迪杰斯特拉算法中的d要小。若路网中任意两点之间存在最优路径，而且估计费用满足可纳性，即h' n小于从节点n到目标节点之间的实际费用，那么通过该算法一定可以找到一条最优路径。
前面两种算法都是从原节点到目标节点没单一方向进行搜索的算法。双向搜索算法的思想是：不仅进行从原节点到目标节点的前向搜索，而且进行从目标节点到原节点的后向搜索。在单cpu硬件平台条件下，两个方向的搜索交替进行。成功实现双向搜索有两个条件，即合适的搜索停止条件和前向后向搜索切换标准。其算法时间为o bd/2。若双向搜索算法中加入估计费用函数，便是更快的双向启发式搜索算法１。
|
|
2 双向启发式搜索算法的改进和实现
2.1 算法的优化与改进
通过对双向启发式搜索算法的仔细分析，发现算法主要围绕两个表进行操作，即open表和close表。前者用于存放已经搜索但尚未确定最小费用的节点，称labbled节点；后者用于存放已经搜索且最小费用已知的节点，称scanned节点。后者也用于存放路径回朔指针等。对open表的主要操作有插入一个i节点insert i，删除费用值最小的节点delete 和减小其中某个节点i的费用decrease i。算法对open表的操作极为频繁。若用高效的数据结构来实现该表及其操作，可以提高算法的效率和速度。最后用有高效算法的最小堆4实现了open表及其操作，优化了算法。具体实现的函数如下：void filter_down int start int endofheap//由起点start从上而下排列堆；void decrease int node//更新减少堆中节点node的费用f'值；void filter_up int start //由起点start从下而上排列堆；void heap_create int maxsize //创建堆；void heap_destructor//析构函数；int insert int node//把节点node插入堆；int remove_min int &iminnode//删除堆中最小费用f'值的节点。
在实际的路网中，路段有不同的属性，如高速公路、收费路段、单行路段等。有些路段可能因修建或发生交通故障而暂时封闭。因此在进行路径规划时，算法应该考虑路网中路段的属性，才能进行符合实际的规划，否则理论上规划出来的最优路径可能是不通的。
|
摘 要： 介绍单车辆路径规划的有关算法，针对车载导航仪的应用，对双向启发式搜索算法进行了改进和优化，提出了可靠有效的搜索终止条件和搜索切换标准，给出了改进算法的流程。最后给出了四种算法的实际测试和比较结果。结果表明改进的双向启发式搜索算法快速高效。
关键词： 路径规划 启发式搜索算法 双向搜索算法
|
|
车载导航仪也称为车载定位和导航系统(vehicle location and navigation system。它的主要功能是利用全球定位系统(gps)获取定位信息并与电子地图进行匹配，以决定车辆的当前位置并用图形化方式显示；按要求规划从出发地到目的地的最优驾驶路线；按照预先设定的路线，自动根据车辆的位置向驾驶员提供操作指令引导驾驶；提供与电子地图相关的集成信息服务；提供无线通信服务等。车载导航仪把先进的全球卫星定位技术、地理信息技术、数据库技术、多媒体技术和现代通信技术综合在一起能够实时、高效地向驾驶员提供多种重要信息，具有很强的实用价值和广阔的市场前景。
路径规划是车载导航仪的重要功能模块。在开发车载导航仪过程中，为了实现路径规划模块，对单车辆路径规划算法进行了研究。
|
|
1 路径规划算法
所谓路径规划，就是在路网中找到任意给定两点之间的最优路径。最优的标准是旅行费用最小或最大。旅行费用可以是距离、时间或速度等因素。路径规划主要算法有：迪杰斯特拉(dijkstra)算法及其改进算法、启发式搜索算法、双向搜索算法和双向启发式搜索算法等。
迪杰斯特拉算法是解决两点之间最短距离的有效算法。算法的思想是从原节点开始，算法每前进一步，都找到一个与原节点之间费用（距离）最小的节点，直至找到所有节点离原节点的最小费用。该算法的特点是只要各段路径的费用非负，一定可以找到从原节点到各节点的最优解。缺点是需遍历所有节点。算法的运行时间为o slogn 1，其中n、s分别为路径节点和路段的总数。单车导航没有必要找到所有节点到原节点的最优路径。改进的迪杰斯特拉算法在找到目标节点的最优路径后，算法停止。其运行时间为o bd，其中b是各节点的平均后继节点数，d为算法的搜索深度，即遍历树的层数。
启发式搜索算法引入启发式估价函数f'n＝g n+h'n，其中gn表示从原节点到当前节点n的实际费用，h'n为当前节点ｎ到目标节点的估计费用。启发式搜索算法基本同于改进的迪杰斯特拉算法，唯一不同的是前者的费用是f'n，而后者为g n。估计费用h' n能引导算法优先搜索接近目标节点的节点，因此比改进的迪杰斯特拉算法有更快的速度。其运行时间为o bd。注意这里的d要比改进的迪杰斯特拉算法中的d要小。若路网中任意两点之间存在最优路径，而且估计费用满足可纳性，即h' n小于从节点n到目标节点之间的实际费用，那么通过该算法一定可以找到一条最优路径。
前面两种算法都是从原节点到目标节点没单一方向进行搜索的算法。双向搜索算法的思想是：不仅进行从原节点到目标节点的前向搜索，而且进行从目标节点到原节点的后向搜索。在单cpu硬件平台条件下，两个方向的搜索交替进行。成功实现双向搜索有两个条件，即合适的搜索停止条件和前向后向搜索切换标准。其算法时间为o bd/2。若双向搜索算法中加入估计费用函数，便是更快的双向启发式搜索算法１。
|
|
2 双向启发式搜索算法的改进和实现
2.1 算法的优化与改进
通过对双向启发式搜索算法的仔细分析，发现算法主要围绕两个表进行操作，即open表和close表。前者用于存放已经搜索但尚未确定最小费用的节点，称labbled节点；后者用于存放已经搜索且最小费用已知的节点，称scanned节点。后者也用于存放路径回朔指针等。对open表的主要操作有插入一个i节点insert i，删除费用值最小的节点delete 和减小其中某个节点i的费用decrease i。算法对open表的操作极为频繁。若用高效的数据结构来实现该表及其操作，可以提高算法的效率和速度。最后用有高效算法的最小堆4实现了open表及其操作，优化了算法。具体实现的函数如下：void filter_down int start int endofheap//由起点start从上而下排列堆；void decrease int node//更新减少堆中节点node的费用f'值；void filter_up int start //由起点start从下而上排列堆；void heap_create int maxsize //创建堆；void heap_destructor//析构函数；int insert int node//把节点node插入堆；int remove_min int &iminnode//删除堆中最小费用f'值的节点。
在实际的路网中，路段有不同的属性，如高速公路、收费路段、单行路段等。有些路段可能因修建或发生交通故障而暂时封闭。因此在进行路径规划时，算法应该考虑路网中路段的属性，才能进行符合实际的规划，否则理论上规划出来的最优路径可能是不通的。
 热门点击
推荐技术资料
| |
公网安备44030402000607
