基于理想点法的多目标最短路求解算法研究

为了简化多目标最短路算法并解决不同度量单位之间存在的换算问题,利用理想点法的优点,探索出一种多目标最短路问题的简便算法。该算法首先确定理想点,计算各目标的k-最短路路径,这些路径组成一个存在可能解的集合,然后对所有的最短路目标值进行归一化处理,并确定所有路径归一化之后的目标值与理想点之间的加权欧几里得距离,从路径集合中寻找与理想点距离最近的路径,该路径即为多目标最短路问题的满意解。最后,给出了算法分析和算法流程,并通过一个虚拟运输网络对算法进行了验证。结果表明:这种算法能够解决多目标最短路问题中不同目标度量单位之间换算或相互矛盾的问题,并能够把复杂的非线性函数转换为简单的线性函数,是一种简单、有效的算法。

基于人体身型曲线特征的身份鉴定技术

研究人体身型特征的身份识别,提高身份准确性问题。针对传统的人体身份识别技术,都是用直线距离近似表示人体身型的几何特征,但是人体身型中的大部分真实几何特征距离都是空间曲线距离,会导致测量的身型几何特征结果不够精确,造成后期的身份识别准确性不高的问题。为了解决上述问题,提出一种基于近似曲线几何特征的身份鉴定方法,运用近似曲面分割逼近技术,求出人体身型几何特征点之间的最短近似路径,运用多个最短路径逼近方法,准确获得人体真实的身型几何特征信息。实验结果表明,改进的方法能够准确提取三维人体身型几何特征,使得身份识别准确率大幅增加。

基于元胞自动机的应急疏散最短路径优化算法

为科学、高效地规划应急疏散最短路径,建立人员对障碍物的绕行距离场,提出一种基于元胞自动机的全局最短路径(GSPCA)优化算法;设置GSPCA2D和GSPCA3D等2种求解模式,并将该算法与基于欧氏距离的启发式搜索算法(A*算法)进行最短路径规划对比试验,分析GSPCA算法的特点和适用性。结果表明:与A*算法相比,GSPCA优化算法搜索结果全局性更好,可避免出现贴壁绕行现象,其最短路径平均缩短12. 39%(GSPCA2D)、16. 82%(GSPCA3D);GSPCA算法能考虑地形因素,可根据地形特征和实际应用需求合理选择求解模式。

动态时间弯曲距离精确计算的Dijkstra方法

将动态时间弯曲距离(DTW)的差异矩阵一一对应于点阵,按DTW定义的行走规则对该点阵连线定向,使所对应点阵成为一个有向图,然后使用一个加权技巧对该有向图的边加权后得到一个加权有向图,于是把求DTW的精确计算问题等价地转化为求一个有向图起点到终点的最短路长,从而使图论中求两点间最短路径的方法如目前公认的经典Dijkstra算法均可用于求DTW,因此间接地找到了精确计算DTW的一个新方法.

访问平面内不相交线段ESP问题的最优求解算法及其验证

针对依次访问平面内一组互不相交线段的ESP问题,以Rubber-band算法为基础,提出一个改进的Rubber-band算法.该算法通过引入分而治之方法来减少算法的迭代次数.设计一个测试数据自动生成算法并随机生成4个测试数据集,实际运行改进前后的两个算法,采用事后分析方法对两个算法的运行时间性能进行对比分析.结果表明:改进算法的时间复杂度为O(n),优于时间复杂度为O(n2)的Rubber-band算法,是一个时间性能最优的ESP问题的求解算法.

典型城市路网中的椭圆最短路径算法

提出了一种高效可靠的限制搜索区域的最优路径算法.该算法是基于典型城市路网的共同特征,而不是某个特定城市的统计信息提出的,它可以应用在不同的城市路网中.针对从源站点到目的站点不同的欧式距离,算法分别在两类不同大小的椭圆内搜索最短路径.理论计算和实验结果都表明,当源站点和目的站点相距较远时,与椭圆限制搜索区域算法相比,该算法可以降低33%47%的时间复杂度,而不会影响查询结果的准确性.