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 characteris...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.展开更多
MonteCloPi算法是一种基于蒙特卡洛树搜索(Monte Carlo tree search,MCTS)的任意时间子群发现算法,旨在使用MCTS策略构建非对称的最佳优先搜索树来发现高质量的多样性模式集,但是限制了目标为二值变量.为此,本文结合了数值目标的特点,...MonteCloPi算法是一种基于蒙特卡洛树搜索(Monte Carlo tree search,MCTS)的任意时间子群发现算法,旨在使用MCTS策略构建非对称的最佳优先搜索树来发现高质量的多样性模式集,但是限制了目标为二值变量.为此,本文结合了数值目标的特点,通过为置信度上界(upper confidence bound,UCB)公式选取合适的C值、动态调整各个样本的拓展权重并对搜索树进行剪枝、使用自适应top-k均值更新策略,将MonteCloPi算法拓展到了数值目标.最后,在UCI数据集、全国健康与营养调查(national health and nutrition examination survey,NHANES)听力测试数据集上的实验结果表明本文的算法相比其他算法可以发现更高质量的多样性模式集,并且最优子群的可解释性也更好.展开更多
为解决快速扩展随机树算法(rapid-exploration random tree,RRT*)在三维环境中盲目搜索路径以及缺乏节点扩展记忆性等问题,提出一种融合蚁群算法的双向搜索算法ACO-RRT*。为适应精细化三维建模环境和解决地面起伏不平坦等问题,对RRT*算...为解决快速扩展随机树算法(rapid-exploration random tree,RRT*)在三维环境中盲目搜索路径以及缺乏节点扩展记忆性等问题,提出一种融合蚁群算法的双向搜索算法ACO-RRT*。为适应精细化三维建模环境和解决地面起伏不平坦等问题,对RRT*算法进行改进优化。采用双向搜索策略,在起点和终点同时运行改进后的RRT算法和蚁群算法,相向而行,对路径长度和运行时间进行优化。针对生成路径不够平滑等问题,引入B样条曲线平滑策略优化路径。仿真结果表明,所提算法能够有效用于机器人三维路径规划。展开更多
In RFID(Radio Frequency IDentification)system,when multiple tags are in the operating range of one reader and send their information to the reader simultaneously,the signals of these tags are superimposed in the air,w...In RFID(Radio Frequency IDentification)system,when multiple tags are in the operating range of one reader and send their information to the reader simultaneously,the signals of these tags are superimposed in the air,which results in a collision and leads to the degrading of tags identifying efficiency.To improve the multiple tags’identifying efficiency due to collision,a physical layer network coding based binary search tree algorithm(PNBA)is proposed in this paper.PNBA pushes the conflicting signal information of multiple tags into a stack,which is discarded by the traditional anti-collision algorithm.In addition,physical layer network coding is exploited by PNBA to obtain unread tag information through the decoding operation of physical layer network coding using the conflicting information in the stack.Therefore,PNBA reduces the number of interactions between reader and tags,and improves the tags identification efficiency.Theoretical analysis and simulation results using MATLAB demonstrate that PNBA reduces the number of readings,and improve RFID identification efficiency.Especially,when the number of tags to be identified is 100,the average needed reading number of PNBA is 83%lower than the basic binary search tree algorithm,43%lower than reverse binary search tree algorithm,and its reading efficiency reaches 0.93.展开更多
In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log ...In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log h) of the running time for the general sequential B&B algorithm and the lower bound Ω(m/p+h log p) for the general parallel best-first B&B algorithm in PRAM-CREW are proposed, where p is the number of processors available. Moreover, the lower bound Ω(M/p+H+(H/p) log (H/p)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B&B algorithm is put forward. The parallel algorithm is the fastest one as p = max{hε, r}, where ε = 1/ rootlogh, and r is the largest branch number of the nodes in the state-space tree.展开更多
针对密度峰值聚类算法DPC(clustering by fast search and find of density peaks)时间复杂度高、准确度低的缺陷,提出了一种基于Ball-Tree优化的快速密度峰值聚类算法BT-DPC。算法利用第k近邻度量样本局部密度,通过构建Ball-Tree加速...针对密度峰值聚类算法DPC(clustering by fast search and find of density peaks)时间复杂度高、准确度低的缺陷,提出了一种基于Ball-Tree优化的快速密度峰值聚类算法BT-DPC。算法利用第k近邻度量样本局部密度,通过构建Ball-Tree加速密度ρ及距离δ的计算;在类簇分配阶段,结合k近邻思想设计统计学习分配策略,将边界点正确归类。通过在UCI数据集上的实验,将该算法与原密度峰值聚类算法及其改进算法进行了对比,实验结果表明,BT-DPC算法在降低时间复杂度的同时提高了聚类的准确度。展开更多
According to the researches on theoretic basis in part Ⅰ of the paper, the spanning tree algorithms solving the maximum independent set both in even network and in odd network have been developed in this part, part ...According to the researches on theoretic basis in part Ⅰ of the paper, the spanning tree algorithms solving the maximum independent set both in even network and in odd network have been developed in this part, part Ⅱ of the paper. The algorithms transform first the general network into the pair sets network, and then decompose the pair sets network into a series of pair subsets by use of the characteristic of maximum flow passing through the pair sets network. As for the even network, the algorithm requires only one time of transformation and decomposition, the maximum independent set can be gained without any iteration processes, and the time complexity of the algorithm is within the bound of O(V3). However, as for the odd network, the algorithm consists of two stages. In the first stage, the general odd network is transformed and decomposed into the pseudo-negative envelope graphs and generalized reverse pseudo-negative envelope graphs alternately distributed at first; then the algorithm turns to the second stage, searching for the negative envelope graphs within the pseudo-negative envelope graphs only. Each time as a negative envelope graph has been found, renew the pair sets network by iteration at once, and then turn back to the first stage. So both stages form a circulation process up to the optimum. Two available methods, the adjusting search and the picking-off search are specially developed to deal with the problems resulted from the odd network. Both of them link up with each other harmoniously and are embedded together in the algorithm. Analysis and study indicate that the time complexity of this algorithm is within the bound of O(V5).展开更多
文摘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.
文摘MonteCloPi算法是一种基于蒙特卡洛树搜索(Monte Carlo tree search,MCTS)的任意时间子群发现算法,旨在使用MCTS策略构建非对称的最佳优先搜索树来发现高质量的多样性模式集,但是限制了目标为二值变量.为此,本文结合了数值目标的特点,通过为置信度上界(upper confidence bound,UCB)公式选取合适的C值、动态调整各个样本的拓展权重并对搜索树进行剪枝、使用自适应top-k均值更新策略,将MonteCloPi算法拓展到了数值目标.最后,在UCI数据集、全国健康与营养调查(national health and nutrition examination survey,NHANES)听力测试数据集上的实验结果表明本文的算法相比其他算法可以发现更高质量的多样性模式集,并且最优子群的可解释性也更好.
文摘为解决快速扩展随机树算法(rapid-exploration random tree,RRT*)在三维环境中盲目搜索路径以及缺乏节点扩展记忆性等问题,提出一种融合蚁群算法的双向搜索算法ACO-RRT*。为适应精细化三维建模环境和解决地面起伏不平坦等问题,对RRT*算法进行改进优化。采用双向搜索策略,在起点和终点同时运行改进后的RRT算法和蚁群算法,相向而行,对路径长度和运行时间进行优化。针对生成路径不够平滑等问题,引入B样条曲线平滑策略优化路径。仿真结果表明,所提算法能够有效用于机器人三维路径规划。
基金the National Natural Science Foundation of China under Grant 61502411Natural Science Foundation of Jiangsu Province under Grant BK20150432 and BK20151299+7 种基金Natural Science Research Project for Universities of Jiangsu Province under Grant 15KJB520034China Postdoctoral Science Foundation under Grant 2015M581843Jiangsu Provincial Qinglan ProjectTeachers Overseas Study Program of Yancheng Institute of TechnologyJiangsu Provincial Government Scholarship for Overseas StudiesTalents Project of Yancheng Institute of Technology under Grant KJC2014038“2311”Talent Project of Yancheng Institute of TechnologyOpen Fund of Modern Agricultural Resources Intelligent Management and Application Laboratory of Huzhou Normal University.
文摘In RFID(Radio Frequency IDentification)system,when multiple tags are in the operating range of one reader and send their information to the reader simultaneously,the signals of these tags are superimposed in the air,which results in a collision and leads to the degrading of tags identifying efficiency.To improve the multiple tags’identifying efficiency due to collision,a physical layer network coding based binary search tree algorithm(PNBA)is proposed in this paper.PNBA pushes the conflicting signal information of multiple tags into a stack,which is discarded by the traditional anti-collision algorithm.In addition,physical layer network coding is exploited by PNBA to obtain unread tag information through the decoding operation of physical layer network coding using the conflicting information in the stack.Therefore,PNBA reduces the number of interactions between reader and tags,and improves the tags identification efficiency.Theoretical analysis and simulation results using MATLAB demonstrate that PNBA reduces the number of readings,and improve RFID identification efficiency.Especially,when the number of tags to be identified is 100,the average needed reading number of PNBA is 83%lower than the basic binary search tree algorithm,43%lower than reverse binary search tree algorithm,and its reading efficiency reaches 0.93.
基金This paper was supported by Ph. D. Foundation of State Education Commission of China.
文摘In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log h) of the running time for the general sequential B&B algorithm and the lower bound Ω(m/p+h log p) for the general parallel best-first B&B algorithm in PRAM-CREW are proposed, where p is the number of processors available. Moreover, the lower bound Ω(M/p+H+(H/p) log (H/p)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B&B algorithm is put forward. The parallel algorithm is the fastest one as p = max{hε, r}, where ε = 1/ rootlogh, and r is the largest branch number of the nodes in the state-space tree.
文摘针对密度峰值聚类算法DPC(clustering by fast search and find of density peaks)时间复杂度高、准确度低的缺陷,提出了一种基于Ball-Tree优化的快速密度峰值聚类算法BT-DPC。算法利用第k近邻度量样本局部密度,通过构建Ball-Tree加速密度ρ及距离δ的计算;在类簇分配阶段,结合k近邻思想设计统计学习分配策略,将边界点正确归类。通过在UCI数据集上的实验,将该算法与原密度峰值聚类算法及其改进算法进行了对比,实验结果表明,BT-DPC算法在降低时间复杂度的同时提高了聚类的准确度。
文摘According to the researches on theoretic basis in part Ⅰ of the paper, the spanning tree algorithms solving the maximum independent set both in even network and in odd network have been developed in this part, part Ⅱ of the paper. The algorithms transform first the general network into the pair sets network, and then decompose the pair sets network into a series of pair subsets by use of the characteristic of maximum flow passing through the pair sets network. As for the even network, the algorithm requires only one time of transformation and decomposition, the maximum independent set can be gained without any iteration processes, and the time complexity of the algorithm is within the bound of O(V3). However, as for the odd network, the algorithm consists of two stages. In the first stage, the general odd network is transformed and decomposed into the pseudo-negative envelope graphs and generalized reverse pseudo-negative envelope graphs alternately distributed at first; then the algorithm turns to the second stage, searching for the negative envelope graphs within the pseudo-negative envelope graphs only. Each time as a negative envelope graph has been found, renew the pair sets network by iteration at once, and then turn back to the first stage. So both stages form a circulation process up to the optimum. Two available methods, the adjusting search and the picking-off search are specially developed to deal with the problems resulted from the odd network. Both of them link up with each other harmoniously and are embedded together in the algorithm. Analysis and study indicate that the time complexity of this algorithm is within the bound of O(V5).
