快速动态优先搜索树的实现及其应用

对形如（x1：x2,[-∞：y]）的二维查询问题,提出一种快速的、易于实现的动态优先搜索树数据结构及其相关算法,采用只在叶节点存储数据的结构,以及在常数时间内实现旋转操作的算法。设n为数据点的个数,k为满足搜索条件的解的个数,则该动态搜索树空间复杂度为O（n）,插入、删除操作的时间复杂度为O（10gn）,搜索复杂度为O（logn＋k）。     

基于加权分治技术的set packing精确算法

加权分治技术是算法分析中的一种新技术,该技术基于选择不同的量来描述分支子问题的大小,以求得到在最糟糕情况下最好的时间复杂度.set packing问题是一典型的NP-hard问题,广泛应用于调度、代码优化和生物信息学等领域.本文对有n个子集的set packing问题,引入符号全集变量N设计基于分支搜索策略的递归算法,并应用加权分治技术对算法加以分析,得到时间复杂度为O*(1.1686n+N) 的精确算法,当N≤n/4时,比现有最佳的算法O*(1.2209n)更加有效.     

基于改进搜索策略的Live-Wire医学图像分割算法

Live-Wire 分割算法提供了一种精确的、可再现的交互式医学图像分割方法。Live-Wire算法中最优路径的搜索通常采用Dijkstra算法,其时间复杂度为O[n2]。提出从两个方面对Live-Wire医学图像分割算法的搜索策略进行改进以提高Live-Wire算法的实时性：（1）在最短路径的搜索过程中应用二叉堆排序,使算法的时间复杂度从原来的O[n2]降为O[n ln n];（2）在最短路径搜索中加入到达目标节点即停止的限制条件,可明显减少搜索节点数,使算法的时间复杂度远小于O[n ln n]。经算法分析及实验表明,搜索策略的改进可显著提高Live-Wire算法的运行效率。     

禁忌搜索在栅格地图中的应用

以禁忌搜索算法为基础,对栅格地图搜索过程进行建模,提出一种能够利用经验知识的改良禁忌搜索算法,为航向指引、水源探测、灾后搜救等领域的智能辅助工具实现提供算法参考。对禁忌搜索算法的关键优势进行分析,提出以正六边形为单元的地图栅格划分方法,将问题建模为禁忌搜索可求解的最优化问题。以沙漠水源搜索为实例,选取多个沙漠元素作为水源探测相关指示参数,进行仿真实验。实验表明,本文所提出的方法可以在10000以内单元格数目的栅格地图中,搜索路径的成功规划次数占比达到91.7%以上,相比于“爬山法”策略提高至少36.68个百分点,搜索耗费的步数相比于遍历策略优化88.4%以上。     

基于立方体剖分的传感器网络快速三维k-覆盖判定算法

提出了一种传感器网络中基于立方体剖分的三维k 覆盖快速判定算（CP-RTCDA）和三维最大k 覆盖问题的快速求解算法（CP-RTMCDA）。算法首先把感兴趣区域剖分为立方体区域，从而将复杂的空间区域覆盖问题转化为简单的立方体区域覆盖问题。理论分析与仿真实验表明, 针对具有n个节点的传感器网络, 新算法的计算时间复杂度为O(n)，远低于已有算法O(n3logn)的计算时间复杂度。     

基于量子计算机的数据库搜索

Grover提出的量子搜索算法,可以用O(N1/2)的时间复杂度完成对规模为N的非结构化数据集的搜索,这在经典计算机上需要O(N)的复杂度。其中量子黑盒(又称为Oracle)依赖于具体问题,根据数据库搜索的要求,设计了量子黑盒的内部结构和相应的量子线路,给出了适合于数据库搜索的量子算法。     

SIMD-LA模型上的大整数乘法

本文提出了一种基于SIMD-LA模型的大整数乘法的算法,将分治策略与Karatsuba-Offman算法相结合改进了已有的算法.当使用p台处理器,大整数长度n＜=256p时,其时间复杂度为O(p);大整数长度n＞256p时,其时间复杂度为O(p[n]1.58/|p|+p).其时间复杂度比传统算法有了进一步的提高.     

基于八数码游戏的两种搜索策略的比较

利用状态空间法描述八数码问题,将其抽象成为一个从起始状态搜索到达目标状态的路径的问题。并在Visual C++6.0环境下,用C++语言实现了其盲目搜索和启发式搜索算法。其中,盲目搜索采用的是宽度搜索和深度搜索,启发式搜索策略采用的是有序搜索。通过比较两种搜索策略的时间复杂度和空间复杂度,得出结论:在搜索步骤较多的情况...     

测试用例生成算法TCBSA研究

软件测试过程中的一个重要任务是生成测试用例,但目前有些测试用例生成方法存在的一些问题限制了它们的使用,如利用动态测试用例生成方法获取合适的测试用例需要进行大量的迭代。提出了一种在面向路径的测试用例生成中使用熟知的二分搜索策略生成测试用例的形式化体制,同时设计了一种测试用例二分搜索算法。该算法确定一个测试用例的迭代次数被限制在O(mnlog｜D｜)内。     

