Research on the adaptive hybrid search tree anti-collision algorithm in RFID system

Due to more tag-collisions result in failed transmissions,tag anti-collision is a very vital issue in the radio frequency identification(RFID) system.However,so far decreases in communication time and increases in throughput are very limited.In order to solve these problems,this paper presents a novel tag anti-collision scheme,namely adaptive hybrid search tree(AHST),by combining two algorithms of the adaptive binary-tree disassembly(ABD) and the combination query tree(CQT),in which ABD has superior tag identification velocity and CQT has optimum performance in system throughput and search timeslots.From the theoretical analysis and numerical simulations,the proposed algorithm can colligate the advantages of above algorithms,improve the system throughput and reduce the searching timeslots dramatically.

基于自动终止准则改进的kd-tree粒子近邻搜索研究

对于大规模运动模拟问题而言,近邻点的搜索效率将对整体的运算效率产生显著影响。本文基于关联性分析建立kd-tree的最大深度dmax与粒子总数N的自适应关系式,提出了kd-tree自动终止准则,即ATC-kd-tree,同时还考虑了叶子节点大小阈值n_(0)对近邻搜索效率的影响。试验表明,ATC-kd-tree具有更高的近邻搜索效率,相较于不使用自动终止准则的kd-tree搜索效率最高提升46%,且适用性更强,可求解不同N值的近邻搜索问题,解决了粒子总数N发生改变时需要再次率定最大深度dmax的问题。同时,本文还提出了网格搜索法组合坐标下降法的两步参数优化算法GSCD法。通过2维阿米巴虫形状的参数优化试验发现,GSCD法可更为快速地率定ATC-kd-tree的可变参数,其优化效率比网格搜索法最高提升了205%,相较于改进网格搜索法最高提升了90%。研究结果表明,ATC-kd-tree和GSCD法不仅提高了近邻搜索的效率,也为复杂运动中近邻粒子搜索问题提供了一种更为高效的解决方案,能够显著降低计算资源的消耗,进一步提升模拟的精度和效率。

Limiting theorems for the nodes in binary search trees

We consider three random variables X_n, Y_n and Z_n, which represent the numbers of the nodes with 0, 1, and 2 children, in the binary search trees of size n. The expectation and variance of the three above random variables are got, and it is also shown that X_n, Y_n and Z_n are all asymptotically normal as n→∞by applying the contraction method.

Blocking optimized SIMD tree search on modern processors

Tree search is a widely used fundamental algorithm. Modern processors provide tremendous computing power by integrating multiple cores, each with a vector processing unit. This paper reviews some studies on exploiting single instruction multiple date （SIMD） capacity of processors to improve the performance of tree search, and proposes several improvement methods on reported SIMD tree search algorithms. Based on blocking tree structure, blocking for memory alignment and dynamic blocking prefetch are proposed to optimize the overhead of memory access. Furthermore, as a way of non-linear loop unrolling, the search branch unwinding shows that the number of branches can exceed the data width of SIMD instructions in the SIMD search algorithm. The experiments suggest that blocking optimized SIMD tree search algorithm can achieve 1.6 times response speed faster than the un-optimized algorithm.

Nearest neighbor search algorithm for GBD tree spatial data structure

This paper describes the nearest neighbor (NN) search algorithm on the GBD(generalized BD) tree. The GBD tree is a spatial data structure suitable for two-or three-dimensional data and has good performance characteristics with respect to the dynamic data environment. On GIS and CAD systems, the R-tree and its successors have been used. In addition, the NN search algorithm is also proposed in an attempt to obtain good performance from the R-tree. On the other hand, the GBD tree is superior to the R-tree with respect to exact match retrieval, because the GBD tree has auxiliary data that uniquely determines the position of the object in the structure. The proposed NN search algorithm depends on the property of the GBD tree described above. The NN search algorithm on the GBD tree was studied and the performance thereof was evaluated through experiments.

Heru Search Method—Unique in the World that Uses Unprecedented Mathematical Formulas and Replaces the Binary Tree Breaking Various Paradigms Like 0(log<i>n</i>)

