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

摘要

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

关键词

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

基金资助

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