基于优化的CAS算法实现线程安全的HashMap

HashMap内存数据结构存在相当广泛的应用场景,通过Hash函数的Key直接获取对应的值,能够确保搜索的时间复杂度为O(1)。HashMap数据结构存在哈希冲突与线程安全问题,悲观锁机制实现线程安全的方法存在很大的性能开销。本文提出了基于优化的CAS算法,实现线程安全的哈希映射数据结构,内部采用数组、链表和红黑树实现了高并发环境下读写操作。通过增加版本戳避免CAS算法的ABA问题,CAS算法实现的无锁方式避免了锁竞争的开销,使用红黑树来优化链表,确保大规模数据集的检索时间复杂度保持O(logn)。支持多线程扩容操作,在执行效率方面有良好的表现。通过大规模的并发压力测试,验证了该数据结构在性能上有稳定的提升。     

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

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

基于CREW遍历图的一种并行算法

针对串行算法模型下基于顶点遍历图的情况，提出了一种在CREWPRAM并行模型下遍历无向图的算法。该算法是找出无向图的一棵最短路径生成树，由向上和向下两条有向边替换最短路径生成树的每条边形成欧拉回路，运用欧拉回路技术计算前缀和，前缀和所对应的顶点即为遍历无向图的顺序。得出了该算法时间复杂度为O（n＋logn）的结论。     

逆序树在求解一维数组最长升序序列问题中的应用

针对一维数组中求最长升序序列问题,在研究树形结构和分析任务需求的基础上,提出采用区别于传统树的逆序树结构进行计算,采用深度优先算法策略查找路径。逆序树采用子节点指向父节点的节点逆序指向方式,在建树过程中不用为每个节点考虑子节点的数量,克服了不可预见的存储分配和节点指向问题,能有效地找出全部升序路径,最终找出一维数组中全局最长的升序序列。在此基础上实现的Java程序验证了逆序树结构的有效性。     

最小生成树算法在旅行商问题中的应用

如何在n个顶点之间的1/2(n-1)!巡回路径中选择距离最短的,这是一个典型的组合优化问题,也是解决旅行商问题的根本。在最小生成树的基本思想上进行了改进,成功地解决了旅行商问题。     

基于树分解结构的Top-k最短路径查询算法

基于树分解原理及性质,本文运用启发式树分解方法将图转换为树结构,并对分解树进行预处理,在这些预存储的索引信息中查询Top-k最短路径。将树分解索引结构应用到Yen算法,通过解决树分解结构上的限制性路径查询,即Top-1最短路径查询,依次循环求解出Top-k最短路径查询。本算法并没有改变Yen算法最坏情况下的时间复杂度,而是通过分解树上的索引信息在分解树上递归查找,快速查找出最短路径。实验结果表明,基于树分解结构的Top-k最短路径查询算法比Yen算法的查询效率高,且存储索引信息在可接受范围内。     

旅行商问题的DNA算法

旅行商问题是求仅一次遍访指定城市并返回出发城市的最短旅行路线的问题,它是图论中一个经典的NP完全问题,用电子计算机需要指数级的时间才能得到解决,该文基于分子生物技术并利用Adleman-Lipton模型给出旅行商问题的DNA算法,这个DNA算法理论上能在多项式的时间内解决这个NP完全问题。具体地对n个城市的旅行商问题,首先将它视为一个具有顶点和边的图,并将顶点、边分别用DNA链编码表示,边的方向通过顶点的编码获得;再将这些DNA链投放在试管中进行生物化学反应,利用DNA计算的高效并行性,通过基本的生物实验操作最后得到旅行商问题的解,其过程的复杂度为O(n)。该算法的创新之处在于表示城市和路径的DNA链长度的设计,能使我们在合理小的范围内寻找旅行商问题的解,较大地简化了问题的复杂度。     

基于AVL搜索树的证书吊销系统

针对公钥基础设施中的证书吊销问题,提出一种基于AVL。搜索树的解决方案,该方案在查询与更新时的最大时间复杂度始终保持在O（lbn）量级。实验结果表明,该方案是有效的,且对工程实现具有一定指导意义。     

外包数据库模型中的完整性检测方案

外包数据库模型中完整性保护的目标是防止数据库服务提供商篡改数据库内容,完整性检测方案的作用是让查询方能够验证查询结果是真实的、未被篡改的.在现有的基于验证数据结构方法的基础上进行改进,提出了一种以带掩码的验证树作为核心数据结构的完整性检测方案,给出了数据结构的形式化定义并证明了其安全性.该方案将数据结构中共同的计算信息抽取到两个掩码向量中,通过避免使用大量幂指数运算,降低了查询验证过程的计算代价,减少了查询验证的时间.其特有的验证数据结构增量更新的优点能够提高数据库更新的执行效率.实验表明,该方案在查询验证时间上略优于现有的同类型方案,在数据更新性能上较同类方案具有明显优势.     

路网中基于地理位置和区域封闭性的最短路径的查询算法