This paper deals with the efficiency of the search, with a method of organization and storage of the information that allows better results than the research trees or binary trees. No one ever dared to present better results than 0(log n) complexity, and when they wish to improve, they use balanced trees, but they continue to use principles that do not impact the pre-semantic information treatment. The Heru search method has as main characteristic the total or partial substitution of the use of the binary trees, enabling the elimination of the approximate results and informing the user the desired information instead of occurrences by sampling outside the desired information. The breakdown of the 0(log n) paradigm and the refinement of the searches are achieved with the use of a set of unpublished mathematical formulas and concepts called Infinite Series with Multiple Ratios.

Parametrically Optimal, Robust and Tree-Search Detection of Sparse Signals

We consider sparse signals embedded in additive white noise. We study parametrically optimal as well as tree-search sub-optimal signal detection policies. As a special case, we consider a constant signal and Gaussian noise, with and without data outliers present. In the presence of outliers, we study outlier resistant robust detection techniques. We compare the studied policies in terms of error performance, complexity and resistance to outliers.

Prediction Distortion in Monte Carlo Tree Search and an Improved Algorithm

Teaching computer programs to play games through machine learning has been an important way to achieve better artificial intelligence (AI) in a variety of real-world applications. Monte Carlo Tree Search (MCTS) is one of the key AI techniques developed recently that enabled AlphaGo to defeat a legendary professional Go player. What makes MCTS particularly attractive is that it only understands the basic rules of the game and does not rely on expert-level knowledge. Researchers thus expect that MCTS can be applied to other complex AI problems where domain-specific expert-level knowledge is not yet available. So far there are very few analytic studies in the literature. In this paper, our goal is to develop analytic studies of MCTS to build a more fundamental understanding of the algorithms and their applicability in complex AI problems. We start with a simple version of MCTS, called random playout search (RPS), to play Tic-Tac-Toe, and find that RPS may fail to discover the correct moves even in a very simple game position of Tic-Tac-Toe. Both the probability analysis and simulation have confirmed our discovery. We continue our studies with the full version of MCTS to play Gomoku and find that while MCTS has shown great success in playing more sophisticated games like Go, it is not effective to address the problem of sudden death/win. The main reason that MCTS often fails to detect sudden death/win lies in the random playout search nature of MCTS, which leads to prediction distortion. Therefore, although MCTS in theory converges to the optimal minimax search, with real world computational resource constraints, MCTS has to rely on RPS as an important step in its search process, therefore suffering from the same fundamental prediction distortion problem as RPS does. By examining the detailed statistics of the scores in MCTS, we investigate a variety of scenarios where MCTS fails to detect sudden death/win. Finally, we propose an improved MCTS algorithm by incorporating minimax search to overcome prediction distortion. Our simulation has confirmed the effectiveness of the proposed algorithm. We provide an estimate of the additional computational costs of this new algorithm to detect sudden death/win and discuss heuristic strategies to further reduce the search complexity.

Performance Characterization of Parallel Game-tree Search Application Crafty

Game-tree search plays an important role in the field of Artificial Intelligence （AI）. In this paper, we characterize one parallel game-tree search workload in chess： the latest version of Crafty, a state of art program, on two Intel Xeon shared-memory multiprocessor systems. Our analysis shows that Crafty is latency-sensitive and the hash-table and dynamic tree splitting used in Crafty cause large scalability penalties. They consume 35%-50% of the running time on the 4-way system. Furthermore, Crafty is not bandwidth-limited.

LLRB算法的函数式建模及其机械化验证

基于机器定理证明的形式化验证技术不受状态空间限制,是保证软件正确性、避免因潜在软件缺陷带来严重损失的重要方法.LLRB(left-leaning red-black trees)是一种二叉搜索树变体,其结构比传统的红黑树添加了额外的左倾约束条件,在验证时无法使用常规的证明策略,需要更多的人工干预和努力,其正确性验证是一个公认的难题.为此,基于二叉搜索树类算法Isabelle验证框架,对其附加性质部分进行细化,并给出具体化的验证方案.在Isabelle中对LLRB插入和删除操作进行函数式建模,对其不变量进行模块化处理,并验证函数的正确性.这是首次在Isabelle中对函数式LLRB插入和删除算法进行机械化验证,相较于目前LLRB算法的Dafny验证,定理数由158减少至84,且无需构造中间断言,减轻了验证的负担;同时,为复杂树结构算法的函数式建模及验证提供了一定的参考价值.

