k-d树

Leth · 2022-02-22 20:57:19 · 个人记录

P6247 [SDOI2012]最近最远点对

题意

• 给定n个点的横纵坐标，求其中两个点的最小距离和最大距离（输出浮点数，保留两位小数）
• 数据范围：0<n≤10^5且输入的所有数均为不超过10^9的非负数

  解题

• 很显然，运用到了k-d树下面阐释参考此博客（k-d树（ k-维树的缩写）是在k维欧几里德空间组织点的数据结构。k-d树可以使用在多种应用场合，如多维键值搜索（例：范围搜寻及最邻近搜索）。）
• 利用k-d树可以直接求出最小距离，最大距离则可根据最小距离公式类比推出，

  k-d树：

  • 它是一种具有如下特征的二叉树：
    1. 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
    2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    3. 它的左、右子树也分别为二叉搜索树；
  • 可以以平均O(lg(n))的时间复杂度搜索数据
  • 构建：
    • 在多维空间存在一个关键问题：每个数据条目由多个数值组成，无法比较
    • 原理：我们不比较全部的k维数据，而是选择其中某一个维度比较，根据这个维度进行空间划分
      1. 判断出在哪一个维度比较：也就是说，我们所要切割的面在哪一个维度上。当然这种切割需要遵循一个基本要求，那就是尽量通过这个维度的切割，使得数据集均分（为二）；
      2. 判断以哪个数据为依据划分：上面我们说，要使得数据集均分为二，那当然要选择一个合适的数据项，充当这个划分的“点”。
      3. 总结：就是要选择一个数据项，以这个数据项的某个维度的值为标准，同一维度的值大于这个值的数据项，划分为一部分，小于的划分为另一部分。根据这种划分来构建二叉树，就如同二叉搜索树那样。
    • 依据需要，要完成两项工作：
      1. 确定划分维度：注：这个维度上所有数据项数值的方差尽可能大（数据在这个维度上尽可能分散）很好理解，只是为让数据更好划分，这就好比是我们切东西，如果你切的是一根黄瓜，当让横着切要比竖着切更容易
      2. 选择充当切割标准的数据项：注：只需要求得这个维度上所有数值的中位数即可，大的一半，小的一半
    • 至此，终于可以设计出k-d树的构建算法了：
      1. 从n个度里选出方差最大的维度d，依据维度d上所有数据项的中位数mid将其划分为两个数据子集D_l，D_r（左子树，右子树），建立树节点，存储这次划分的情况（记录划分的维度d以及中位数mid）
      2. 对D_l,D_r重复进行以上的划分，并且将新生成的树节 点设置为上一次划分的左右孩子（递归），直到不能再划分（当前节点中包含的数据项的数量小于了我们事先规定的阈值，不失一般性，我在此篇博客中默认这个阈值是2，也就是说所有叶子节点包含的数据项不会多于2条）为止，此时将对应的数据保存至最后的节点中，这些最后的节点也就是叶子节点。

         类或函数           |作用
         class-KdTreeNode  |kd-tree节点，包含以下6个Attributes
         Attribute1-data   |树节点属性，代表这个节点的数据项，其实是一个列表，如果不是叶子节点，则为空
         Attribute2-split  |树节点属性，代表构建树时，对这个节点进行分割所依据的数据维度
         Attribute3-median |树节点属性，代表构建树时，所有上面split维度上数据的中位数
         Attribute4-left   |树节点属性，代表左孩子
         Attribute5-right  |树节点属性，代表右孩子
         Attribute6-parent |树节点属性，代表父亲节点，作用是在后面的搜索算法中用
         Attribute7-visited|树节点属性，代表此节点是否被算法回溯遍历，作用是在后面的搜索算法中用
         func-getSplit     |函数，得到所有维度中方差最大那个维度的序号
         func-getMedian    |函数，得到要分割的维度的中位数

  • 这里使用numpy库，假设现在已经将所有的数据项读入为一个ndarray型的数据矩阵datamatrix，datamatrix的每一行代表了一个数据项。

    搜索算法

• 构建好kd-tree后，就可以执行搜索算法了。其实，这也是信息检索最常见的模式，先构建索引，然后依照索引执行搜索算法。当然几乎所有的搜索算法都与其索引是配套的，也就是说，即便是同样的数据，索引不同，其搜索算法就不同，而各有各的技巧
• 基本思路：
  1. 依照非叶节点中存储的分割维度以及中位数信息，自根节点始，从上向下搜索，直到到达叶子。遍历的原则当然是比较分割维度上，查询值与中位数的大小，设查询为Q，当前遍历到的节点为u，则若Q[u.split] > u.median，继续遍历u的右子树，反之，遍历左子树。
  2. 遍历到叶子之后，计算叶子节点中与查询Q距离最小的数据项与查询的距离，记为minDis；其后执行“回溯”操作，回溯至当前节点的父节点，判断以Q为球心，以minDis为半径的超球面是否与这个父节点的另一个分支所代表的区域有交集（这里的区域是一个超矩形，它包含了所有这个节点代表的数据项）。如果没有，继续向上一层回溯；如果有，则按照1步继续执行，探底到叶子节点后，如果此时Q与这个叶子节点中的数据项有更小的距离，则更新minDis。
  3. 持续进行这两步，直到回溯至根节点，且根节点的两个分支都搜索过为止。
• 如何判断以查询Q为球心，以当前的minDis为半径的超球面与树中，一个非叶节点所代表的超矩形是否相交 ：一种简单的方法是在构建树的时候直接给每个节点赋值一个超矩形，这个超矩形以一个树节点属性的形式存在。一般情况下是给出超矩形的一个最大点和一个最小点。判断的方法只需要看如下的两个条件是否都成立即可：
  1. Q[u.split] + minDis >= minPoint[u.split]
  2. Q[u.split] - minDis >= maxPoint[u.split]
• 其中，u为查询当前遍历到的节点的父节点，minPoint与maxPoint为u所代表的超矩形的最大点和最小点（所谓最大最小点，那二维空间的矩形来说，就是他的右上角的点和左下角的点，分别拥有这个矩形范围内各个维度上的最大值和最小值）
• 原因：以Q为球心，以当前这个矩形区域的一个点为球面上一点的一个超球面，一定是经过了当前这个叶子所代表的区域，但是同时它不可能完全覆盖他的兄弟节点代表的区域。

  说了这么多，回归题目：

• 最小距离是可以用k-d树解决的经典模型，但是这道题还要求一个最大距离,仿照求最小距离的估价函数，可以写出一个最大距离的估价函数，然后和最小距离一样去求即
• maxdis(p) = log(\sum_{i = 0}^{degree}max((p_i-mn_i)^2,(p_i-mx_i)^2)
• 如果提前就把整棵树建好，求最小距离的时候，会收到自己的影响，可以动态插入点，先查询当前点和之前已经插入的点的贡献，再插入当前点。可以采用random_shuffle 随机打乱