一种改进的 Dijkstra 算法在嵌入式 GIS中的应用

在实践中,Dijkstra算法是处理道路网络的最有效的算法之一。但Dijkstra算法每次都需要扫描节点集合中的所有节点,降低了算法效率。通过改变图的存储结构及搜索方法,减少了内存存储空间,缩短查询时间,提高了该算法在嵌入式GIS系统中路径优化的效率。     

Dijkstra算法在嵌入式GIS中的改进与研究

Dijkstra算法是求解嵌入式GIS系统中最短路径的经典算法,通过对Dijkstra算法进行分析,改变图的存储结构和搜索方法,采用基于矩形限制区域的二叉排序树改进算法,减少了内存存储空间,缩短了查询时间,在一定程度上优化了最短路径的计算过程,实际数据测试也表明了该算法的有效性。     

嵌入式空间数据库综合查询算法

嵌入式空间数据库一般作为嵌入式GIS的后端,为其提供对空间数据和属性数据的存储、搜索、查询等多项功能。其中,查询性能是直接影响嵌入式GIS运行效率的基本因素之一。该文对嵌入式空间数据库综合查询算法进行分类,提出并实现了先空间串行查询算法、先属性串行查询算法和并行查询算法,对该3种查询算法进行性能测试与比较,并给出了测试比较结果。     

嵌入式空间数据库综合查询算法

嵌入式空间数据库一般作为嵌入式GIS的后端,为其提供对空间数据和属性数据的存储、搜索、查询等多项功能.其中,查询性能是直接影响嵌入式GIS运行效率的基本因素之一.该文对嵌入式空间数据库综合查询算法进行分类,提出并实现了先空间串行查询算法、先属性串行查询算法和并行查询算法,对该3种查询算法进行性能测试与比较,并给出了测试比较结果.     

嵌入式环境下全文搜索系统的设计与实现

为了改善嵌入式环境下用户海量文本查询的方便性,提高文本查询速度、降低资源消耗,建立了一个用于Windows Mobile的全文搜索系统。利用委托机制进行异步搜索;利用正则表达式进行关键词的模糊或精确查询,设计了两种查询模式。搜索完毕统计搜索结果将含有关键词的文本信息及其存储路径以HTMl的形式返回,根据实际搜索数量可设置每屏显示的数量。开发了软件系统,实际数据测试结果表明了该系统的可用性和算法的高效性。     

基于J2ME的嵌入式公交查询系统的研究与实现

介绍了一个基于J2ME平台用于嵌入式设备的无线公交线路查询系统的总体结构和功能,该系统用于向移动设备用户提供各种公交信息的查询服务,重点讨论了系统的分层设计和公交换乘算法的实现。     

嵌入式电子地图的实现及路径查询优化

该文主要对桌面电子地图数据到嵌入式电子地图数据的转换进行分析,完成了MIF格式地图数据的解析,并引入Dijkstra最短路径算法,实现了路径查询优化。     

基于ＳＱＬ的ＸＭＬ查询的有效实现

讨论了关系数据库中利用ＳＱＬ语句实现ＸＭＬ查询的问题,首先提出了一个利用映射信息（映射图）将带正则路径表达式的ＸＭＬ查询重写为一组简单路径查询的算法,该过程中的一个关键问题的Ｋleene表达式不能直接利用映射图重写,为此,提出了利用路径实例的统计信息来扩展Ｋleene表达式的算法,然后,进一步描述了将简单路径表达式查询重写为ＳＱＬ查询的方法,这些算法在ＸＭＬ－关系系统原型ＶＸＭＬＲ中实现,初步性能研究表明提出了方法是有效的。     

一种新的移动查询路径选择方法

在移动查询路径选择中,约束关系和网络特性对路径选择都有较大的影响,根据这一特点提出了一种新的移动查询的路径选择方法。该方法先把一个查询分解成几个子查询并根据约束条件组合成几条备选路径,然后估算这几条备选路经的元组大小,最后通过查询路径选择算法在这几条备选的查询路径中找到较优的路径。该方法充分考虑了约束关系和网络特性这两个因素,实验表明该方法可以在几条备选路径中求得较优路径。     

城市交通智能查询系统的研究与设计

本文介绍了一个利用自然语言处理技术进行城市交通查询的系统。该系统采用正向搜索反向匹配算法进行分词提取出起点和终点,综合采用最少换乘次数算法和最短路径算法,使城市交通查询更加人性化、智能化。     

可变时滞系统的控制与仿真

炉温变化时硬质合金真空烧结炉的时滞常数变化很大，常规PID控制不能同时在高温段与低温段满足生产工艺提出的控制品质要求。本文在利用最小二乘法拟合出真空烧结炉时滞常数与炉温变化函数的基础上，PID参数采用经典的CHR整定算法随炉温变化实时整定，并利用MAT—LAB仿真软件对该控制算法在真空烧结炉中的应用进行了仿真研究，结果表明该算法能够实现对真空炉的有效控制，控制系统能够满意地跟踪设定的温度曲线。     

铁路运输特定经路算法的研究与实现

径路选择和经由计算是关系到铁路运输效率和效益的重要问题。文中阐述了径路计算的概念,讨论了特定经由要求的构成,以及以此为基础的经由规则,提出了铁路运输特定经路算法,在满足经由文件要求对原路径进行调整的同时,保证了路径调整后最短,实现了铁路运输特定经由最短路径的求解,其对应的经由规则也易于检查与维护。此算法解决了传统车流径路系统的计算难点,极大地方便了货物运输计划、技术计划、列车编组计划以及列车运行图的编制,提高了工作效率,同时保证了正确性。     