树状结构在数据流求均值中的应用

数据采集过程中,随着数据的增加,数据的平均值持续发生变化。为了研究平均值的变化过程,分析平均值序列的计算方法是有必要的。传统的方法是使用线性顺序存储方式计算均值序列,总的时间复杂度高达O(n2)。提出利用树状结构存储方法求取均值序列,并介绍其实现方法,该方法时间复杂度大大降低,仅为O(n*lnn)。

基于KNN-RRT 的机械臂运动路径规划算法

针对机械臂路径规划过程中节点生成容易陷入局部最小值、算法收敛速度慢等问题,以目标引力函数渐进最优快速扩展随机树(P-RRT)为基础,提出一种基于KNN快速查找的自适应步长的改进RRT算法(KNN-RRT)。首先,在目标引力的基础上引入AdaGrad方法来调整自适应步长系数,降低随机点采样陷入局部最小值的问题;其次,利用KDTree来存储节点并利k邻近快速搜索查找相邻节点,提高算法的效率,并结合三次B样条曲线优化搜索路径的质量;最后,基于KNN-RRT算法在不同障碍物环境下进行实验,实验结果表明该算法在路径搜索时间、路径质量等方面有显著提升,提高算法的稳定性。

考虑综合性能最优的非短视快速天基雷达多目标跟踪资源调度算法

合理有效的资源调度是天基雷达效能得以充分发挥的关键。针对天基雷达多目标跟踪资源调度问题,建立了综合考虑目标威胁度、跟踪精度与低截获概率(LPI)的代价函数;考虑目标的不确定、天基平台约束以及长远期期望代价,建立了多约束下的基于部分可观测的马尔可夫决策过程(POMDP)的资源调度模型;采用拉格朗日松弛法将多约束下的多目标跟踪资源调度问题转换分解为多个无约束的子问题;针对连续状态空间、连续动作空间及连续观测空间引起的维数灾难问题,采用基于蒙特卡罗树搜索(MCTS)的在线POMDP算法—POMCPOW算法进行求解,最终提出了一种综合多指标性能的非短视快速天基雷达多目标跟踪资源调度算法。仿真表明,与已有调度算法相比,所提算法资源分配更合理,系统性能更优。

面向人员岸滩行进的三维路径规划算法研究

针对当前无法为人员岸滩行进提供科学合理的路径规划这一问题,论文基于蚁群算法提出了面向岸滩行进的最优路径规划算法。首先对基本的蚁群算法进行了改良,包括路径搜索方式、信息素更新策略和启发函数的合理设计等,改善了算法的收敛效率;然后定量结合多类岸滩场路径规划影响因子,构建了满足岸滩行进的代价函数;最终实现了面向岸滩行进的算法构建。该算法可为实现复杂地形条件下岸滩行进的最优路径解算和基于蚁群算法的相关三维路径规划分析研究提供参考借鉴。

基于聚类和GBDT的镀锌钢卷力学性能预测

热镀锌钢卷力学性能影响因素之间关系复杂,限制了模型精度的提升。采用k-means算法利用化学成分属性对镀锌钢卷数据集进行聚类,将数据聚成三种模式簇实现样本的优选。利用梯度提升树算法,开展各模式数据集与不划分模式的全数据集下的力学性能建模研究,最后结合网格搜索与交叉验证方法进行模型参数优化。研究结果表明,分模式下模型MAE误差相比于全数据集建模平均减小0.85 MPa。参数优化后,各模式下MAE误差平均减少5.19 MPa,RMSE误差平均减少3.63 MPa,提高了预测模型精度。

基于深度蒙特卡洛树搜索的拱坝仓面排序研究

