行满秩Toeplitz型矩阵Moore-Penrose逆的快速算法

通过构造对称分块矩阵给出了秩为m的m×n阶Toeplitz型矩阵Moore-Penrose逆的快速算法。该算法计算复杂度为O（mn）+O（m²）,而由T^T（TT^T）^-1直接求解所需运算量为O（m²n）+O（m3）。数值算例表明了该快速算法的有效性。     

网络中时延受限的代理服务器放置问题

该文考虑网络数据更新,需要控制代理服务器与客户的距离时,网络中的代理服务器的放置问题。找到代理服务器的最优数量和放置位置,使网络中数据访问的总花费（包括数据读取和更新）最小。利用二叉树结构和动态规划方法,得到了一个时间复杂度O（n²）的多项式时间算法,其中n为网络结点数。     

分组排序算法

提出了分组排序算法,详细分析了算法的原理及其时间与空间复杂度,得出了在最坏情况下的时间复杂度是θ（mn）;最好情况和平均情况下的时间复杂度均是θ（nlog（n/m^k））;在最坏情况下的空间复杂度是O（mn-m²＋m）;最好情况和平均情况下的空间复杂度均是O（m^klog（n/m^k））;并用多组随机数据与效率较高的快速算法进行仿真对比实验,试验结果说明了文中结论的正确性。这一结果,将有助于进一步设计高效的海量数据分析方法。     

并行最短路径搜索算法的设计与实现

针对串行最短路径搜索算法本身固有的局限性,难以随着网络规模的增大而提高搜索速度的问题,设计并实现了一种基于并行Dijkstra思想的并行最短路径搜索算法,使算法复杂度由O（N²）减少到O（N²/p+N*（p-1））,提高了算法的效率。实验结果表明,该算法搜索速度快且性能稳定,当结点数目相当庞大时,算法的优越性更加明显。     

基于动态规划的分批排序算法

研究了在给定截止期限（deadline）下的单机分批（batch）排序问题,目标函数是最大提前完工时间。由于工件不能延迟,因此先讨论了问题可行解的存在。当问题有可行解时,证明了工件按最早截止期限（Earliest Deadline,ED）规则的排序是一个最优排序,接着给出一个时间复杂度为O（n³）的动态规划算法来获得最优分批。     

RA码在分布式信源编码中的应用

介绍了分布式信源编码的基本原理和实现方法,说明了RA码的编译码原理,然后重点将RA码应用于分布式信源编码中并进行了仿真,在BSC信道下比较了与普通的基于LDPC的分布式信源编码的性能。仿真结果证明,使用基于RA码的分布式信源编码性能上略差于基于LDPC的方法,但编码复杂度却由原来的O（n²）降为O（n）。因此基于RA码的分布式信源编码器更适用于实时业务和需要低功耗的场合,并且能降低成本,应用前景乐观。     

用于WEB文档分类的并行KNN算法

针对WEB文档分类中KNN算法计算复杂度高的缺点,不同于以往从减少训练样本集大小和采用快速算法角度来降低KNN算法的计算复杂度,从并行的角度出发,提出一种在Hyper-cube SIMD模型上的并行算法,其关键部分的时间计算复杂度从O（n²）降为O（log（n））,该算法与传统的串行算法相比,能显著地提高分类速度。     

信息量不完备决策表属性约简的一种新算法

目前,基于不完备决策表的属性约简研究较少。基于信息量的不完备决策表属性约简是一种新的属性约简。由于在该属性约简中,计算相容关系是最主要的计算,也比计算等价关系要难得多。基于信息量的不完备决策表的属性约简算法的时间复杂度一般为O（|C|²|U|²）。为降低其时间复杂度,首先分析了老算法的不足,然后给出了一个效率较好的计算相容类的算法。最后设计了一个新的基于信息量的不完备决策表的属性约简算法,其时间复杂度为O（|C|²|U|²）。     

一种改进的中文字符串排序方法

对中文字符串排序,最快算法的时间复杂度是O（nlgn）。基数排序算法是目前最快的排序方法之一,时间复杂度是O（dn）,但其一般适用于相同长度的整型数据排序。提出了一种快速的变换方法,将字符串转换为与之等长的整型数组,使用基数排序算法对代表字串的整型数组排序,用以实现对字符串的快速排序。实验表明,提出的算法能快速地进行中文字符串排序,比快速排序算法具有更好的性能,且排序时间与数据规模之间是线性关系,算法的时间复杂度为O（dn）。     

高效的求解TSP问题的近似算法

提出了一种基于矩阵变换的方法,将n阶TSP问题近似转化为n-1阶TSP问题,然后用递归运算得出最后解。此算法的时间复杂度为O（n³）。而后又对此算法做了进一步的改进,近似度有很大提高但时间复杂度增加为O（n⁴）。经过实验表明,此类算法求解的近似度很高,尤其是在满足三角不等式的问题中,误差更低。利用TSPLIB数据库中的数据进行测试,得到的结果误差最多不超过10%。     

论两条直线段的求交

本文给出一种用计算机求两和直线段交点的算法，较之常用算法，本算法针对计算机的计算误差和几何元素在计算机内的表示误差，构造交点模糊判断树，使求两条直线段交点的正确性和可靠性有较大改进，并用于几何造型系统ＧＥＭＳ４．０，取得了较好的效果。     

一种线/群线GIS缓冲区构建实现新方法

