最邻近搜索

最邻近搜索（NNS）又称为“最近点搜索”（Closest point search），是一个在尺度空间中寻找最近点的优化问题。问题描述如下：在尺度空间M中给定一个点集S和一个目标点q ∈ M，在S中找到距离q最近的点。很多情况下，M为多维的欧几里得空间，距离由欧几里得距离或曼哈顿距离决定。高德纳在《计算机程序设计艺术》（1973）一书的第三章中称之为 邮局问题，即居民寻找离自己家最近的邮局。