合理的仓面排序方案对于加快工程进度和优化资源配置有着重要影响。然而,现有仓面排序方法将这一序贯决策问题简化,多数采用多属性决策方法,存在仅对大坝实时施工状态进行分析以及未考虑未来仓面浇筑方案对当前排序策略影响的问题;部分采用多目标优化方法进行仓面排序多目标优化问题分析,但主要是采用静态权重,存在忽略了仓面排序策略随环境动态变化的不足。针对以上问题,本文提出基于深度蒙特卡洛树搜索的拱坝仓面排序方法。首先,分析仓面排序问题的约束条件和目标函数,建立仓面排序强化学习模型;其次,针对仓面排序强化学习模型具有复杂且庞大的离散状态空间,为提高搜索效率,提出融合深度学习的蒙特卡洛树搜索方法,分别利用深度神经网络进行先验动作概率分布预测和策略函数评估;最后,以乌东德拱坝工程为例进行研究,结果表明本文方法可以有效地分析拱坝仓面排序问题,且相比于粒子群方法、证据理论方法,本文方法分析的施工工期可分别提前6天、14天,平均机械利用率分别提高1.19%、1.35%。本研究为拱坝仓面排序分析与优化提供了新思路。

Navi:基于自然语言交互的数据分析系统

随着大数据时代的到来,数据分析的作用日益显著.它能够从海量数据中发现有价值的信息,从而更有效地指导用户决策.然而,数据分析流程中存在三大挑战:分析流程高耦合、交互接口种类多和探索分析高耗时.为了应对上述挑战,提出了基于自然语言交互的数据分析系统Navi.该系统采用模块化的设计原则,抽象出主流数据分析流程的3个核心功能模块:数据查询、可视化生成和可视化探索模块,从而降低系统设计的耦合度.同时,Navi以自然语言作为统一的交互接口,并通过一个任务调度器实现了各功能模块的有效协同.此外,为了解决可视化探索中搜索空间指数级和用户意图不明确的问题,提出了一种基于蒙特卡洛树搜索的可视化自动探索方法,并设计了基于可视化领域知识的剪枝算法和复合奖励函数,提高了搜索效率和结果质量.最后,通过量化实验和用户实验验证了Navi的有效性.

结合K均值聚类和KD-Tree搜索的快速分形编码方法

利用部分失真搜索求解传统K均值聚类算法中的最近邻搜索问题,显著地减少了传统算法的乘法次数,从而提高了聚类速度;然后用改进后的聚类算法来加速分形编码:首先将定义域块聚类并为每个类建立一棵KD-Tree,编码时对每个值域块先后用部分失真搜索与近似最近邻搜索得到与其距离最近的若干KD-Tree及其上的若干最近邻,而其最优匹配块即由后者产生.实验结果表明,相对于全局搜索,该方法能大幅度地提高编码速度和较大地提高压缩比,而解码质量只有很小的下降;相对于同类方法,在相同压缩比下有更好的加速效果和解码质量.

一种基于决策树的比特币不可达节点发现方法

不可达节点是指比特币网络中不接收外部连接请求的网络工作节点,发现、验证均较为困难。现有研究大多集中于可达节点,而对不可达节点的研究较少。为此,提出一种基于决策树算法的不可达节点发现方法,可以从大量比特币地址中自动分类发现不可达节点。实验结果表明:所提方法在实验数据集上分类准确率为95.73%,召回率为91.97%;在真实数据上进行实测,并利用网络空间搜索引擎进行验证,所提方法实际分类准确率为53.75%,召回率约为76.86%。对实验中发现不可达节点的总量、地理分布、所属网络服务商等进行统计分析,为比特币监管工作提供有力技术支撑。

基于电压序列最小KL散度索引的低压台区拓扑识别

为了实现对低压台区拓扑结构的准确刻画,提出一种基于电压序列最小KL(Kullback-Leibler)散度与深度搜索相结合的拓扑识别方法。首先,采用Neville插值修复电压采样序列,利用改进的KL散度计算用户电压序列概率分布,并依据KL散度大小对用户所属台区进行划分;其次,基于最小KL散度确定深度搜索的索引方向,通过主干搜索与分支搜索遍历台区用户节点,判断用户之间的连接关系;最后,针对不同场景分析所提方案拓扑识别性能。仿真结果验证了所提方案的有效性。