针对大规模城市路网寻找最短路径的问题,提出了一种基于边的聚类树(ECT)和最小封闭格(MCL)的算法来达到路网中快速查询的目的。首先对给定的城市路网进行预处理,即利用封闭格的定义对路网进行划分;其次利用ECT树对划分出的MCL格进行存储;最后利用虚拟路径的思想(两点之间直线距离最短)并结合MCL格的性质和路网的平面性的特点,利用ECT树存储的优势,在查询中大大减少了无用节点的访问数量,降低了时间复杂度,从而达到了快速寻找最短路径的目的。理论分析和仿真实验表明,在大规模的城市路网中ECT树的存储空间相比PCPD算法减少了约45.56%,相比TNR算法减少了24.35%,其在存储方面略优于较为完备的SILC算法。MCL算法在查找过程中的搜索效率比SPB算法快15.6%。实验结果表明基于ECT存储的MCL算法在实际查询过程中能提高查询的效率。     

The period traveling salesman problem: a new heuristic algorithm

A new, simple and effective heuristic algorithm has been developed for the period traveling salesman problem. Computational results obtained from the test problems taken from the literature indicate that the algorithm compares well in terms of accuracy with other existing algorithms, finding a larger number of best solutions. Moreover, its average percentage error and its worst ratio of solution to the best-known solution are smaller than those of the other existing algorithms.Scope and purposeIn the period traveling salesman problem, a traveling salesman must visit each city a fixed number of times over a given m-day planning period. Each city specifies a set of sequences of visit days and the visit days are assigned to the city by selecting one of these sequences. Moreover, for each day of the planning period, a not empty tour must be generated by connecting the salesman home city and the cities that must be visited on that day. The salesman objective is to minimize the total distance traveled over the entire m-day period. For this problem, arising in various situations such as mail delivery or lawn-care services, the paper proposes a simple and effective heuristic algorithm where an improvement procedure is embedded within a tour construction type procedure.     

求解TSP问题的多级归约算法

TSP(traveling salesman problem)问题是最经典的NP-hard组合优化问题之一.长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的计算时间内解决大规模问题.由于对较大规模的问题,目前的近似算法尚不能在较短的时间内给出高质量的解,因此提出了多重归约算法.该算法的基本原理是通过对TSP问题的局部最优解与全局最优解之间关系的分析,发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解.利用这些部分解可以大大缩小原问题的搜索空间,同时也不会降低搜索的性能.这就是所谓的归约原理.再通过多次归约使问题的规模降到足够小,然后对这个较小规模的实例直接用已有的算法求解,最后通过相反的次序拼接部分解,最终得到一个合法的解.在TSPLIB(traveling salesman problem library)中,典型实例上的实验结果表明,此算法在求解质量和求解速度上与目前已知的算法相比有较大的改进.     

A theoretical investigation into the performance of the Hopfieldmodel

An analysis is made of the behavior of the Hopfield model as a content-addressable memory (CAM) and as a method of solving the traveling salesman problem (TSP). The analysis is based on the geometry of the subspace set up by the degenerate eigenvalues of the connection matrix. The dynamic equation is shown to be equivalent to a projection of the input vector onto this subspace. In the case of content-addressable memory, it is shown that spurious fixed points can occur at any corner of the hypercube that is on or near the subspace spanned by the memory vectors. Analysed is why the network can frequently converge to an invalid solution when applied to the traveling salesman problem energy function. With these expressions, the network can be made robust and can reliably solve the traveling salesman problem with tour sizes of 50 cities or more.     

一种新的求解ATSP问题的PBIL算法

该文将二进制的人口增量学习算法(PBIL)改进为整数(集值)形式(multiplePBIL),并提出了一种新的基于城市间连接关系的非对称旅行商问题(ATSP)的解法。这种解法结合了集值人口增量学习算法和TSP问题的启发式搜索3-opt加强方法。混沌定位,分布式随机遍历构架和判断进化结束条件的可能性分布的熵的确定是该解法的三大创新之处。     

A memetic algorithm for the generalized traveling salesman problem

The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The recent studies on this subject consider different variations of a memetic algorithm approach to the GTSP. The aim of this paper is to present a new memetic algorithm for GTSP with a powerful local search procedure. The experiments show that the proposed algorithm clearly outperforms all of the known heuristics with respect to both solution quality and running time. While the other memetic algorithms were designed only for the symmetric GTSP, our algorithm can solve both symmetric and asymmetric instances.     

Adapting the traveling salesman problem to an adiabatic quantum computer

We show how to guide a quantum computer to select an optimal tour for the traveling salesman. This is significant because it opens a rapid solution method for the wide range of applications of the traveling salesman problem, which include vehicle routing, job sequencing and data clustering.     

Effective splaying with restricted rotations

The splay tree is a well-known binary search tree with many remarkable properties. It is a self-adjusting data structure whose amortized performance matches any of the many forms of balanced search trees. Furthermore, splay trees are adaptive, and have superior performance in many specialized cases. It is a long-standing open problem whether splay trees are dynamically optimal. Most search tree algorithms are based on the fundamental rotation operation. In 2002 Cleary introduced the concept of restricted rotations, which severely limits where the rotation can be performed. We show that splaying can still be effected using only restricted rotations, while maintaining the same properties as regular splay trees.     

Hybrid control systems and the dynamic traveling salesman problem

A new approximate algorithm for solving the dynamic traveling salesman problem (DTSP) is proposed; the traveling salesman starting from the base city visits megapoleis and cities inside megapoleis and comes back to the base city. A specific feature of this variant of DTSP is the movement of cities inside megapoleis in time. To solve this problem, a general solution theory for hybrid (complicated) systems with “combinatorial” and “continuous” path segments is developed. The general theory is based on the sufficient optimality conditions known in the theory of optimal control.