面向行车诱导的最优路径算法研究

路径诱导系统是交通信息系统的重要组成部分,其综合应用车载定位系统、数据库技术、信息处理技术、现代通讯技术以及网络通信技术等先进技术来获取丰富的交通信息并通过对信息的整合,以达到诱导驾驶员行为,为驾驶员提供最优行驶路径的目的。在路径诱导系统中,最优路径问题是其研究的核心和关键。本文在研究传统的Dijkstra算法的基础上引入一种新的最优路径搜索思想即直线优化法对其进行改进。直线法优化Dijkstra算法在搜索过程中一直趋向于目标节点,能够减少算法中遍历的节点个数,从而提高搜索速度。最后,对传统Dijkstra算法和直线法优化Dijkstra算法进行了对比仿真分析。仿真表明,改进的算法既优化了最优路径搜索的过程,又大大地缩短了其运行时间。     

多播环境下的增量式查询归并

在信息广播型应用中,数据从少数的“信息生产者”发送到广大的“信息消费者”．如果把“相似”查询归并,就可以通过多播技术避免重复数据发送,从而大大提高因特网上信息广播的效率．因为寻找最优查询归并集合属于ＮＰ完备问题,所以作者对此提出了复杂性较低的启发式算法,并讨论了如何增量式地维护所得到的查询归并集合．     

无线自组网AODV路由后备策略的改进算法

传统的自组网AODV-BR路由算法在主路径断裂时,并没有对断裂路径进行修复,对AODV-BR改进的AODV-IBR(Im-provementBackupRoute)算法,从后备路径中选择一条跳数最短的路径作为主要路径,实现对断裂路径的修复,有效提高数据传送率。     

数学形态学滤波器的优化设计

数学形态学滤波器作为图像处理领域中的一类重要的非线性滤波器已被广泛地用于图像降噪、边缘检测和模式识别等图像处理技术之中,然而其处理效果的好坏却严重地依赖于结构元素的形状和大小。在传统的形态滤波器的设计中,结构元素的选择完全凭借设计者的经验,因而很难保证所选择的结构元素为最优结构元素。针对此问题,该文应用遗传算法对形态滤波器设计中的结构元素进行优化,通过对样本图像的学习训练,获得基于优化结构元素的形态滤波器,并在此基础上设计了一种简单、实用的自适应优化滤波算法。该算法的有效性用计算机仿真实验进行了验证。     

移动自组网按需机制路由协议路径失效预测和局部修复算法

提出利用信号强度对将要断开的链路进行检测，并在局部利用路径请求—路径回答过程，找到替代路径，对原来的路径进行局部修复的算法。在尽量少增加路由开销的同时，达到提高路径修复的效果。同时对缓存器中路径设置失效时限，以免长时间未用路径时误用失效路径。在DSR协议上应用改进算法，在ns-2仿真环境中对6组不同场景进行仿真，验证算法正确，明显提高了移动自组网的性能。     

改进的蚁群－遗传算法在优化航线中的应用

航线优化是一个重要问题。提出的改进算法是先通过限制、选择和更新信息素、控制周游次数,找出航线的满意解,大大缩短了搜索时间;再用所得较好的航线表示作为初始种群,指定为父体,直接进行分组定界操作,将已得航线进行优化改良,求得最佳航线。实验结果表明,该算法应用于求解航线优化问题行之有效。     

基于最大似然估计的空间谱测向技术

介绍了基于最大似然估计（简称ML）的空间谱测向,ML是一种高分辨算法,常用于空间测向和谱估计等方面。文中首先介绍了ML测向原理,由于ML是一个非线性、多维的极值问题,需要全局极值的多维搜索,其计算量非常的巨大,因此采用了AP算法进行ML算法的优化,最后通过均匀圆阵对非相干信号和相干信号进行了ML测向的计算机仿真,仿真结果表明：一个阵列对空间多个信号的分辨能力除了与信噪比有关外,还与入射信号是否相干以及两相干信号的相位差有关,ML算法可以直接对相干的入射信号进行测向,但是信号的相干性会影响ML算法测向的角度分辨率,在两信号相关的情况下,两信号间的相位差越大则测向精度越高。     

An Efficient Approach for Solving Optimization over Linear Arithmetic Constraints

Satisfiability Modulo Theories (SMT) have been widely investigated over the last decade. Recently researchers have extended SMT to the optimization problem over linear arithmetic constraints. To the best of our knowledge, Symba and OPT-MathSAT are two most efficient solvers available for this problem. The key algorithms used by Symba and OPT-MathSAT consist of the loop of two procedures: 1) critical finding for detecting a critical point, which is very likely to be globally optimal, and 2) global checking for confirming the critical point is really globally optimal. In this paper, we propose a new approach based on the Simplex method widely used in operation research. Our fundamental idea is to find several critical points by constructing and solving a series of linear problems with the Simplex method. Our approach replaces the algorithms of critical finding in Symba and OPT-MathSAT, and reduces the runtime of critical finding and decreases the number of executions of global checking. The correctness of our approach is proved. The experiment evaluates our implementation against Symba and OPT-MathSAT on a critical class of problems in real-time systems. Our approach outperforms Symba on 99.6% of benchmarks and is superior to OPT-MathSAT in large-scale cases where the number of tasks is more than 24. The experimental results demonstrate that our approach has great potential and competitiveness for the optimization problem.