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

作     者：张挺 王宗锴 林震寰 郑相涵 

作者机构：福州大学土木工程学院 福州大学计算机与大数据学院 

出 版 物：《工程科学与技术》 (Advanced Engineering Sciences)

年 卷 期：2023年

核心收录：

学科分类：07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：国家自然科学基金项目（52079032） 福建省水利科技重大项目（MSK202215） 

主　　题：kd-tree 粒子近邻搜索 自适应 网格搜索法 坐标下降法 

摘      要：对于大规模运动模拟问题而言，近邻点的搜索效率将对整体的运算效率产生显著影响。本文基于关联性分析建立kd-tree的最大深度dmax与粒子总数N的自适应关系式，提出了kd-tree自动终止准则，即ATC-kd-tree，同时还考虑了叶子节点大小阈值n0对近邻搜索效率的影响。实验表明ATC-kd-tree具有更高的近邻搜索效率，适用性更强，可求解不同N值的近邻搜索问题，解决了粒子总数N发生改变时需要再次率定最大深度dmax的问题。同时，本文还提出了网格搜索法组合坐标下降法的两步参数优化算法GSCD法。通过二维阿米巴虫形状的参数优化实验发现，GSCD法可更为快速地率定ATC-kd-tree的可变参数，其优化效率相比于网格搜索法最高提升了205%，相较于改进网格搜索法最高提升了90%。