邻居搜索 Neighbor Search
邻居搜索是计算机科学中一个概念，尤其在数据挖掘和机器学习领域扮演着重要角色。它指的是确定在模拟盒子中每个粒子（通常是原子）周围的邻近粒子的过程。这个过程对于计算粒子间的相互作用，如范德华力 (van der Waals forces) 和短程排斥力非常重要。它涉及在给定的数据集中快速定位与特定查询点距离最近的点或一组点。
由于粒子间的相互作用通常只在短距离内显著，因此只需要考虑每个粒子周围一定范围内的其他粒子。这个范围通常被称为截断半径 (cutoff radius) 。在每次时间步长的模拟中，都需要进行邻居搜索，以更新这个范围内的粒子列表，因为粒子在模拟过程中会不断移动。
邻居搜索的主要目的包括：
- 效率：通过限制计算范围到邻近粒子，可以显著减少所需的计算量，提高模拟的效率。
- 准确性：确保在截断半径内正确计算粒子间的相互作用力，这对于模拟结果的准确性至关重要。
- 处理非键相互作用：邻居搜索有助于处理那些不通过化学键连接但仍然有物理相互作用的粒子对。
在实际的模拟中，邻居搜索通常需要构建一个数据结构，如网格 (grid) 或链接单元列表 (linked-cell list)，以快速定位每个粒子的邻近粒子。这个过程在每次模拟步骤中都是必需的，并且对性能有显著影响，因此在高性能计算中，邻居搜索的优化是一个重要的研究方向。在 GROMACS 等分子动力学软件中，邻居搜索可以通过 CPU 或 GPU 加速，以提高模拟的速度和效率。
邻居搜索的挑战在于，随着数据集规模的增长，计算成本会显著增加，尤其是在高维空间中，这被称为维度灾难。为了提高搜索效率，研究者们开发了多种数据结构和算法，包括 k-d 树、球树和倒排索引等，这些结构能够加速在大规模数据集中的搜索过程。此外，由于精确搜索可能非常耗时，许多场景下会采用近似算法来快速找到一个接近最优的解。