GIS线目标缓冲区的构建通常采用平行线算法。但是当基线复杂时,会带来许多难以处理的问题,当基线为线群时更加难以解决。通过将基线分解为线段,分别构建线段的缓冲区并进行合并,可以避免这些复杂的情况。为了提高实现效率,构建了点、线、面间的拓扑关系并大量采用了向量代数的方法进行计算,同时对某些特殊情形进行了讨论。     

基于激光扫描的移动机器人行走环境直线检测

提出一种移动机器人行走环境直线检测算法;对激光传感器采集的环境信息作预处理,设计分割、提取规则将离散距离信息转化为具备明显特征的直线段序列,考虑传感器误差用最小二乘法拟合直线段;计算拟合误差作为直线分割提取的阈值自动调整条件,实现阈值自动调整.基于极坐标内直线协方差矩阵计算Mahalanobis距离,实现直线合并,不丢失环境信息同时降低其直线存储量.与传统的Split-and-Merge算法相比,解决了对分割阈值参数敏感的问题.经过实验证明:直线检测算法能够有效检测出直线特征.     

A Minimum Cost Approach for Segmenting Networks of Lines

The extraction and interpretation of networks of lines from images yields important organizational information of the network under consideration. In this paper, a one-parameter algorithm for the extraction of line networks from images is presented. The parameter indicates the extracted saliency level from a hierarchical graph. Input for the algorithm is the domain specific knowledge of interconnection points. Graph morphological tools are used to extract the minimum cost graph which best segments the network.We give an extensive error analysis for the general case of line extraction. Our method is shown to be robust against gaps in lines, and against spurious vertices at lines, which we consider as the most prominent source of error in line detection. The method indicates detection confidence, thereby supporting error proof interpretation of the network functionality. The method is demonstrated to be applicable on a broad variety of line networks, including dashed lines. Hence, the proposed method yields a major step towards general line tracking algorithms.     

具有约束条件的船舶运动预测控制

研究了船舶在航向偏差和转首角速度约束条件下的航向保持和航迹保持广义预测控制问题,以一步优化代替对控制量的多步优化,根据约束和状态预测值确定满足条件的加权系数的范围,在此范围内在线调整加权系数,保证了系统的状态始终满足给定的约束条件,仿真结果验证了算法的有效性。     

基于凸片段分解的多边形窗口线裁剪算法

将多边形窗口的边顺序地分割成一些片段，使得每个片段都能局部地形成一个凸多边形，称为凸片段，并建立一个二叉树来管理这些凸片段．在裁剪计算时，先根据二叉树快速地找到与被裁剪线段相交的凸片段，再利用高效的凸多边形线裁剪算法对这些凸片段进行裁剪操作．文中算法能有效地降低裁剪计算的时间复杂度，使其在O（logN）～O（N）之间自适应地变化，且大部分情况下时间复杂度小于O（N）．     

Algorithms for scheduling real-time tasks with input error andend-to-end deadlines

This paper describes algorithms for scheduling preemptive, imprecise, composite tasks in real-time. Each composite task consists of a chain of component tasks, and each component task is made up of a mandatory part and an optional part. Whenever a component task uses imprecise input, the processing times of its mandatory and optional parts may become larger. The composite tasks are scheduled by a two-level scheduler. At the high level, the composite tasks are scheduled preemptively on one processor, according to an existing algorithm for scheduling simple imprecise tasks. The low-level scheduler then distributes the time budgeted for each composite task across its component tasks so as to minimize the output error of the composite task     

室内环境下基于平面与线段特征的RGB-D视觉里程计

针对室内环境的结构特点,提出一种使用平面与线段特征的RGB-D视觉里程计算法．首先根据RGB-D扫描点的法向量对3D点云进行聚类,并使用随机抽样一致（RANSAC）算法对每簇3D点集进行平面拟合,抽取出环境中的平面特征;随后利用边缘点检测算法分割出环境中的边缘点集,并提取出环境中的线段特征;然后提出一种基于平面与线段几何约束的特征匹配算法,完成特征之间的匹配．在平面与线段特征匹配结果能提供充足的位姿约束的条件下,利用特征之间的匹配关系直接求解RGB-D相机的位姿;若不能,则利用匹配线段的端点以及线段点集来实现RGB-D相机位姿的估计．在TUM公开数据集中的实验证明了选择平面与线段作为环境特征可以提升视觉里程计估计和环境建图的精度．特别是在fr3/cabinet数据集中,本文算法的旋转、平移的均方根误差分别为2.046°/s、0.034m/s,要显著优于其他经典的视觉里程计算法．最终将本文系统应用到实际的移动机器人室内建图中,系统可以建立准确的环境地图,且系统运行速度可以达到3帧/s,满足实时处理的要求．     

基于中值夹角链码的掌静脉特征提取

结合夹角链码的特点,提出一种改进的提取手掌静脉结构特征的方法：中值夹角链码。通过中值迭代将细化后的静脉纹理曲线段用一组变长线段拟合,用距离法计算其拟合误差,在允许的误差下,根据相邻线段间的斜度差形成一串角度序列并计算中值夹角链码。实验结果表明,该方法保证了拟合精度,有效地提取出掌静脉结构特征,同时减少了计算量。     

基于神经网络和PID算法的数控机床并行混合控制模型

针对数控机床低速运动时由于非线性摩擦造成的问题，提出了一种基于神经网络和PID算法的并行混合控制模型．当电机速度大于转换速度时使用PID控制，小于转换速度时使用神经网络控制器．神经网络为5个输入的单神经元，采用Hebb学习算法．分析表明，混合控制器使跟随误差的波动明显减小，机床运动变得平稳．利用可由用户编写伺服算法的多轴运动控制器(PMAC)进行了实验，验证了混合控制器的控制效果．