最长递增子序列问题研究

本文采用分治策略和动态规划策略探讨了最长递增子序列问题的两种解法,并分析了算法的计算复杂度。结果表明,本文算法的时间复杂度和空间复杂度分别为O(nlogn)和O(n)。     

Learning concepts in parallel based upon the strategy of versionspace

Applies the technique of parallel processing to concept learning. A parallel version-space learning algorithm based upon the principle of divide-and-conquer is proposed. Its time complexity is analyzed to be O(k log₂n) with n processors, where n is the number of given training instances and k is a coefficient depending on the application domains. For a bounded number of processors in real situations, a modified parallel learning algorithm is then proposed. Experimental results are then performed on a real learning problem, showing that our parallel learning algorithm works, and being quite consistent with the results of theoretical analysis. We conclude that when the number of training instances is large, it is worth learning in parallel because of its faster execution     

一种改进的点在多边形内外判断算法

为解决多边形内外算法中BSP树退化为链表的问题,提出一种改进的点在多边形内外的判断算法。在构建水平扫描线的BSP树之前,对水平扫描线按照Y值进行排序,将排好序的水平扫描线按照二分法的顺序插入到BSP树中,其查找时间复杂度为O(lbn)。实验结果表明,该算法在不增加BSP构建时间复杂度的前提下,能够保证BSP树的查找效果总是最优的,且简单易行,具有较好的通用性。     

构造二叉树的两个改进算法

在数据结构中,已知一棵二叉树的先序序列和中序序列,可唯一确定此二叉树.本文在分析建立二叉树经典算法的时间复杂度的基础上,给出了两个改进算法:①利用哈希函数,使得改进后的算法在最差情况下,时间复杂度由O(n2)降为O(n);②利用栈和控制输入的结点序列构造二叉树,时间复杂度也由O(n2)降为O(n).     

基于EREW的后序遍历二叉树算法

针对单处理器后序遍历二叉树的时间复杂度为O（n）问题,提出了在EREW PRAM并行计算模型下一种后序遍历二叉树的算法。将后序遍历二叉树的边构造一个单链表,使用指针跳越技术对单链表进行表序问题求解,从而得到后序遍历二叉树结点的顺序。得出了运用该算法将时间复杂度从O（n）减少到O（logn）的结论。     

深度优先稳定原地归并排序的高效算法

基于分治策略,使用深度优先的方法,提出了一种用于线性表的稳定原地归并排序算法,其时间复杂度为O(n lb n),辅助空间复杂度为O(1),递归栈空间复杂度为O(lb n),同时进行了算法分析和实验测试。实验结果表明,该算法效率较STL中的稳定原地归并排序算法有67.51%的提升,解决了稳定排序算法中要么时间复杂度高要么空间复杂度高的问题。     

基于概念的折半查找算法

自顶向下或自底向上两种标准查找方式不适合于具体领域逻辑,且缺乏灵活性.模拟有序数组中的折半查找,提出逻辑空间上的折半查找方法,证明该查找方法在保持完备性和非冗余性的同时,还提供了更好的灵活性,最后给出了该查找的通用算法,并分析其复杂性.     

改进的二分法查找

当前有很多的查找算法,其中在对有序数列的查找算法中二分法查找（binary search）是最常用的。利用二分法,在含有n个元素的有序数列中查找一个元素的最大比较次数为[logn]＋1。在很多情况中,在查找之前有序数列分布的很多信息为已知,比如说如果知道了有序数列中每相邻两个元素之差的最大值的一个上界,就可以有比二分法更加有效的查找算法。文章给出了一个称之为改进的二分法查找算法。改进的二分法查找性能明显优于二分法查找,受数列分布的影响,其最坏情况下查找一个元素的最大比较次数在1和[logn]＋1之间,明显优于二分查找的[logn]＋1。在实际应用中利用改进的二分法可以极大地提高查找效率。     

一个多维数据搜索算法

本文提出了一种使用二叉树组织多维数据的数据结构,在这种结构下提出了一个区域搜索算法,确定空间中给定点的区域内所有在给定数据集中的点,搜索效率与维数无关,算法的平均时间复杂性为O(logn),为了保证算法的效率,提出了一种平衡树操作算法。     

基于改进蚁群算法的火源定位策略研究

为了达到多机器人系统能够模仿蚁群寻找食物源的行为来定位搜索火源目标,对基本蚁群算法和禁忌搜索算法进行融合和修正,形成一种新的目标搜索策略。修正的蚁群算法包括：全局随机搜索、局部遍历搜索和信息素更新三个部分。在搜索过程中,通过设定信息素的有效作用范围来实现对多个火源目标的定位。仿真结果表明,局部遍历搜索能够保证机器人逐步靠近火源目标,而融合了禁忌搜索的蚁群算法在搜索效率上大大提高。